蓝桥杯：四方定理

 1 /*
 2    本题满分： 9分
 3 
 4   填空1: (3分)
 5   n==0
 6   或者：0==n
 7 
 8   填空2: (6分)
 9   f(n-i*i, a, idx+1)
10   或者：
11   f(n-i*i, a, idx+1) > 0
12   f(n-i*i, a, idx+1) == 1
13  
14 对每个不同的答案要细心，首先带入程序，看结果是否正确
15 再换数据测试
16 
17 */
18 
19 
20 
21 #include "stdafx.h"
22 #include "math.h"
23 
24 // 四方定理：所有自然数至多只要用四个数的平方和就可以表示。
25 
26 int f(int n, int a[], int idx)
27 {
28     if(n==0) return 1;// 填空1
29     if(idx==4)  return 0;
30 
31     for(int i=(int)sqrt(n); i>=1; i--)
32     {
33         a[idx] = i;
34 
35         if(f(n-i*i, a, idx+1))// 填空2
36             return 1;
37     }
38 
39     return 0;
40 }
41 
42 int main(int argc, char* argv[])
43 {
44     for(;;)
45     {
46         int number;
47         printf("输入整数(1~10亿)：");
48         scanf("%d",&number);
49         
50         int a[] = {0,0,0,0};
51 
52         int r = f(number, a, 0);
53 
54         printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]);
55         
56     }
57 
58     return 0;
59 }