C 程序设计例解(02)

文章作者 100test 发表时间 2007:03:10 16:54:28
来源 100Test.Com百考试题网

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^3\n",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)说明对于表中的每一行，应从左到右逐个考查，且没有必要保存一整行的候选者供选择，一行只要保存一个已足够。当某行的当前候选者已被确认不是解时，则可生成该行的下一个候选者，等候被考虑。