问个弱弱的算法问题...

august

题目是求证任何一个自然数都可由4个数的平方和来表示
程序如下：

2. #include<stdio.h>
3. #include<stdlib.h>
5. void check(int);
7. int main(void)
8. {
9.     int n;
10.    
11.    
12.     scanf("%d",&n);
13.     check(n);
14.    
15.     getch();
16.     return 0;
17. }
18. void check(int i)
19. {
20.     int aa[4];
21.     int t;
22.    
23.     t = i;
24.     for(aa[0]=sqrt(t);aa[0]>=sqrt(t/2);aa[0]--)
25.     {
26.         t -= aa[0] * aa[0];
27.         for(aa[1]=sqrt(t);aa[1]>=sqrt(t)/2;aa[1]--)
28.         {
29.             t -= aa[1] * aa[1];
30.             for(aa[2]=sqrt(t);aa[2]>=sqrt(t)/2;aa[2]++)
31.             {
32.                 t -= aa[2] * aa[2];
33.                 for(aa[3]=sqrt(t);aa[3]>=sqrt(t)/2;aa[3]++)
34.                     if(aa[0]*aa[0]+aa[1]*aa[1]+aa[2]*aa[2]+aa[3]*aa[3]==i)
35.                     {
36.                         printf("%5d %5d %5d %5d",aa[0],aa[1],aa[2],aa[3]);
37.                         getch();
38.                         exit(0);
39.                     }
40.             }
41.         }
42.     }
43.     printf("无解 ！\n");
44.     getch();
45. }

复制代码

问题：
1）为什么它循环的最大值为什么可以写成 被判断数的一半再开方(sqrt(t/2))
2) 为什么下面又变成了 (sqrt(t)/2)
3) 为什么上两循环都是 --, 而最后两个循环用++呢？

麻烦大大们解释一下。谢谢了

shawind

这个算法，数学问题大于程序问题吧。
我数学不及格。

august

现在大概理解了，比如用5来分解的话可以分成 5=2^2 + 1^2 + 0^2 + 0^2,所以其实最大值只需要取到，sqrt(5/2)就够了，像五的话，它最大的值只能取到2。但是最后两个循环，我觉得应该改为-- 才对，要不好像会造成死循环。
说了这么多其实不知是不是这样。。。

yelengye

好恐怖的时间复杂度……