02.找一個最小的自然數(shù)x，使它等于不同的兩對自然數(shù)的三次冪之和，即使得：
x=a*a*a+b*b*b=c*c*c+d*d*d
其中a,b,c,d都是自然數(shù)，且有a!=c和a!=d
解：
問題要找的解是兩個自然數(shù)對，以自然數(shù)對為解的候選者，如程序能這樣枚舉解的候選者，使枚舉出來的自然數(shù)對的三次冪之和構成一個不減的序列，則當發(fā)現(xiàn)兩個自然數(shù)對的三次冪之和相等時，這兩對自然數(shù)就是問題的解。將這種思想寫成抽象算法描述如下：
{
i1=1;j1=1;x=i1*i1*i1+j1*j1*j1;
do
{
i0=i1;j0=j1;min=x; /*保存上一個解的候選者*/
確定下一對自然數(shù)i1,j1;
x=i1*i1*i1+j1*j1*j1;
}while(x!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3\n",x,i0,j0,i1,j1);
}
問題已轉化成如何按上述要求逐一自然數(shù)對。
為了尋找產生候選者規(guī)則的線索，將問題簡化為找一個最小的自然數(shù)x，使它等于不同的兩對自然數(shù)的平方之和。下面列出部分兩個自然數(shù)的平方之和的數(shù)表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是兩對自然 平方和的最小者。要尋找的產生候選者的規(guī)則就是要尋找一個方法，使枚舉產生的候選者(自然數(shù)對)的平方和構成以下數(shù)列：
2 5 8 10 13 ... 45 50 50
仔細考查表中s[i][j]與i和j，不難發(fā)現(xiàn)有以下性質：
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]
因問題將自然數(shù)對(i,j)和(j,i)視為同一個自然數(shù)對，所以只需考慮i>=j的情況，性質1)說明對于表中的每一行，應從左到右逐個考查，且沒有必要保存一整行的候選者供選擇，一行只要保存一個已足夠。當某行的當前候選者已被確認不是解時，則可生成該行的下一個候選者，等候被考慮。
由以上分析，可用下面的兩個一維數(shù)組表示當前正在考慮的狀態(tài)：
int s[?],j[?];
其中？意指數(shù)組的大小還未確定。數(shù)組j[]的成份j[k]表示s表中的第k行當前待考慮的列號。所以，s[]和j[]有關系：
s[k]=k*k*k+j[k]*j[k]*j[k]
將以上分析結果反映到找解方法中，原先的找解算法可改寫成如下形式：
{
for(k=1;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^3\n",min,i0,j0,i,j[i]);
}
按上述算法編寫程序還有兩處不足，需進一步確定或調整：一是為個數(shù)不確定的數(shù)組s[]和j[]送初值；另一個是個數(shù)不確定的候選者中選正式候選者。由性持，由性質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]的初值。
再次把上述思想反映到算法中，找解算法又可改寫成如下形式：
算法--找一個最小的自然數(shù)x，使它等于不同的兩對自然 的三次冪之和
{
il=1;ih=1; /*首先只局限于第一行*/
j[1]=1;s[1]=2;i=1;
d
{
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] }while(s[i]!=min(;
printf("%d=%d^3+%d^3=%d^3+%d^3\n",min,i0,j0,i,j[i]);
}
以上算法可作為最后的算法，下面的程序作了必要的優(yōu)化，避免反復計算一個整數(shù)的三次冪。引入數(shù)組p[]，其中p[i]存儲i*i*i。
x=a*a*a+b*b*b=c*c*c+d*d*d
其中a,b,c,d都是自然數(shù)，且有a!=c和a!=d
解：
問題要找的解是兩個自然數(shù)對，以自然數(shù)對為解的候選者，如程序能這樣枚舉解的候選者，使枚舉出來的自然數(shù)對的三次冪之和構成一個不減的序列，則當發(fā)現(xiàn)兩個自然數(shù)對的三次冪之和相等時，這兩對自然數(shù)就是問題的解。將這種思想寫成抽象算法描述如下：
{
i1=1;j1=1;x=i1*i1*i1+j1*j1*j1;
do
{
i0=i1;j0=j1;min=x; /*保存上一個解的候選者*/
確定下一對自然數(shù)i1,j1;
x=i1*i1*i1+j1*j1*j1;
}while(x!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3\n",x,i0,j0,i1,j1);
}
問題已轉化成如何按上述要求逐一自然數(shù)對。
為了尋找產生候選者規(guī)則的線索，將問題簡化為找一個最小的自然數(shù)x，使它等于不同的兩對自然數(shù)的平方之和。下面列出部分兩個自然數(shù)的平方之和的數(shù)表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是兩對自然 平方和的最小者。要尋找的產生候選者的規(guī)則就是要尋找一個方法，使枚舉產生的候選者(自然數(shù)對)的平方和構成以下數(shù)列：
2 5 8 10 13 ... 45 50 50
仔細考查表中s[i][j]與i和j，不難發(fā)現(xiàn)有以下性質：
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]
因問題將自然數(shù)對(i,j)和(j,i)視為同一個自然數(shù)對，所以只需考慮i>=j的情況，性質1)說明對于表中的每一行，應從左到右逐個考查，且沒有必要保存一整行的候選者供選擇，一行只要保存一個已足夠。當某行的當前候選者已被確認不是解時，則可生成該行的下一個候選者，等候被考慮。
由以上分析，可用下面的兩個一維數(shù)組表示當前正在考慮的狀態(tài)：
int s[?],j[?];
其中？意指數(shù)組的大小還未確定。數(shù)組j[]的成份j[k]表示s表中的第k行當前待考慮的列號。所以，s[]和j[]有關系：
s[k]=k*k*k+j[k]*j[k]*j[k]
將以上分析結果反映到找解方法中，原先的找解算法可改寫成如下形式：
{
for(k=1;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^3\n",min,i0,j0,i,j[i]);
}
按上述算法編寫程序還有兩處不足，需進一步確定或調整：一是為個數(shù)不確定的數(shù)組s[]和j[]送初值；另一個是個數(shù)不確定的候選者中選正式候選者。由性持，由性質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]的初值。
再次把上述思想反映到算法中，找解算法又可改寫成如下形式：
算法--找一個最小的自然數(shù)x，使它等于不同的兩對自然 的三次冪之和
{
il=1;ih=1; /*首先只局限于第一行*/
j[1]=1;s[1]=2;i=1;
d
{
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] }while(s[i]!=min(;
printf("%d=%d^3+%d^3=%d^3+%d^3\n",min,i0,j0,i,j[i]);
}
以上算法可作為最后的算法，下面的程序作了必要的優(yōu)化，避免反復計算一個整數(shù)的三次冪。引入數(shù)組p[]，其中p[i]存儲i*i*i。