C趣味程序百例(19)

61.1~9组成三个3位的平方数  
62.由8个整数形成奇异的立方体  
   



61.1~9组成三个3位的平方数   
    将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不答应有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。
*问题分析与算法设计
    本问题的思路很多，这里介绍一种简单快速的算法。
    首先求出三位数中不包含0且是某个整数平方的三位数，这样的三位数是不多的。然后将满足条件的三位数进行组合，使得所选出的3个三位数的9个数字没有重复。
    程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。
*程序与程序注释
#include<stdio.h>
void main()
{
    int a[20],num[20][3],b[10];     /*a:存放满足条件的三位数*/
                                    /*若不是10 的倍数，则分解三位数*/
                                    /*分解该三位数中的每一个数字*/
    int i,j,k,m,n,t,flag;
    printf("The 3 squares with 3 different digits each are:\n");
    for(j=0,i=11;i<=31;i++)      /*求出是平方数的三位数*/
    if(i%10!=0)            /*若不是10的倍数，则分解三位数*/
    {
        k=i*i;             /*分解该三位数中的每一个数字*/
        num[j+1][0]=k/100;   /*百位*/
        num[j+1][1]=k/10%10;    /*十位*/
        num[j+1][2]=k%10;      /*个位*/
        if(!(num[j+1][0]==num[j+1][1]||num[j+1][0]==num[j+1][2]||
                            num[j+1][1]==num[j+1][2]))     /*若分解的三位数字均不相等*/
            a[++j]=k;      /*j:计数器，统计已找到的满足要求的三位数*/
    }
    for(i=1;i<=j-2;++i)     /*从满足条件的三位数中选出三个进行组合*/
    {
        b[1]=num[i][0];
        b[2]=num[i][1];
        b[3]=num[i][2];
        for(t=i+1;t<=j-1;++t)
        {
            b[4]=num[t][0];           /*取第t个数的三位数字*/
            b[5]=num[t][1];
            b[6]=num[t][2];
            for(flag=0,m=1;!flag&&m<=3;m++)     /*flag:出现数字重复的标记*/
                for(n=4;!flag&&n<=6;n++)      /*判定两个数的数字是否有重复*/
                    if(b[m]==b[n])flag=1;      /*flag=1:数字有重复*/
            if(!flag)
                for(k=t+1;k<=j;k++)
                {
                    b[7]=num[k][0];         /*取第k个数的三位数字*/
                    b[8]=num[k][1];
                    b[9]=num[k][2];
                    for(flag=0,m=1;!flag&&m<=6;m++)  /*判定前两个数字是否*/
                        for(n=7;!flag&&n<=9;n++)     /*与第三个数的数字重复*/
                            if(b[m]==b[n])flag=1;
                    if(!flag)             /*若均不重复则打印结果*/
                        printf("%d,%d,%d\n",a[i],a[t],a[k]);
                }
        }
    }
}
*运行结果
    The 3 squares with 3 different digits each are:
        361,529,784

*思考题
    将1、2、3、4、5、6、7、8、9九个数字分成二组，每个数字只能用一次，一组形成一个5位数，另一组形成一个4位数，使得前者为后者的n倍。求所有满足条件的5位数和4位数。(注重：N的最大值等于68,68以内的某些N也是不可能的。不可能的N值包括：1、10、11、20、21、25、30、31等共32个。)

-------------------------------------------------------

62.由8个整数形成奇异的立方体
    任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数之和相等。
*问题分析与算法设计
    简化问题：将8个顶点对应数组中的8个元素，将“每个面上的四个数之和皆相等”转换为数组无素之间和的相等关系。这里的要害在于正确地将立方体的8个顶点与数组的8个元素对应。
    可以利用简单的穷举方法建立8个数的全部排列。
*程序与程序注释
#include<stdio.h>
#include<stdlib.h>
void main()
{
    int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag;
    for(i=1;i<=8;i++)               /*输入个数*/
    {
        printf("Please enter [%d]number:",i);
        scanf("%d",&a[i]);
        ii+=a[i];
    }
    printf("******************************************\n");
    if(ii%2)   /*和为奇数则输入的8个数不可用*/
    {
        printf("Sorry they can't be constructed required cube!\n");
        exit(0);
    }
    for(flag=0,a1=1;a1<=8;a1++)         /*flag:完成标记.flag=1;表示完成*/
      for(a2=1;a2<=8;a2++)      /*采用八重循环建立八个整数的全排列*/
        if(a2!=a1)            /*前两个数不能相同*/
          for(a3=1;a3<=8;a3++)    
            if(a3!=a2&&a3!=a1)    /*前三个数不能相同*/
              for(a4=1;a4<=8;a4++)
                if(a4!=a3&&a4!=a2&&a4!=a1)         /*前四个数不能相同*/
                   for(b1=1;b1<=8;b1++)
                     if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1)     /*不能相同*/
                        for(b2=1;b2<=8;b2++)
                          if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1)
                            for(b3=1;b3<=8;b3++)
                              if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1)
                                                          /*不能取相同的数*/
                                for(b4=1;b4<=8;b4++)
                                  if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1)
                                    if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2
                                          &&a[a1]+a[a2]+a[b1]+a[b2]==ii/2
                                          &&a[a1]+a[a4]+a[b1]+a[b4]==ii/2)
                                    {
                                      flag=1;goto out;  /*满足条件则将flag置1后退出*/
                                    }
  out:
    if(flag)
    {
        printf("They can be constructed required cube as follow:\n");
        printf("        /%2d............/%2d\n",a[a4],a[a3]);
        printf("        %2d/............%2d/|\n",a[a1],a[a2]);
        printf("        |  |            |  |\n");
        printf("        |  |            |  |\n");
        printf("        |  %2d|          |  |%2d\n",a[b4],a[b3]);
        printf("        /................/\n");
        printf("        %2d/.............%2d/\n",a[b1],a[b2]);
    }
    else printf("Sorry they can't be constructed required cube!\n");
}
*运行结果
      Please enter [1] number:20
      Please enter [2] number:45
      Please enter [3] number:39
      Please enter [4] number:25
      Please enter [5] number:29
      Please enter [6] number:7
      Please enter [7] number:3
      Please enter [8] number:2
      Sorry they can't be constructed required cube!     
     

思考题
    程序中建立全排列的方法效率太低，算法虽然简单但程序过于冗余。请读者自行设计新的算法完成同样的工作。

上一篇：{实例}C趣味程序百例(18) 人气:6807
下一篇：{实例}C趣味程序百例(20) 人气:4496

C语言程序设计视频教程

Windows操作[文]	Word教程[文]	Excel教程[文]	PowerPoint[文]	Dreamweaver[文]	Fireworks[文]
Flash教程[文]	PhotoShop[文]	CorelDraw[文]	C语言教程[文]	Html教程[文]	Div+Css布局[文]
Javascript[文]	ACCESS数据库[文]	ASP教程[文]	SQLServer[文]	ASP.NET教程[文]	FlashAS[文]