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+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 .当j>k
2) s[i][j]>s[k][j]，对于所有J，当I > k
3)s[I][J]= s[J][I]
将是一行当前候选已被确认不是时由于问题产生的自然数