C程序設計例解(03)

2019-11-17 05:40:46

字體：大中小

來源：轉載

供稿：網友

03. 找一個最小的自然數，使它等于不同的兩組三個自然數的三次冪之和，即找最小的x，使得：
x=a*a*a+b*b*b+c*c*c+d*d*d+e*e*e+f*f*f
其中，a,b,c,d,e,f都是自然數,a<=b<=c<=d<=e<=f; [a,b,c]!=[d,e,f]
解：
利用上一問題的求解思想，上一問題在正方形平面下三角區內找解，本題在正立方體的下三角棱內找解。記i為三角棱體的平面，j為某平面的行，k為某行上的列。當前考察的下三角棱體的范圍由最上平面至最下平面控制；對應每個平面的下三角區域，在每個下三角區域內當前待考查的行可由行的下界和上界控制，每個有效行上的候選列由其當前列來表示。因此有如下解法：
算法---找一個最小的自然數x，使它等于不同的兩組三個自然數的三次冪之和
{
以三角棱體的頂點為最初候選者；
為最初尋找平面設定行的變化范圍和列的初值；
do
{
保存上一個候選者；
if(當前候選者在最下平面)
{
尋找平面范圍的最下平面向下進一層；
為新平面設定行的變化范圍；
}
if(在最上平面最下角點找到候選者)
尋找平面范圍的最上平面向下進一層；
else
{
if(在第一列找到候選者)
{
當前平面的行的變化上增1；
置當前平面的最高行的列為1；
}
if(在對角線上找到候選者)
當前平在的行的變化下界增1；
else
調整當前平面當前行的列號值；
}
在當前最上平面至當前最下平面范圍內尋找最小值的候選者；
}while(兩候選者對應的值不相等);
輸出解；
}
因每個平面有行變化的下界和上界，程序分別用兩個一維數組來存貯；每個平面的每行都有一個當前列，程序用一個二維數組來存貯；為避免反復計算一個整數的三次冪，另引入一個一維數組，對應第i下標位置存貯i*i*i。令當前找到的候選者為i1,j1,k表示在i1平面的第j1行的k1列找到的候選者。因候選者限制在三角棱內，i1,j1,k1滿足條件：
i1>=j1>=k1
當候選者在最下平面時，則最下平面向下進一層，并為新平面設定行的變化范圍和對應列號；當前最上平面的最下角點找到候選者時，最上平面向下進一層；當在第一列找到候選者時，當前平面的行的上界增，并為新的行設定初始列號；當在某行的對角線上找到候選者時，該行不應該再被考慮，當前平面的行的下界增1；其它情況，當前行的下一列將會被考慮，為該行調整當前列。在調整當前平面的行的下界和上界時，應不能超過當前平面號。為在三角棱體的當前有效平面內找最小值的候選者，先假定最上平面的最小行的當前列為下一個候選者，然后自最上平面至最下平面，每個平面自最小行至最大行，尋找最小值所在平面號、行號和列號。

程序代碼如下：
#include<stdio.h>
#define N 100
void main()
{
int i,j,il,ih,i0,j0,k0,i1,j1,k1;
int jl[N],jh[N]; /*第i層平面的行的變化范圍，自jl[i]至jh[i]*/
int k[N][N]; /*第i層平面中，對應行j，當前的列號值為k[i][j]*/
int p[N], min; /*p[i]=i*i*i*/
i1=1;j1=1;k1=1; /*首先只局限下三角棱體的頂點*/
il=1;ih=1; /*預置i的變化范圍初值il<=i<=ih*/
jl[1]=1;jh[1]=1; /*對應i層平面的行的變化范圍*/
k[il][jl[il>=1; /*第i層平面中，對應行的列的初值*/
p[1]=1;
do
{
min=p[i1]+p[j1]+p[k1];
i0=i1;j0=j1;k0=k1;
if(i1==ih) /*當前候選者在ih平面，則ih增1*/
{
ih++;
p[ih]=ih*ih*ih;
/*為ih平面設定j的變化范圍和對應k值*/
jl[ih]=1;jh[ih]=1;k[ih][1]=1;
}
if(i1==il&&j1==il&&k1==il)
il++; /*在il平面最下角點找到候選者，il增1*/
else
{
if(k1==1&&jh[i1]<i1)
{ /*在第一列找到候選者，i1平面的行的上界增1*/
jh[i1]++;
k[i1][jh[i1>=1;
}
if(k1==j1&&jl[i1]<i1)
jl[i1]++; /*在對角線上找到候選者，il平面的行的下界增1*/
else
k[i1][j1]++; /*調整i1平面當前行的列號*/
}
i1=il; /*預定最上平面的最小行的當前列為下一個候選者*/
j1=jl[i1];
k1=k[i1][j1];
for(i=il;i<=ih;i++) /*尋找最小值所在平面號、行號和列號*/
{
for(j=jl[i];j<=jh[i];j++)
if(p[i]+p[j]+p[k[i][j><p[i1]+p[j1]+p[k1])

{
i1=i;j1=j;k1=k[i][j];
}
}
}while(p[i1]+p[j1]+p[k1]!=min&&ih!=N);
if(p[i1]+p[j1]+p[k1]==min)
else printf("The %d is too small./n",N);
}

程序運行結果如下：
251 = 5^3 + 5^3 + 1^3 = 6^3 + 3^3 + 2^3