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