Python: 每日一题 58
本帖最后由 ooxx7788 于 2017-6-4 12:41 编辑根据给定的数字（n）返回一个升序的数组，数组中的值的平方和等于给定数(n)的平方。
当有多个组合时，返回倒序数字最大的那一组数组。
是不是看文字有点难懂呢？看例子：
decompose(11) ---> 11**2 = sum(map(lambda x:x**2,))
虽然也满足条件，但是因为9小于10，所以不是结果
再看一个列子：
decompose(50)--->
当然,也是不能做为答案的（这就不要算了），也是不可以的。如果没有合适的结果，那么就返回None。
**** Hidden Message ***** def decompose(n):
results = []
maxi = n-1
queue = [ for i in range(2,n)]
while queue:
q = queue.pop()
if results and max(q) < maxi:
return results[-1]
for i in range(min(q)-1,0,-1):
if sum(map(lambda x:x*x,q)) + i*i == n*n and i not in q:
results.append(sorted(q + ))
maxi = max(q)
elif sum(map(lambda x:x*x,q)) + i*i < n*n and i not in q:
queue.append(q+)
else:
return None
print(decompose(50))
A*搜索算法，不过好像效率不是很高，尤其当n比较大的时候 本帖最后由 ooxx7788 于 2017-6-3 23:03 编辑
jerryxjr1220 发表于 2017-6-3 22:18
A*搜索算法，不过好像效率不是很高，尤其当n比较大的时候
能算出结果来应该是没什么问题，但是这种列表型的题目，又是while又是for的，基本上遇到大列表就过不去了。
不过答案还是很不错的。 有点厉害~ 66666 xuexi yixia 学习一下 looklook 学习 想知道这个while起到了什么作用，另外我运行你这个代码不会出现你上面说到的另外一组数据 哨子1122 发表于 2017-6-7 16:44
想知道这个while起到了什么作用，另外我运行你这个代码不会出现你上面说到的另外一组数据
def decompose(n):
total = 0
answer =
while len(answer):
print('***')
temp = answer.pop()
total += temp ** 2
for i in range(temp - 1, 0, -1):
if total - (i ** 2) >= 0:
total -= i ** 2
answer.append(i)
print(answer, total)
if total == 0:
return sorted(answer)
return None
建议你把程序改成我这样的，然后运行一次50.
再仔细研究研究就懂了。 看起来题目的意思是每个数字只能用一次吧
用了工具把组合都算出来，才发现原来分解方式多得很，基本上不会有None的情况
那算出所有组合反而慢了
import math
import itertools
# 用字典，itertools的组合工具
def decompose(n):
dit = {i:i**2 for i in range(n+1)}
m = n-1 # 极限最大值
result = []
while 1:
x = dit - dit # 平方差
left = int(math.sqrt((x))) # 最大剩余数
if left>x or n<=1: # 过了之后就重复了，等于凑不出结果
return None
a = for i in range(left,0,-1)]
for i in range(1,left): # 剩下的所有组合可能算出来与结果对比
result.append()
if list(filter(None,result))!=[]: # 不是空列表就表示有结果了
result = +]
return sorted(result)
m -= 1 # 极限最大值向后移一位，排除一个数 kakan 求教。。。为什么我fun(50) 没得出最大数是 49 想不通
def fun57(num):
sum1 = num ** 2
list1 = list(x**2 for x in range(1,num))
list1.reverse()
length = len(list1)
list2 = []
while length:
for each in range(length):
if sum1 >= list1:
sum1 -= list1
list2.append(int(list1**0.5))
if sum1 == 0:
get = True
break
elif list1 == 1 and sum1 !=0:
get = False
if get:
return sorted(list2)
list2 = []
list1.remove(list1)
length -= 1
sum1 = num ** 2
print(fun57(11))
print(fun57(50)) def decompose(num):
global lst# 全局列表
for i in range(num-1, 0, -1):
lst.append(i)# 大往小遍历
total = sum(map(lambda x: x ** 2, lst))# 求和
if total == num**2:# 与num平方相等返回list
return lst
elif total < num ** 2:# 小于则继续递归
decompose(i)
else:
lst.pop()# 大于则弹出
else:
return lst
lst = []
print(decompose(50000)) study 1 看看 学习啦 1
页:
[1]