Python: 每日一题 58

ooxx7788

根据给定的数字（n）返回一个升序的数组，数组中的值的平方和等于给定数(n)的平方。
当有多个组合时，返回倒序数字最大的那一组数组。

是不是看文字有点难懂呢？看例子：

1. decompose(11)    --->[1,2,4,10]       11**2 = sum(map(lambda x:x**2,[1,2,4,10]))   
   
2.                                      [2,6,9]           虽然也满足条件，但是因为9小于10，所以不是结果
   

复制代码

再看一个列子：

1. decompose(50)  ---> [1, 3, 5, 8, 49]

复制代码

当然[11],[50]也是不能做为答案的（这就不要算了），[1,1,1,…,1]也是不可以的。如果没有合适的结果，那么就返回None。

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

jerryxjr1220

1. def decompose(n):
   
2.         results = []
   
3.         maxi = n-1
   
4.         queue = [[i] for i in range(2,n)]
   
5.         while queue:
   
6.                 q = queue.pop()
   
7.                 if results and max(q) < maxi:
   
8.                         return results[-1]
   
9.                 for i in range(min(q)-1,0,-1):
   
10.                         if sum(map(lambda x:x*x,q)) + i*i == n*n and i not in q:
    
11.                                 results.append(sorted(q + [i]))
    
12.                                 maxi = max(q)
    
13.                         elif sum(map(lambda x:x*x,q)) + i*i < n*n and i not in q:
    
14.                                 queue.append(q+[i])
    
15.         else:
    
16.                 return None
    
17.        
    
18. print(decompose(50))

复制代码

[1, 3, 5, 8, 49]
[Finished in 0.4s]
A*搜索算法，不过好像效率不是很高，尤其当n比较大的时候

ooxx7788

jerryxjr1220 发表于 2017-6-3 22:18
[1, 3, 5, 8, 49]
[Finished in 0.4s]
A*搜索算法，不过好像效率不是很高，尤其当n比较大的时候

能算出结果来应该是没什么问题，但是这种列表型的题目，又是while又是for的，基本上遇到大列表就过不去了。
不过答案还是很不错的。

WelanceLee

有点厉害~

badaoqingchen

66666

瓦蓝

xuexi yixia

小锟

学习一下

花寺情僧

looklook

哨子1122

学习

哨子1122

想知道这个while起到了什么作用，另外我运行你这个代码不会出现你上面说到的另外一组数据

ooxx7788

哨子1122 发表于 2017-6-7 16:44
想知道这个while起到了什么作用，另外我运行你这个代码不会出现你上面说到的另外一组数据

1. def decompose(n):
   
2.     total = 0
   
3.     answer = [n]
   
4.     while len(answer):
   
5.         print('***')
   
6.         temp = answer.pop()
   
7.         total += temp ** 2
   
8.         for i in range(temp - 1, 0, -1):
   
9.             if total - (i ** 2) >= 0:
   
10.                 total -= i ** 2
    
11.                 answer.append(i)
    
12.                 print(answer, total)
    
13.                 if total == 0:
    
14.                     return sorted(answer)
    
15.     return None
    

复制代码

建议你把程序改成我这样的，然后运行一次50.
再仔细研究研究就懂了。

solomonxian

看起来题目的意思是每个数字只能用一次吧
用了工具把组合都算出来，才发现原来分解方式多得很，基本上不会有None的情况
那算出所有组合反而慢了

1. import math
   
2. import itertools
   
3. # 用字典，itertools的组合工具
   
4. def decompose(n):
   
5.     dit = {i:i**2 for i in range(n+1)}
   
6.     m = n-1 # 极限最大值
   
7.     result = []
   
8.     while 1:
   
9.         x = dit[n] - dit[m] # 平方差
   
10.         left = int(math.sqrt((x))) # 最大剩余数
    
11.         if left>x or n<=1: # 过了之后就重复了，等于凑不出结果
    
12.             return None
    
13.         
    
14.         a = [dit[i] for i in range(left,0,-1)]
    
15.         for i in range(1,left): # 剩下的所有组合可能算出来与结果对比
    
16.             result.append([j for j in itertools.combinations(a,i) if sum(j)==x])
    
17.             
    
18.             if list(filter(None,result))!=[]: # 不是空列表就表示有结果了
    
19.                 result = [m]+[int(k**0.5) for k in max(result)[0]]
    
20.                 return sorted(result)
    
21.         m -= 1 # 极限最大值向后移一位，排除一个数

复制代码

咕咕鸡鸽鸽

kakan

咕咕鸡鸽鸽

求教。。。为什么我fun(50) 没得出最大数是 49   想不通

1. def fun57(num):
   
2.     sum1 = num ** 2
   
3.     list1 = list(x**2 for x in range(1,num))
   
4.     list1.reverse()
   
5.     length = len(list1)
   
6.     list2 = []
   
7.     while length:
   
8.         for each in range(length):        
   
9.             if sum1 >= list1[each]:
   
10.                 sum1 -= list1[each]
    
11.                 list2.append(int(list1[each]**0.5))
    
12.             if sum1 == 0:
    
13.                 get = True
    
14.                 break
    
15.             elif list1[each] == 1 and sum1 !=0:
    
16.                 get = False
    
17. 
    
18.         if get:
    
19.             return sorted(list2)
    
20.             
    
21.         list2 = []                           
    
22.         list1.remove(list1[0])
    
23.         length -= 1
    
24.         sum1 = num ** 2
    
25.    
    
26.         
    
27. print(fun57(11))
    
28. print(fun57(50))

复制代码

Geoffreylee

1. def decompose(num):
   
2.     global lst  # 全局列表
   
3.     for i in range(num-1, 0, -1):
   
4.         lst.append(i)  # 大往小遍历
   
5.         total = sum(map(lambda x: x ** 2, lst))  # 求和
   
6.         if total == num**2:  # 与num平方相等返回list
   
7.             return lst
   
8. 
   
9.         elif total < num ** 2:  # 小于则继续递归
   
10.             decompose(i)
    
11. 
    
12.         else:
    
13.             lst.pop()  # 大于则弹出
    
14.     else:
    
15.         return lst
    
16. 
    
17. 
    
18. lst = []
    
19. print(decompose(50000))

复制代码

holiday_python

study

19971023

1

z2x2c8

看看

nononoyes

学习啦

wwwwwise

1