计算机等级考试C语言程序设计例解(02)

02.求最小的自然数X，使其等于两对不同自然数的三次方之和，也就是说:
X = A * A+B * B * B = C * C * C+D * D * D
其中A，B，C，D都是自然数，[ =c，A！=d
解:
问题的解是两个自然数对，自然数对是解的候选。如果程序能够枚举出解的候选项，使得枚举出的自然数对的三次幂之和形成一个不减序列，那么当发现两个自然数对的三次幂之和相等时，这两个自然数就是问题的解。把这个想法写成抽象算法，描述如下:
{
i1 = 1；J1 = 1；x = i1 * i1 * i1+J1 * J1 * J1；
do
{
i0 = i1；j0 = j1min = 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。生成候选项的规则是想办法使枚举生成的候选项(自然数对)的平方和形成如下序列:
2 5 8 10 13...45 50 50
仔细考察表中的s[i][j]和I、J，不难发现以下性质:
1) S .当j>k
2) s[i][j]>s[k][j]，对于所有J，当I > k
3)s[I][J]= s[J][I]
将是一个自然数由于问题当一行的当前候选已被确认不是
从上面的分析来看，所考虑的当前状态可以用下面两个一维数组来表示:
int s[？]，j[？];
其中？意味着数组的大小还没有确定。数组j[]的分量j[k]表示S表的第k行中要考虑的当前列号。因此，s[]与j[]:s[K]= K * K * K+j[K]* j[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^3\n",min,i0,j0,i,j[i])；
}
按照上述算法编程还有两个不足之处，需要进一步确定或调整:一是初始值发送给不确定数的数组s[]和j[]；另一种是从数量不确定的候选人中选择一个正式候选人。本质上，通过属性2)，引入了当前考虑的行、行ih和最小行il的范围，其中ih是指j[k]为1的最小下标k。由于目前无法选取ih行后的最小值s[i]，因此可将初始值和最小元素选取限定为K将上述思想再次反映到算法中，求解算法可改写为以下形式:
算法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++；/* Adjust 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 if(s[k] }while(s[i]！= min(；
printf("%d=%d^3+%d^3=%d^3+%d^3\n",min,i0,j0,i,j[i])；
}
以上算法可作为最终算法，以下程序已优化，避免重复计算整数的三次方。引入数组p[]，其中p[i]存储i * i * i.