Python：每日一题97（答题领鱼币）
本帖最后由 冬雪雪冬 于 2017-9-9 18:45 编辑我们在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的正整数了。
我的解法：
**** Hidden Message ***** 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补15除3补1 2除3补1 1除3余1 即得到1TTT
普通三进制： 14除3余24除3余1 1除3余1 即得到112=9+3+2
综上可以使用对称三进制思路写任意数余2补1
楼上的112=9+3+2是怎么解的？ 本帖最后由 jerryxjr1220 于 2017-9-10 08:25 编辑
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)) 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) for i in range(len(num)) if num)
return result.replace("+-", "-") 左手十字 发表于 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 路过学习
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)) 只好来看看答案了。。 偷偷看一下 #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):
return "{}".format(n)
else:
if n<=(pow(3,index_n)//2):
return "{0} + {1}".format(pow(3,index_n),add_sub(n-pow(3,index_n)))
else:
add_sub_str = add_sub(pow(3,index_n)-n)
if len(add_sub_str)>1:
#print(add_sub_str)
for i in range(len(add_sub_str)):
if add_sub_str == '+':
add_sub_str = add_sub_str[:i] + '-' + add_sub_str
elif add_sub_str == '-':
add_sub_str = add_sub_str[:i] + '+' + add_sub_str
return "{0} - {1}".format(pow(3,index_n),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() {:10_254:} {:{:5_91:}{:5_102:} 一条小鱼儿 发表于 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 * 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)
#if string == "-" :
# continue
# string1.reverse()
return string
fun(12345645464) 回复 回复看咪咪 看看
页:
[1]
2