• 当前位置:首页>>C++语言>>C++试题库>>C程序设计例解(03)
  • C程序设计例解(03)

  • 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)
    printf("%4d=%2d^3+%d^3+%d^3=%2d^3+%d^3+%d^3\n",min,i0,j0,k0,i1,j1,k1);
    else printf("The %d is too small.\n",N);
    }

    程序运行结果如下:
    251 = 5^3 + 5^3 + 1^3 = 6^3 + 3^3 + 2^3
     

    [1]

  • 上一篇:C++习题与解析(重载-04)
    下一篇:C++习题与解析(类和对象-02)