1．实验题目
1.7【问题描述】
第四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去，就正好可以表示为4个数的平方和。比如：5 = 0^2 + 0^2 + 1^2 + 2^2 7 = 1^2 + 1^2 + 1^2 + 2^2（^符号表示乘方的意思）对于一个给定的正整数，可能存在多种平方和的表示法。 要求你对4个数排序：0 <= a <= b <= c <= d 并对所有的可能表示法按a,b,c,d为联合主键升序排列，最后输出第一个表示法
【输入】 一个正整数N (N<5000000)
【输出】 4个非负整数，按从小到大排序，中间用空格分开
【输入范例1】 5
【输出范例1】0 0 1 2
【输入范例2】773535
【输出范例2】1 1 267 838
2．需求分析
本演示程序用VC++6.0编写，完成一个数经过拉格朗日定理所得结果。
① 输入的形式和输入值的范围：一个正整数N (N<5000000)。在所有输入中，元素的值都是整数
② 输出的形式：4个非负整数，按从小到大排序，中间用空格分开。
③ 程序所能达到的功能：每个正整数都可以表示为至多4个正整数的平方和，找出其4个正整数
④ 测试数据：
【输入范例1】 5
【输出范例1】0 0 1 2
【输入范例2】773535
【输出范例2】1 1 267 838
3．概要设计
1）为了实现上述程序功能，需要定义函数，主函数调用来实现：
int f(int n)
{
int a,b,c,d;
先定义四个形参；
2）本程序包含2个函数：
① 主函数main()
② 求4个正整数函数int f(int n)
各函数间关系如下：
main（） int f(int n)
4．详细设计
#include<stdio.h>
#include<math.h>
int MAX=(int)sqrt(5000000); //利用最大值的开方数，使用sqrt函数
int f(int n)
{
int a,b,c,d;
for(a=0;a<=MAX;a++) //5000000的开方数为MAX，a作为最外层的循环，即0<=a<=b<=c<=d，升序
{if(a*a>n)continue; //满足a*a>n则结束此次循环，跳到下一语句
for(b=a;b<=MAX;b++)
{if(a*a+b*b>n)continue; //满足a*a+b*b>n即结束此次循环
for(c=b;c<=MAX;c++)
{if(a*a+b*b+c*c>n)continue; //满足a*a+b*b+c*c>n即结束此次循环
for(d=c;d<=MAX;d++) //d变化最快
{if(a*a+b*b+c*c+d*d>n)continue; //满足a*a+b*b+c*c+d*d>n即结束此次循环
if(a*a+b*b+c*c+d*d!=n)continue;//判断4个正整数的平方和是否等于n,不等就结束此次循环
printf("%d %d %d %d\n",a,b,c,d);
return 0; //输出满足条件的第一个表示法
}
}
}
}
return 0;
}
void main()
{
int n;
printf("请输入N值:");
scanf("%d/n",&n); //输入一个整数
if(n<0||n>5000000) //根据题目要求的范围
printf("输入的N值不在范围内!\n");
else f(n);
}
5．调试分析
#include<stdio.h>
#include<math.h>
int MAX=(int)sqrt(5000000);
int f(int n)
{
int a,b,c,d;
for(a=0;a<=MAX;a++)
{if(a*a>n)continue;
for(b=a;b<=MAX;b++)
{if(a*a+b*b>n)continue;
for(c=b;c<=MAX;c++)
{if(a*a+b*b+c*c>n)continue;
for(d=c;d<=MAX;d++)
{if(a*a+b*b+c*c+d*d>n)continue;
if(a*a+b*b+c*c+d*d!=n)continue;
printf("%d %d %d %d\n",a,b,c,d);
return 0;
}
}
}
}
return 0;
} //时间复杂度T(n)=O(n^4),空间复杂度S(n)=O(1)
void main()
{
int n;
printf("请输入N值:");
scanf("%d/n",&n);
if(n<0||n>5000000)
printf("输入的N值不在范围内!\n");
else f(n);
}
调试时，先进入main()函数，然后执行输出语句来进行提示，执行输入语句，再根据判断输入的n值来执行相应的语句，要是是1就输出“输入的N值不在范围内!”,要是0即调用f(n)函数。f(n)函数有四重循环，最外层为a的循环，接下来就是b,c,d。实现0 <= a <= b <= c <= d ，再根据判断四个数的平方和是否等于n，不等就结束此次循环，要是相等就输入结果，输出第一个就执行return 0语句，结束输出。
6．使用说明
程序名为1.exe，运行环境为VC++6.0。程序执行后显示
根据提示，在第一行先输入一个正整数N (N<5000000)，点击换行，下一行输出结果。
7．测试结果
1）建立函数：
» 输入：5
输出：0 0 1 2
» 输入：773535
输出：1 1 267 838
» 输入：0
输出：输入的N值不在范围内!