Python: 每日一题 58

ooxx7788

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

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

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

再看一个列子：

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

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

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

jerryxjr1220

def decompose(n):
        results = []
        maxi = n-1
        queue = [[i] 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 + [i]))
                                maxi = max(q)
                        elif sum(map(lambda x:x*x,q)) + i*i < n*n and i not in q:
                                queue.append(q+[i])
        else:
                return None
        
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起到了什么作用，另外我运行你这个代码不会出现你上面说到的另外一组数据

def decompose(n):
    total = 0
    answer = [n]
    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.
再仔细研究研究就懂了。

solomonxian

看起来题目的意思是每个数字只能用一次吧
用了工具把组合都算出来，才发现原来分解方式多得很，基本上不会有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[n] - dit[m] # 平方差
        left = int(math.sqrt((x))) # 最大剩余数
        if left>x or n<=1: # 过了之后就重复了，等于凑不出结果
            return None
        
        a = [dit[i] for i in range(left,0,-1)] 
        for i in range(1,left): # 剩下的所有组合可能算出来与结果对比
            result.append([j for j in itertools.combinations(a,i) if sum(j)==x])
            
            if list(filter(None,result))!=[]: # 不是空列表就表示有结果了
                result = [m]+[int(k**0.5) for k in max(result)[0]] 
                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[each]:
                sum1 -= list1[each]
                list2.append(int(list1[each]**0.5))
            if sum1 == 0:
                get = True
                break
            elif list1[each] == 1 and sum1 !=0:
                get = False

        if get:
            return sorted(list2)
            
        list2 = []                            
        list1.remove(list1[0])
        length -= 1
        sum1 = num ** 2
    
        
print(fun57(11))
print(fun57(50))

Geoffreylee

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))

holiday_python

study

19971023

1

z2x2c8

看看

nononoyes

学习啦

wwwwwise

1