Python：每日一题97（答题领鱼币）

冬雪雪冬

我们在92题中说到“1，2，4，8，16，32，64和128这8个数字利用加法可以得到1~255中的任意数字”
现在把题目变换一下，用1， 3， 9， 27等3的幂，利用加法和减法组成任意的整数，3的幂可以使用其中任意一个或几个，但每个数字只能使用一次，例如：

>>> fun(40)
40 = 27 + 9 + 3 + 1 
>>> fun(41)
41 = 81 - 27 - 9 - 3 - 1
>>> fun(12345)
12345 = 19683 + 27 + 9 - 6561 - 729 - 81 - 3

现在我们就一起编写这个函数吧，要求参数为一个正整数，函数最后打印出结果或return返回结果。

其实负数也可以做，为了简单点，就取1~n的正整数了。

我的解法：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

1=1
2=3-1
3=3
4=3+1
5=9-4=9-(3+1)
6=9-3
7=9-2=9-(3-1)
8=9-1
9=9
10=9+1
11=9+2=9+(3-1)
12=9+3
13=9+4=9+(3+1)
14=27-13=27-(9+3+1)
其实可以利用动态规划解的

一条小鱼儿

       感觉很像二进制，百度下存在一种对称三进制：将 -1，0，1作为基。如楼上说的十进制14转化成对称三进制则为：1TTT(我们将-1用T代替)即：3^3-3^2-3^1-3^0=27-9-3-1.如果用纯粹的三进制则会出现2：
       对称三进制： 14除3补1  5除3补1 2除3补1 1除3余1             即得到1TTT
       普通三进制： 14除3余2  4除3余1 1除3余1             即得到112=9+3+2
       综上可以使用对称三进制思路写任意数余2补1

左手十字

楼上的112=9+3+2是怎么解的？

jerryxjr1220

jerryxjr1220 发表于 2017-9-9 18:41
1=1
2=3-1
3=3

写个递归算法。

def calc(n):
  i = 0
  while n>3**i:
    i+=1
  else:
    if n==3**i:
      return str(n)
    else:
      if n>(3**i)/2.0:
        return str(3**i)+'-'+calc(3**i-n).replace('-','*').replace('+','-').replace('*','+')
      else:
        return str(3**(i-1))+'+'+calc(n-3**(i-1))

print(calc(12345))

solomonxian

1、换成另类三进制表示，,逢2进1自己变-1，算权重；2、字符串操作，接上符号输出

def fun(n):
    num = []
    while n:
        n, m = divmod(n, 3)
        if m == 2:
            n += 1
            m = -1
        num.append(m)

    result = "+".join(str(3**i*num[i]) for i in range(len(num)) if num[i])
    return result.replace("+-", "-")

bush牛

左手十字 发表于 2017-9-9 20:36
楼上的112=9+3+2是怎么解的？

普通三进制就是看余数，然后反过来就是这个数了。
在举个栗子：
15/3商 5 余 0   
5/3  商 1 余 2 （到这一步就可以了，只要商为0,1,2就可以直接出来了）
1/3  商 0 余 1
反过来 1 2 0  等于15

BngThea

路过学习

mmdn

def calc(n):
  i = 0
  while n>3**i:
    i+=1
  else:
    if n==3**i:
      return str(n)
    else:
      if n>(3**i)/2.0:
        return str(3**i)+'-'+calc(3**i-n).replace('-','*').replace('+','-').replace('*','+')
      else:
        return str(3**(i-1))+'+'+calc(n-3**(i-1))

print(calc(12345))

schweinfan

只好来看看答案了。。

不可以

偷偷看一下

lxchace

#Magic Power of Three

def Index_three(n):
    if n<=0:
        return False
    i = 0
    while True:
        if pow(3,i)<=n<pow(3,i+1):
            return i,i+1
        i += 1

#print(Index_three(0))

def add_sub(n):
    if n<=0:
        return "请输入大于0的数！！！"
    elif n==1:
        return "1"
    elif n>1:
        index_n = Index_three(n)
        if n == pow(3,index_n[0]):
            return "{}".format(n)
        else:
            if n<=(pow(3,index_n[1])//2):
                return "{0} + {1}".format(pow(3,index_n[0]),add_sub(n-pow(3,index_n[0])))
            else:
                add_sub_str = add_sub(pow(3,index_n[1])-n)
                if len(add_sub_str)>1:
                    #print(add_sub_str[2])
                    for i in range(len(add_sub_str)):
                        if add_sub_str[i] == '+':
                            add_sub_str = add_sub_str[:i] + '-' + add_sub_str[i+1:]
                        elif add_sub_str[i] == '-':
                            add_sub_str = add_sub_str[:i] + '+' + add_sub_str[i+1:]
                return "{0} - {1}".format(pow(3,index_n[1]),add_sub_str)

#print(add_sub(3))

def main():
    for i in range(12345,12346):
        add_sub_str = "{0} = {1} ".format(i,add_sub(i))
        print(add_sub_str)
    return

if __name__ == "__main__":
    main()

染黑

染黑

{:

新手潘包邮

一条小鱼儿 发表于 2017-9-9 19:55
感觉很像二进制，百度下存在一种对称三进制：将 -1，0，1作为基。如楼上说的十进制14转化成对称三进 ...

这个思路强

新手潘包邮

import math
def fun(n):
    new = []
    while True:
        if n%3 == 2:
            new.append(-1)
            n = (n+2)
        elif n%3 == 1:
            new.append(1)
            if n == 1:
                break     
        else:
            new.append(0)
        n = n//3
    new.reverse()
    new1 = []
    j = len(new)-1
    for i in range(len(new)):
        new1.append(new[i] * 3 **j)
        j -= 1
    string = "+".join(map(str, new1)).replace("+-", "-").replace("+0", "")
    #return string
    #string
    #print(new, new1, string)
    #string1 = []
    #for i in range(len(string) - 1, 0, -1):
        #string1.append(string[i])
        #if string[i] == "-" :
           # continue
   # string1.reverse()
    return string
        
fun(12345645464)

ABC23

回复

archlzy

回复看咪咪

小贤啊哦

看看