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

zltzlt · 发表于 2019-10-13 13:07:48

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

今天的题目：

给定正整数 n，找到能组成 n 的完全平方数（比如 1, 4, 9, 16, ...）。你需要让组成 n 的完全平方数的个数最少。

难度：★★★☆☆
注意：为了提高鱼油们的积极性，前 10 位答对的鱼油才有奖哦 ~

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

XiaoPaiShen

2019-10-14 06:50:15

class SquareFactor:
def get_factor(self, number):
factor = 1
while number % 4 == 0:
number /= 4
factor *= 4
return int(number), factor
def get_maxSqrtRoot(self, number):
root = math.sqrt(number)
return int(root)
def num_squares(self, number):
if not number:
return 0
number, factor = self.get_factor(number)
queue = list()
queue.append([number, 0])
visited = [number == i for i in range(number + 1)]
while any(queue):
num, step = queue.pop(0)
i = 1
remain = num - i*i
while remain >= 0:
if not remain:
return step + 1
if not visited[remain]:
queue.append([remain, step+1])
visited[remain] = True
i += 1
remain = num - i*i
if __name__ == '__main__':
sf = SquareFactor()
print(sf.num_squares(13))

复制代码

跳转到最佳答案楼层

MyWifeDF41 · 发表于 2019-10-13 15:38:17

本帖最后由 MyWifeDF41 于 2019-10-13 15:43 编辑

'''
把12分别拆成1、11；4、8；9、3；然后再拆11、8、3。
11最少是9 1 1，3 个数，因此12可拆成四个数；
8最少是4 4，12拆成三个数
3最少是1 1 1，12拆成四个数
因此输出3
'''
def numSqu(n):
list = [float('inf') for i in range(n+1)] #生成一个长度为n的list，每个元素表示平方的个数，初始为正无穷
list[0] = 0
for i in range(n+1): #计算组成i的完全平方数最少的个数
j = 1
while j**2 <= i :
list[i] = min(list[i],1 + list[i-j**2]) #把i分解为j**2+1, list[j**2] == 1, 比较哪种方法最小
j += 1
return list[i]

复制代码

如果算个大点的数，我感觉内存会爆。。。

danteer · 发表于 2019-10-13 16:46:43

本帖最后由 danteer 于 2019-10-13 16:49 编辑

def func1(n):
list1 = []
list2 = []
count = 0
for i in range(int(n**0.5) + 1):
list1.append(i)
for i in list1:
for j in list1:
for k in list1:
list2.append([i**2,i**2 + j**2,i**2 + j**2 + k**2])
for each in list2:
if each[0] == n:
count = 1
break
if count != 0:
return count
for each in list2:
if each[1] == n:
count = 2
break
if count != 0:
return count
for each in list2:
if each[2] == n:
count = 3
break
if count != 0:
return count
else:
count = 4
return count

复制代码

四平方和定理说明每个正整数均可表示为4个整数的平方和。它是费马多边形数定理和华林问题的特例。
大概因为这个定理的关系可以省点劲？
反正我知道我这个程序算一个大的数字肯定超时，但是就当抛砖引玉了。

战场原 · 发表于 2019-10-13 22:08:42

def solution(n: int) -> int:
      mylist = [n]
      step = 0

      while True:
         step += 1
         tmp = set()
         while mylist:
            n = mylist.pop()
            for i in range(1, int(n**0.5)+1):
                  cha = n-i**2
                  if cha == 0:
                     return step
                  else:
                     tmp.add(cha)
         mylist = list(tmp)

XiaoPaiShen · 发表于 2019-10-14 06:50:15

这个最佳答案由 XiaoPaiShen 给出，感谢 XiaoPaiShen 的回答。

单击隐藏图章

class SquareFactor:
def get_factor(self, number):
factor = 1
while number % 4 == 0:
number /= 4
factor *= 4
return int(number), factor
def get_maxSqrtRoot(self, number):
root = math.sqrt(number)
return int(root)
def num_squares(self, number):
if not number:
return 0
number, factor = self.get_factor(number)
queue = list()
queue.append([number, 0])
visited = [number == i for i in range(number + 1)]
while any(queue):
num, step = queue.pop(0)
i = 1
remain = num - i*i
while remain >= 0:
if not remain:
return step + 1
if not visited[remain]:
queue.append([remain, step+1])
visited[remain] = True
i += 1
remain = num - i*i
if __name__ == '__main__':
sf = SquareFactor()
print(sf.num_squares(13))

复制代码

Hoiste · 发表于 2019-10-14 11:04:13

本帖最后由 Hoiste 于 2019-10-14 11:35 编辑

刚学习Python的新手现在水平有限，只用自己现在知道的一些内容编写了组成任意n的最少完全平方数，解释部分以后有思路再试试吧。。。
n = input('请输入任意正整数：')
n = int(n)
while n <= 0:
print('要求输入的是正整数哦！')
n = input('请输入任意正整数：')
n = int(n)
print('你输入的数字是：'+str(n))

i = 1
k = 0
rest = n
if i ** 2 == rest:
k = k + 1
print('组成n的完全平方数个数为：'+str(k))
else:
while i ** 2 < rest:
      i = i + 1
      if i ** 2 > rest:
         rest = rest - (i - 1) ** 2
         k = k + 1
         i = 1
      if i ** 2 == rest:
         k = k + 1
         print('组成n的完全平方数个数为：'+str(k))
         break

华博文 · 发表于 2019-10-14 11:26:52

本帖最后由华博文于 2019-10-14 18:19 编辑

最大数测试为：12345678901 ，出的还是挺快的，把#去掉有详细信息但是会慢很多~~
自己琢磨瞎写的，跟大佬们学习

import math
zong = list()
def yun(guess , sq_guess , zhan):
re_guess = guess - (sq_guess * sq_guess)
# print(re_guess)
bian = str(math.sqrt(re_guess))
if int(bian[bian.find(".") + 1 : ]) != 0:
zhan.append(sq_guess * sq_guess)
yun(re_guess , int(float(bian)) , zhan)
return zhan
else:
zhan.append(sq_guess * sq_guess)
if re_guess != 0:
zhan.append(re_guess)
return zhan
def eson(guess , zong = zong):
sq_guess = int(math.sqrt(guess))
for each in range(sq_guess , 0 , -1):
zhan = list()
zhan = yun(guess , each , zhan)
zong.append(zhan)
return zong
if __name__ == "__main__":
text = ""
try:
wen = input("请输入一个整数，求出组成它的完全平方组：")
if int(wen) != 0:
#请从此处开始测试,看更详细的答案请把下列【#】全部去掉~~
lis = [each for each in eson(int(wen) , zong)]
lis_len = [len(each) for each in lis]
#dex = [lis[each] for each in range(len(lis)) if len(lis[each]) == min(lis_len)]
print("结果为:{}".format(min(lis_len)) , end="")
#print("\n详细：" , end="")
#for fir in dex:
#text += "\n "
#for sec in range(len(fir) - 1):
#text += str(fir[sec]) + " + "
#text += str(fir[-1])
#print(text)
else:
print("结果为：0")
except (ValueError , TypeError):
print("您输入的数值不可运算~~")

复制代码

Garou · 发表于 2019-10-14 14:01:23

本帖最后由 Garou 于 2019-10-14 16:04 编辑

！！！###注意：该段代码是用python27实现的###！！！
最近在通过python27学习一些东西，wxpython；
这样会是最短的吗，抱有疑惑不敢肯定。。。

inputValue = int(input("请输入一个正整数: "))
tempList = []
value = None
tempValue = inputValue
if value == None:
# 开方并保留一位小数，再将其转化为int
value = int(round(tempValue ** 0.5, 1))
tempValue = tempValue - value ** 2
tempList.append(value)
while True:
if tempValue >= 4:
value = int(round(tempValue ** 0.5, 1))
tempValue = tempValue - value ** 2
tempList.append(value)
print value
print tempValue
elif tempValue >= 1:
a_list = [1] * tempValue
tempList += a_list
tempValue = None
else:
break
print tempList
list = []
for ii in tempList:
aa = ii**2
list.append(aa)
print list
print len(list)

复制代码

756437832 · 发表于 2019-10-14 15:56:09

我这个数大了也爆炸...
而且自己有的地方也理解

list_sum=[]
dict_res={}
temp=input('请输入一个整数：')
def x(each_1,list_n,n,temp):#递归求值
global list_sum
for each_2 in range(0,n+1):
if each_1 + each_2 == n:
if each_2==0:
list_sum.append(each_1)
count=len(list_sum)
if sum(list_sum)==temp:#这里递归到最后有个值是1，不知道怎么去掉，所以加了个if，求指点
dict_res[count]=list_sum
list_sum=[]
continue
elif each_2 in list_n:
list_sum.append(each_2)
count=len(list_sum)
if sum(list_sum)==temp:
dict_res[count]=list_sum
list_sum=[]
continue
else:
list_sum.append(each_1)
n-=each_1
for each_1 in list_n:
return x(each_1,list_n,n,temp)
def sumn(list_n,n,temp):
global count
for each_1 in list_n:
x(each_1,list_n,n,temp)
def fun(temp):
global dict_res
n=temp+1
list_n=[]
num=int(n**0.5)
list_x=[x for x in range(1,num+1)]
for each in list_x:
list_n.append(each**2)
sumn(list_n,n,temp)
#准备输出结果及解释
explain=''
i=1
for each in dict_res[min(dict_res)]:
if i<len(dict_res[min(dict_res)]):
explain=explain+str(each)+'+'
i+=1
else:
explain=explain+str(each)
explain=str(sum(dict_res[min(dict_res)]))+'='+explain
print('输出：%d\n解释:%s'%(min(dict_res),explain))
dict_res={}#初始化,为下轮做准备
fun(int(temp))

复制代码

不了..

__mrsq__ · 发表于 2019-10-14 16:07:59

本帖最后由 __mrsq__ 于 2019-10-14 16:12 编辑

def fun256(num):
rt = int(num**0.5)
set0 = {num}
set1 = {n**2 for n in range(1,rt+1)}
set2 = {num -n**2 for n in range(1,rt+1)}
set3 = {num - m**2 - n**2 for n in range(1,rt+1) for m in range(1,rt+1)}
set4 = {num - m**2 - n**2 -l**2 for n in range(1,rt+1) for m in range(1,rt+1) for l in range(1,rt+1)}
if not(set1.isdisjoint(set0)):
return 1
elif not(set1.isdisjoint(set2)):
return 2
elif not(set1.isdisjoint(set3)):
return 3
else:
return 4

复制代码

emm也利用了四平和定理，总感觉有点作弊的嫌疑

zltzlt · 发表于 2019-10-14 20:19:32

MyWifeDF41 发表于 2019-10-13 15:38
如果算个大点的数，我感觉内存会爆。。。

输入 4128 超时

zltzlt · 发表于 2019-10-14 20:22:30

danteer 发表于 2019-10-13 16:46
四平方和定理说明每个正整数均可表示为4个整数的平方和。它是费马多边形数定理和华林问题的特例。
大概 ...

输入 437 超时

zltzlt · 发表于 2019-10-14 20:23:10

战场原发表于 2019-10-13 22:08
def solution(n: int) -> int:
mylist = [n]
step = 0

恭喜通过！

执行用时：612 ms

zltzlt · 发表于 2019-10-14 20:24:59

XiaoPaiShen 发表于 2019-10-14 06:50

恭喜通过！

执行用时：216 ms

zltzlt · 发表于 2019-10-14 20:27:55

Hoiste 发表于 2019-10-14 11:04
刚学习Python的新手现在水平有限，只用自己现在知道的一些内容编写了组成任意n的最少完全平方数，解释部分 ...

虽然解答错误，但是代码比较规范！

zltzlt · 发表于 2019-10-14 20:30:23

华博文发表于 2019-10-14 11:26
最大数测试为：12345678901 ，出的还是挺快的，把#去掉有详细信息但是会慢很多~~
自己琢磨瞎 ...

解答错误

输入：48
输出：4
预期结果：3

zltzlt · 发表于 2019-10-14 20:33:02

Garou 发表于 2019-10-14 14:01
！！！###注意：该段代码是用python27实现的###！！！
最近在通过python27学习一些东西，wxpython；
这样 ...

输入 12 出错

zltzlt · 发表于 2019-10-14 20:36:14

756437832 发表于 2019-10-14 15:56
我这个数大了也爆炸...
而且自己有的地方也理解不了..

解答错误。

zltzlt · 发表于 2019-10-14 20:37:07

__mrsq__ 发表于 2019-10-14 16:07
emm也利用了四平和定理，总感觉有点作弊的嫌疑

输入 7691 超时

克里斯保罗 · 发表于 2019-10-15 13:12:05

XiaoPaiShen 发表于 2019-10-14 06:50

看不太懂，可以解释一下吗

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分