解题思路:
四平方和问题最简单的解题方式,最开始想到的估计都是暴力法,这里笔者也是先想到这个,用两种不同的语言都试了一下,c++三重循环暴力能过,但python会超时间一个样例,参考代码如下:
a=int(input())#暴力法求四平方和,超时
i=0
j=0
k=0
flag=1
while i*i<=a and flag:
j=i
while i*i+j*j<=a and flag:
k=j
while i*i+j*j+k*k<=a and flag:
h=int(a-i**2-j**2-k**2)
b=int(h**0.5)
if (b)**2==h:
print(i,j,k,b,sep=" ")
flag=0
break
k+=1
j+=1
i+=1
我们想要完全通过这一题,就要考虑换一个方法,这里我考虑的是二分法,首先遍历出四个平方数中的后两个,将其存储在一个列表record中,这里主要的一个思路就是用空间换时间,毕竟现在空间存储技术越来越发达,对于空间复杂度的要求越来越低,这里完全可以采用这种方式牺牲空间复杂度来换取时间复杂度。存储完后两个平方数之后,再进行前两个平方数的遍历(a-i**2-j**2),然后检索其是否能在咱们之前存储的对应数值里找到,如果能的话,则为我们要找的对应平方数,这里检索的过程利用二分求解:
a=int(input())
record=[]
for i in range(int(a**0.5)+1):
for j in range(i,int((a-i*i)**0.5)+1):
record.append((i*i+j*j,i,j))
record.sort()#别忘了二分需要升序排序
for i in range(int(a**0.5)+1):
for j in range(i, int((a - i * i) ** 0.5) + 1):
t=a-i*i-j*j
l=0
r=len(record)-1
while l<r:#检索record中是否有对应的前两项平方和
mid=(l+r)//2
if record[mid][0]>=t:
r=mid
else:
l=mid+1
if record[l][0]==t:#检索到的话就输出,退出程序,检索到的第一个即为字典序最小的,为节省时间直接exit
print(i,j,record[l][1],record[l][2],sep=" ")
exit()
这里有一个需要严格注意的细节,就是二分的时候尽量采用向左逼近的二分方法,避免mid+1,不然的话容易时间复杂度过高,虽然这个理论上没什么根据,但是根据刷题的经验来看是这样的
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:664 |
printf基础练习2 (C语言代码)浏览:740 |
A+B for Input-Output Practice (II) (C语言代码)浏览:989 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:738 |
DNA (C语言描述,蓝桥杯)浏览:1553 |
简单的a+b (C语言代码)浏览:414 |
printf基础练习2 (C语言代码)浏览:503 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:601 |
求圆的面积 (C++代码)浮点数有误差!!!浏览:671 |
简单的a+b (C语言代码)浏览:430 |