问个弱弱的算法问题...
题目是求证任何一个自然数都可由4个数的平方和来表示程序如下：
#include<stdio.h>
#include<stdlib.h>
void check(int);
int main(void)
{
int n;
scanf("%d",&n);
check(n);
getch();
return 0;
}
void check(int i)
{
int aa;
int t;
t = i;
for(aa=sqrt(t);aa>=sqrt(t/2);aa--)
{
t -= aa * aa;
for(aa=sqrt(t);aa>=sqrt(t)/2;aa--)
{
t -= aa * aa;
for(aa=sqrt(t);aa>=sqrt(t)/2;aa++)
{
t -= aa * aa;
for(aa=sqrt(t);aa>=sqrt(t)/2;aa++)
if(aa*aa+aa*aa+aa*aa+aa*aa==i)
{
printf("%5d %5d %5d %5d",aa,aa,aa,aa);
getch();
exit(0);
}
}
}
}
printf("无解 ！\n");
getch();
}
问题：
1）为什么它循环的最大值为什么可以写成 被判断数的一半再开方(sqrt(t/2))
2) 为什么下面又变成了 (sqrt(t)/2)
3) 为什么上两循环都是 --, 而最后两个循环用++呢？
麻烦大大们解释一下。谢谢了 这个算法，数学问题大于程序问题吧。
我数学不及格。 现在大概理解了，比如用5来分解的话可以分成 5=2^2 + 1^2 + 0^2 + 0^2,所以其实最大值只需要取到，sqrt(5/2)就够了，像五的话，它最大的值只能取到2。但是最后两个循环，我觉得应该改为-- 才对，要不好像会造成死循环。
说了这么多其实不知是不是这样。。。 好恐怖的时间复杂度……
页:
[1]