最近看电脑报有一个叫作《编程擂台》的栏目，要求证明四方定理，仔细一看题目不觉得难，就尝试了一下，在选修课上兴冲冲的（自以为是的）把算法想到了，回来一试，在验证1000的时候出现了问题，次数成了5次，也就是说1000 = 31 * 31 + 6 * 6 + 1 * 1 + 1 * 1 + 1* 1；这显然不对，如果换成500的话就显示2，又是对的，500被分解成22 * 22 + 4 * 4，于是我明白了还是算法出问题了。
今天上网搜索了一下四方定理，发现解法真是极其简单，用的就是穷举搜索，除去效率的问题（我本身用的时递归，效率也不高）。看来有的时候想问题真是会把问题想得过于复杂了。呵呵：）
我的算法：
#include <iostream>
#include <math.h>
using namespace std;
static short unsigned a = 0;
void Func(int i)
{
int j = sqrt( i );
if (!( i - j * j ))
{
a ++;
}
else
{
Func( i - j * j );
a ++;
}
}
int main()
{
int k = 0;
cin >> k;
Func( k );
cout << a <<endl;
return 0;
}
正确算法：
*问题分析与算法设计
本题是一个定理，我们不去证明它而是编程序验证。
对四个变量采用试探的方法进行计算，满足要求时输出计算结果。
*程序与程序注释
#include<stdio.h>
#include<stdlib.h>
void main()
{
int number,i,j,k,l;
printf("Please enter a number=");
scanf("%d",&number); /*输入整数*/
for(i=1;i<number/2;i++) /*试探法。试探i,j,k,k的不同值*/
for(j=0;j<=i;j++)
for(k=0;k<=j;k++)
for(l=0;l<=k;l++)
if(number==i*i+j*j+k*k+l*l) /*若满足定理要求则输出结果*/
{
printf(" %d=%d*%d+%d*%d+%d*%d+%d*%d\n",number,i,i,j,j,k,k,l,l);
exit(0);
}
}
*运行结果
1) Please enter a number = 110
110=7*7+6*6+4*4+3*3
2) Please enter a number = 211
211=8*8+7*7+7*7+7*7
3) Please enter a number = 99
99=7*7+5*5+4*4+3*3