四方定理

四方定理

数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。
我们可以通过计算机验证其在有限范围的正确性。

对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 1 #include<stdio.h>
 2 #include<math.h>
 3 int f(int n, int a[], int idx)
 4 {
 5  if (n==0) return 1;  // 填空1  if() return 1;
 6  if (idx == 4)  return 0;
 7  for (int i = (int)sqrt(n); i >= 1; i--)
 8  {
 9   a[idx] = i;
10   if (f(n-i*i,a,idx+1))  return 1;  // 填空2    if()  return 1;
11  }
12  return 0;
13 }
14 int main()
15 {
16  for (;;)
17  {
18   int number;
19   printf("输入整数(1~10亿)：");
20   scanf("%d", &number);
21   int a[] = { 0,0,0,0 };
22   int r = f(number, a, 0);
23   printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]);
24  }
25     return 0;
26 }

四方定理可以改为：所有自然数都能用四个数的平方和表示；n=a^2+b^2+c^2+d^2（不足四个数的，其他的数就用零表示）
拿到这题，先看主函数；

for (;;)
for循环里没有结束语句，表示程序一直循环，不从这里跳出；

int number;
printf(“输入整数(1~10亿)：”);
scanf(“%d”, &number);
结合后面的printf语句，说明number表示有限范围所有自然数中的一个；

int a[] = { 0,0,0,0 };
然后他声明了一个数组a，里面的四个数都为0，可以猜测，这个数组是来存储a,b,c,d四个数的；

int r = f(number, a, 0);
最后它int了个r，调用了自定义函数f,并把f的返回值赋给r；在程序最后看r的值就能完成验证；

if (__) return 1;
if (idx == 4) return 0;
整个函数return返回0或1；猜测这是两种状态，成功或失败；

for (int i = (int)sqrt(n); i >= 1; i–)
(int)sqrt(n)强转了一下，把sqrt(n)转换成int；那四个数从i开始找起（i^2<=n），一直找直到1；

a[idx] = i;
把i赋值给数组a；

if (___) return 1;
返回1

整个函数f有四条return语句，相当于f有四个出口结束，因为f中return一旦执行，后面的代码就不会执行，所以f可以理解成四种不同的情况：
1.if (填空1) return 1;

2.if (idx == 4) return 0;

3.for (int i = (int)sqrt(n); i >= 1; i–)
{
a[idx] = i;
if (填空2) return 1;
}

4.for (int i = (int)sqrt(n); i >= 1; i–)
{
a[idx] = i;
}
return 0;

idx == 4的时候，说明不止四个数，所以0表示证明定理是假，1表示真；
1和3都返回1，是能证明定理成立的；所有自然数从零开始，0的话是不能从3得到，所以只能从1得到；
所以填空1这里填n==0；
2和4都返回1，定理不成立；找到的多于四个的数（情况2）；还没找到四个数，就已经没有数找了（情况4）；
填空2中应该用了递归，用n-i^2不断缩小n，idx就加一；
填空二f(n-i*i,a,idx+1);

  • 补充知识
    return的用法
    1.背景介绍
    return表示从被调函数返回到主调函数继续执行，返回时可附带一个返回值，由return后面的参数指定。
    return通常是必要的，因为函数调用的时候计算结果通常是通过返回值带出的。
    如果函数执行不需要返回计算结果，也经常需要返回一个状态码来表示函数执行的顺利与否（-1和0就是最常用的状态码）， 主调函数可以通过返回值判断被调函数的执行情况。
    2.知识剖析
    返回值是必须有的，作用就是把固定不变的。常用的代码封装起来写在类里，每次用到的时候就调用就行了
    如果需要这个共能返回一个值，甚至一个对象 就需要用返回值了就是用return来把把值返回给调用的者
    return 语句会终止函数的执行并返回函数的值。
    比如：
    function a()
    {
    return 10;//这个时候，函数a的值会等于10，并且函数中下面的内容不再执行
    document.write(50);//由于上面已经return了，这条代码不会执行
    }
    至于什么时候会用到，那看你要函数来做什么，你要他返回值就返回咯，不要他返回就不返回咯！
    比如，用函数来做一个加法运算，需要他返回值：
    function a( b, c )
    {
    return b + c;
    }
    那么调用：var abc = a(5, 80);
    这个时候，abc这个变量的值会是85
    如果想直接输出结果，不要返回值那就
    function a( b, c )
    {
    document.write( b + c );
    }
    这个时候调用， var abc = a(5, 80);
    那么页面会输出85，但abc是没有值的;
    也可以说默认函数是没有返回值的。
    通常函数经过一系列处理后需要给外部返回一个值或者对象
    比如：
    function sum(a,b)
    {
    return a+b
    };
    alert(sum(1,2))==>3如果没有return将会弹出undefined3.