[已解决]Python：每日一题 303

zltzlt

今天的题目：

给一个正整数 n，求最少多少个平方数（比如1、4、9...）的和等于 n。

示例 1：

输入：12
输出：3
解释：4 + 4 + 4

示例 2：

输入：13
输出：2
解释：4 + 9

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Stubborn

2020-1-11 18:05:16

zltzlt 发表于 2020-1-11 17:32
输入超过 8400 的数会超时

1. def fun303(number:int):
   
2.     """四平方和定理，任何一个正整数都可以表示成不超过四个整数的平方之和"""
   
3.     import math
   
4.     while number % 4 == 0:
   
5.         number /= 4
   
6.     if number % 8 == 7 : return 4
   
7.     l = int(math.sqrt(number)) + 1
   
8.     for a in range(l):
   
9.         b = int(math.sqrt(number - a*a))
   
10.         if a*a + b*b == number:
    
11.             if a == 0:return 1
    
12.             return 2
    
13.     return 3

复制代码

跳转到最佳答案楼层

阴阳神万物主

玄学求解：

1. def solve(n:'int > 0')->int:
   
2.     def pa(n):
   
3.         def getn(a:int):
   
4.             mid = int(a**(1/2))
   
5.             for i in range(mid,0,-1):
   
6.                 yield i**2
   
7.         for each in getn(n):
   
8.             if each <= n:
   
9.                 #print('调试',each)
   
10.                 return 1 + solve(n-each)
    
11.         return 0
    
12.     def pb(n):
    
13.         res = 0
    
14.         while n:
    
15.             if str(n**0.5)[-2:] == '.0':
    
16.                 return res + 1
    
17.             else:
    
18.                 n -= int(int(n/2)**0.5)**2
    
19.                 res += 1
    
20.             #print('调试',n)
    
21.         return res
    
22.     return min(pa(n),pb(n))
    
23. if __name__ == '__main__':
    
24.     print('示例1 输出：',solve(12))
    
25.     print('示例2 输出：',solve(13))
    

复制代码

但果然还是不对。
正经来解：

1. def solve(n:'int > 0')->int:
   
2.     def pa(n):
   
3.         def getn(a:int):
   
4.             mid = int(a**(1/2))
   
5.             for i in range(mid,0,-1):
   
6.                 yield i**2
   
7.         res = 0
   
8.         for each in getn(n):
   
9.             if each <= n:
   
10.                 #print('调试1',each,n)
    
11.                 get = 1+pa(n-each)
    
12.                 if res:
    
13.                     if get < res:
    
14.                         res = get
    
15.                     else:
    
16.                         return res
    
17.                 else:
    
18.                     res = get
    
19.         return res
    
20.     return pa(n)
    
21. if __name__ == '__main__':
    
22.    
    
23.     print('示例1 输出：',solve(12))
    
24.     print('示例2 输出：',solve(13))
    
25.    

复制代码

塔利班

阴阳神万物主 发表于 2020-1-11 00:38
玄学求解。
两个有缺陷的放一起，结果就对了？

应该不对，，13*4结果就变4了

Croper

我记得有一个定理就是任意正整数可以写成不超过4个完全平方数的和。。

不过我们不采用这一结论，正好直接写程序来验证这一点

1. def func303(n:int)->int:
   
2.     stk=[]
   
3.     ret=-1
   
4.     while True:
   
5.         stk.append(int(n**0.5))
   
6.         n-=stk[-1]**2
   
7.         if (n==0):
   
8.             ret=len(stk)
   
9.             if (ret<=2):
   
10.                 return ret
    
11.         if (ret!=-1 and len(stk)>=ret):
    
12.             if (n==0):
    
13.                 n+=stk.pop()**2
    
14.             n+=stk.pop()**2
    
15.             while (len(stk)>0 and stk[-1]**2*(ret-len(stk))<=n):
    
16.                 if (len(stk)==1):
    
17.                     return ret
    
18.                 n+=stk.pop()**2
    
19.             stk[-1]-=1
    
20.             n+=2*stk[-1]+1

复制代码

采用回溯法，思路：
采用一个变量ret来记录当前的最小值
采用一个数组stk来记录当前拆分方式

回溯条件：
1、当前stk已经能组成完全平方数（并记录ret）
2、如果stk的剩余所有位数（以ret为限）都是当前stk的最后一位时，其表示的n值也也不能超过时（包含当前stk的长度已经不小于ret且不能组成完全平方数）

得出结论的条件：
1、ret不大于2（已经没有回溯的意义了）
2、由于是从大到小遍历，当stk的首位即使乘以ret也不能大于n时

NAMELESSONE

1. def solve(num:int,figure:int):
   
2.         sqrt=num**0.5
   
3.         if int(sqrt)==sqrt:
   
4.                 return 1
   
5.         else:
   
6.                 num-=(int(sqrt)-figure)**2
   
7.                 return 1+solve(num,0)
   
8. while True:
   
9.         count=0
   
10.         data=int(input('请输入:'))
    
11.         while data!=0:
    
12.                 one=solve(data,0)
    
13.                 two=solve(data,1)
    
14.                 if one>two:
    
15.                         data-=(int(data**0.5)-1)**2
    
16.                         count+=1
    
17.                 elif one==two:
    
18.                         count+=one
    
19.                         break
    
20.                 else :
    
21.                         data-=(int(data**0.5))**2
    
22.                         count+=1
    
23.         print(count)
    

复制代码

阴阳神万物主

塔利班 发表于 2020-1-11 09:53
应该不对，，13*4结果就变4了

哦，谢谢，应该是能做到 6**2+4**2 的。

TJBEST

原来想用迭代法，发现不太现实，太耗时，换了个方法

1. import itertools
   
2. def fun303(n):
   
3.     if n == 1:
   
4.         return 1
   
5.     def isOK(n,index):
   
6.         for eachCouple in itertools.combinations_with_replacement(powList, index):
   
7.             if sum(eachCouple) == n:
   
8.                 return True
   
9.         return False
   
10.     powList = []
    
11.     for i in range(1,(n//2) + 1):
    
12.         if i * i > n:
    
13.             break
    
14.         powList.append(i * i)
    
15.     if n in powList:
    
16.         return 1
    
17.     else:
    
18.         index = 2
    
19.         while index <=  n:
    
20.             if isOK(n,index):
    
21.                 return index
    
22.             index = index + 1

复制代码

TJBEST

Croper 发表于 2020-1-11 10:13
我记得有一个定理就是任意正整数可以写成不超过4个完全平方数的和。。

不过我们不采用这一结论，正好直 ...

是4个，我测试最多4个，31就是4个

Stubborn

对结果的要求，是尽可能的少吗？

TJBEST

Stubborn 发表于 2020-1-11 16:28
对结果的要求，是尽可能的少吗？

是，题目的意思就是 若n个正整数 其平方和 为给定值 则找到n的最小值

Stubborn

TJBEST 发表于 2020-1-11 16:33
是，题目的意思就是 若n个正整数 其平方和 为给定值 则找到n的最小值

1. def fun303(number:int):
   
2.     """"""
   
3.     import math
   
4.     k = int(math.sqrt(number))
   
5.     if k*k == number:return 1
   
6.     result = float("inf")
   
7.     while k > math.sqrt(number//2)-1 :
   
8.         l = 1 + fun303(number=number - k*k)
   
9.         if result > l: result = l
   
10.         k -= 1
    
11.     return result

复制代码

kinkon

直接这样子行不行？

1. def fun303(n:int)->int:
   
2.     res = []
   
3.     while n != 0:
   
4.         res.append(int(n**0.5))
   
5.         #print("调试列表： ",[x**2 for x in res])        
   
6.         n -= res[-1]**2
   
7.         if (n == 0):
   
8.             return len(res)
   
9. 
   
10. print(fun303(98))

复制代码

zltzlt

阴阳神万物主 发表于 2020-1-11 00:38
玄学求解：

但果然还是不对。

解答错误

输入：8400
输出：5
期望答案：3

zltzlt

NAMELESSONE 发表于 2020-1-11 12:20

解答错误

输入：8400
输出：5
期望答案：3

zltzlt

Stubborn 发表于 2020-1-11 16:46

输入超过 8400 的数会超时

zltzlt

kinkon 发表于 2020-1-11 16:58
直接这样子行不行？

当然行不通。。

Stubborn

zltzlt 发表于 2020-1-11 17:32
输入超过 8400 的数会超时

1. def fun303(number:int):
   
2.     """四平方和定理，任何一个正整数都可以表示成不超过四个整数的平方之和"""
   
3.     import math
   
4.     while number % 4 == 0:
   
5.         number /= 4
   
6.     if number % 8 == 7 : return 4
   
7.     l = int(math.sqrt(number)) + 1
   
8.     for a in range(l):
   
9.         b = int(math.sqrt(number - a*a))
   
10.         if a*a + b*b == number:
    
11.             if a == 0:return 1
    
12.             return 2
    
13.     return 3

复制代码

塔利班

Stubborn 发表于 2020-1-11 18:05

这个似曾相识

Stubborn

塔利班 发表于 2020-1-11 19:10
这个似曾相识