python实现计算最少完美平方数给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9 ... )的和等于 n。

python实现计算最少完美平方数给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9 ... )的和等于 n。

目录

​​1、题目描述 ​​

​​2、代码实现​​

​​3、运行结果​​

1、题目描述

给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9 ... )的和等于 n。输入样例①：12 输出样例：3 解释：4+4+4输入样例②：13 输出样例：2 解释：4+9

2、代码实现

"""-*- coding:utf-8 -*- Author：yang-rocQQ:327844461Email：aida_pc@qq.comTime: 2020/12/29 """def fun(n): squares = [] j = 1 while j * j <= n: squares.append(j * j) j += 1 level = 0 queue = [n] while queue: level += 1 temp = [] visited = [False] * (n + 1) for q in queue: for factory in squares: if q - factory == 0: return level if q - factory < 0: break if visited[q - factory]: continue temp.append(q - factory) visited[q - factory] = True queue = temp return levelif __name__ == '__main__': print(fun(12)) print(fun(13))

3、运行结果

32

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。