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

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

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；其它情况，当前行的下一列将会被考虑，为该行调整当前列。在调整当前平面的行的下界和上界时，应不能超过当前平面号。为在三角棱体的当前有效平面内找最小值的候选者，先假定最上平面的最小行的当前列为下一个候选者，然后自最上平面至最下平面，每个平面自最小行至最大行，寻找最小值所在平面号、行号和列号。