-
-
[原创]3.LeetCode刷题-完全平方数
-
发表于:
2022-2-6 10:28
4977
-
完全平方数有这样的特性：如果一个正整数a是某一个整数b的平方，那么这个正整数a叫做完全平方数，零也可称为完全平方数。那么： 给定正整数n，找到若干个完全平方数使得它们的和等于n。你需要确定组成和的完全平方数的最少的个数。例如：
对于正整数13，其可以拆解为13 = 4 + 9，则最少个数为2。
对于正整数12，其可以拆解为 12 = 4 + 4 + 4，则最少个数为3。
四平方数和定理又称拉格朗日四平方数和定理，由拉格朗日最终解决，四平方数和定理可以证明：任何正整数均可表示为四个整数的平方和(其中允许有整数为0)。
如果一个数n只能使用4个非零的完全平方数的和表示，则这个数n一定满足4a(8b+7)
1、先假设组成这个数n的完全平方数的个数最少为4，则数n必定满足n = 4a(8b+7)，首先对这个等式进行检查，如果检查通过，则最终答案为4。否则继续算法。
2、假设假设组成这个数n的完全平方数的个数最少为1，则数n可以表示为某个正整数的平方，遍历查找。如果找不到则继续算法。
3、假设假设组成这个数n的完全平方数的个数最少为2，使用循环嵌套嵌套进行遍历查找，找不到则继续算法。
4、算法执行到此，则最终答案为3。
def yyds(n):
num=n
while num % 4 ==0:
num = num / 4
if num % 8 ==7:
return 4
for i in range(1,n+1):
if i*i ==n:
return 1
for i in range(1,n+1):
for j in range(1,n+1):
if i * i+j*j==n:
return 2
return 3
print(yyds(12))
def yyds(n):
num=n
while num % 4 ==0:
num = num / 4
if num % 8 ==7:
return 4
for i in range(1,n+1):
if i*i ==n:
return 1
for i in range(1,n+1):
for j in range(1,n+1):
if i * i+j*j==n:
return 2
return 3
print(yyds(12))
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
