C++程序设计例解(02)
02.找一个最小的自然数x，使它等于不同的两对自然数的三次幂之和，即使得：
x=a*a*a+b*b*b=c*c*c+d*d*d
其中a,b,c,d都是自然数，且有a!=c和a!=d
解：
问题要找的解是两个自然数对，以自然数对为解的候选者，如程序能这样枚举解的候选者，使枚举出来的自然数对的三次幂之和构成一个不减的序列，则当发现两个自然数对的三次幂之和相等时，这两对自然数就是问题的解。将这种思想写成抽象算法描述如下：
{
i1=1;j1=1;x=i1*i1*i1+j1*j1*j1;
do
{
i0=i1;j0=j1;min=x; /*保存上一个解的候选者*/
确定下一对自然数i1,j1;
x=i1*i1*i1+j1*j1*j1;
}while(x!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3n",x,i0,j0,i1,j1);
}
问题已转化成如何按上述要求逐一自然数对。
为了寻找产生候选者规则的线索，将问题简化为找一个最小的自然数x，使它等于不同的两对自然数的平方之和。下面列出部分两个自然数的平方之和的数表s[]，其中：
s[i][j]=i*i+j*j
从上面的s[]表查得：
50=1*1+7*7=5*5+5*5
65=1*1+8*8=4*4+7*7
所以50是两对自然 平方和的最小者。要寻找的产生候选者的规则就是要寻找一个方法，使枚举产生的候选者(自然数对)的平方和构成以下数列：
2 5 8 10 13 ... 45 50 50
仔细考查表中s[i][j]与i和j，不难发现有以下性质：
1) s[i][j]>s[i][k],对于所有的i，当j>k
2) s[i][j]>s[k][j],对于所有的j，当i>k
3)s[i][j]=s[j][i]
因问题将自然数对(i,j)和(j,i)视为同一个自然数对，所以只需考虑i>=j的情况，性质1)说明对于表中的每一行，应从左到右逐个考查，且没有必要保存一整行的候选者供选择，一行只要保存一个已足够。当某行的当前候选者已被确认不是解时，则可生成该行的下一个候选者，等候被考虑。
由以上分析，可用下面的两个一维数组表示当前正在考虑的状态：
int s[?],j[?];
其中？意指数组的大小还未确定。数组j[]的成份j[k]表示s表中的第k行当前待考虑的列号。所以，s[]和j[]有关系：
s[k]=k*k*k+j[k]*j[k]*j[k]
将以上分析结果反映到找解方法中，原先的找解算法可改写成如下形式：
{
for(k=1;k<?;k++)
{ /*每行都从第一列一始考查*/
j[k]=1;
s[k]=k*k*k+1;
}
i=1; /*最初候选者在第一行*/
do
{
min=s[i];i0=i;j0=j[i];
为i行设定下一个候选者存入s[i];
在s[]中找最小的候选者为正式候选者，并将找到的位置存于i中；
}while(s[i]!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3n",min,i0,j0,i,j[i]);
}
按上述算法编写程序还有两处不足，需进一步确定或调整：一是为个数不确定的数组s[]和j[]送初值；另一个是个数不确定的候选者中选正式候选者。由性持，由性质2)，引入当前考虑的行的范围，最大行ih和最小行il，其中ih是指有j[k]为1的最小下标k，因为当前还不可能在ih行之后选到最小的s[i]，所以置初值和选最小元可局限于k<=ih的s[k]中进行。另外,当j[i]=i时，因对s表的考查只限于它的左下角，所以对该行的进一步考查应放弃。利用这个事实，程序可引入il表示s表的当前行范围的下界。于是置初值、寻找局限于s表的il 行到 ih行之间。每当j[i]=i时，il增1；每当j[i]=1时,ih增1,并同时设定s[ih]和j[ih]的初值。
再次把上述思想反映到算法中，找解算法又可改写成如下形式：
算法--找一个最小的自然数x，使它等于不同的两对自然 的三次幂之和
{
il=1;ih=1; /*首先只局限于第一行*/
j[1]=1;s[1]=2;i=1;
do
{
min=s[i];i0=i;j0=j[i];
if(j[i]==1)
{ /*调整ih,并为j[ih]与s[ih]设定初值*/
ih++;
j[ih]=1;
s[ih]=ih*ih*ih+1;
}
if(j[i]==i)il++; /*调整il*/
else
{ /*为i行设定下一个待候选者*/
j[i]++;
s[i]=i*i*i+j[i]*j[i]*j[i];
}
/*以下确定新的i，使得s[i]=min(s[il],...s[ih])*/
i=il;
for(k=il+1;k<=ih;k++)
if(s[k]<s[i])i=k;
}while(s[i]!=min(;
printf("%d=%d^3+%d^3=%d^3+%d^3n",min,i0,j0,i,j[i]);
}
以上算法可作为最后的算法，下面的程序作了必要的优化，避免反复计算一个整数的三次幂。引入数组p[]，其中p[i]存储i*i*i。
程序代码如下：
#include<stdio.h>
#define N 50
void main()
{
int i,il,ih,i0,j0,min,k;
int j[N],s{n],p[N];
il=1;ih=1;j[1]=1;
p[1]=1;s[1]=2;i=1;
do
{
min=s[i];i0=i;j0=j[i];
if(j[i]==1)
{
ih++;p[ih]=ih*ih*ih;
j[ih]=1;s[ih]=p[ih]+1;
}
if(j[i]==i) il++;
else{
j[i]++;
s[i]=p[i]+p[j[i>;
}
i=il;
for(k=il+1;k<=ih;k++)
if(s[k]<s[i]) i=k;
}while(s[i]!=min&&ih!=N);
if(s[i]==min)
printf("%d=%d^3+%d^3=%d^3+%d^3n",min,i0,j0,i,j[i]);
else printf("The %d is too small.n",N);
}
程序运行结果如下：
1729=10^3+9^3=12^3+1^3
