C趣味程序百例(24)

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:44:44

74.可称1~40磅的4块砝码
75.10个小孩分糖果
76.小明买书



74.可称1~40磅的4块砝码
    法国数学家梅齐亚克在他闻名的《数字组合游戏》(1962)中提出了一个问题：一位商人有一个重40磅的砝码，一天不小心将砝码摔成了四块。后来商人称得每块的重量都是整磅数，而且发现这四块碎片可以在天平上称1至40磅之间的任意重量。请问这四块碎片各重多少？
*问题分析与算法设计
    本题是上一题的发展。题目中给出的条件是“在天平上”，这意味着：同一砝码既可以放在天平的左侧，也可以放在天平的右侧。若规定重物只能放在天平的左侧，则当天平平衡时有：
            重物重量+左侧砝码重量总和=右侧砝码重量总和
 由此可得：
            重物重量=右侧砝码重量总和-左侧砝码重量总和
    编程时只要根据以上公式，使“右侧砝码重量总和-左侧砝码重量总和”可以表示1到40之间的全部重量即可。编程中要注重的是：怎样采用一种简单的方法来表示一个砝码是在天平的左侧还是在天平的右侧，或是根本没有使用。
    以下程序采用1、 -1和0分别表示上述三种情况，请注重理解。
*程序与程序注释
#include<stdio.h>
#include<math.h>
void main()
{
   int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag;     /*flag:满足题意的标记*/
   printf("The weight is broke up as following 4 pieces:");
   for(weight1=1;weight1<=40;weight1++)         /*将40分解成4份*/
      for(weight2=weight1+1;weight2<=40-weight1;weight2++)
         for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)
           if((weight4=40-weight1-weight2-weight3)>=weight3)
             {
                 for(flag=1,x=1;x<41&&flag;x++)     /*判定可否称出1~40之间的全部重量*/
                     for(flag=0,d1=1;d1>-2;d1--)     /*将重物放在天平的左边*/
                        for(d2=1;d2>-2&&!flag;d2--)   /*1:砝码在天平右边*/
                           for(d3=1;d3>-2&&!flag;d3--)    /*0：不用该砝码*/
                           for(d4=1;d4>-2&&!flag;d4--)    /*-1:砝码在天平的左边*/
                              if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)
                                 flag=1;
                  if(flag) printf("%d %d %d %d\n",weight1,weight2,weight3,weight4);
                  flag=0; 
              }
}
*运行结果
      The weight is broke up as following 4 pieces: 1  3  9  27

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

75.10个小孩分糖果
    十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块，第四个小孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块，第九个小孩14块，第十个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？
*问题分析与算法设计
    题目描述的分糖过程是一个机械的重复过程，编程算法完全可以按照描述的过程进行模拟。
*程序与程序注释
#include<stdio.h>
void print(int s[]);
int judge(int c[]);
int j=0;
void main()
{
    static int sweet[10]={10,2,8,22,16,4,10,6,14,20};   /*初始化数组数据*/
    int i,t[10],l;
    printf("              child\n");
    printf(" round       1   2   3   4   5   6   7   8   9   10\n");
    printf(".............................\n");
    print(sweet);          /*输出每个人手中糖的块数*/
    while(judge(sweet))      /*若不满足要求则继续进行循环*/
    { 
        for(i=0;i<10;i++)    /*将每个人手中的糖分成一半*/
            if(sweet[i]%2==0)     /*若为偶数则直接分出一半*/
                t[i]=sweet[i]=sweet[i]/2;
            else               /*若为奇数则加1后再分出一半*/
                t[i]=sweet[i]=(sweet[i]+1)/2;
        for(l=0;l<9;l++)         /*将分出的一半糖给右(后)边的孩子*/
            sweet[l+1]=sweet[l+1]+t[l];
        sweet[0]+=t[9];
        print(sweet);             /*输出当前每个孩子中手中的糖数*/
    }
}
int judge(int c[])
{
    int i;
    for(i=0;i<10;i++)          /*判定每个孩子手中的糖是否相同*/
        if(c[0]!=c[i]) return 1;          /*不相同返回 1*/
    return 0;
}
void print(int s[])      /*输出数组中每个元素的值*/
{
    int k;
    printf("       %2d ",j++);
    for(k=0;k<10;k++)   printf("%4d",s[k]);
    printf("\n");
}

*运行结果

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

76.小明买书
   小明假期同爸爸一起去书店，他选中了六本书，每本书的单价分别为：3.1，1.7，2，5.3，0.9和7.2。不巧的是，小明的爸爸只带了十几块钱，为了让小明过一个愉快的假期，爸爸扔然同意买书，但提邮购一个要求，要小明从六本书中选出若干本，使得单价相加所得的和同10最接近。你能够帮助小明解决这个问题吗？
*问题分析与算法设计
   分析题意，可将题目简化为：从六个数中选出若干个求和，使得和与10的差值最小。
   题目中隐含两个问题，其一是怎样从六个数中选出若干个数；其二是求与10的差。
   从六个数中选出若干个数实质是从六个数中选出若干个进行组合。每个数在组合过程中只有两种情况：要么是选中参加求和，要么是没选中不参加求和。这样就可以使用六重循环对每个数是否参加求和进行全部可能情况的组合。
   关于求与10的差值应当注重的是：差值的含义是指差的绝对值。例如：“9-10=-1"和"11-10=1",但9和11这两者与10的差值都是1。若认为”9“与”10的差值为-1就错了。
*程序与程序注释
#include<stdio.h>
#include<math.h>
void main()
{
   int d[6],m,i,j;
   long b[63],flag;
   float c[6],min,x;
   printf("Please enter the prices of 6 books:");
   for(i=0;i<6;i++)  scanf("%f",&c[i]);    /*输入六个浮点数*/
   for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++)    /*建立六个数的全部组合并处理*/
      for(d[1]=0;d[1]<2;d[1]++)           /*i:差值具有min组合的数量*/
         for(d[2]=0;d[2]<2;d[2]++)        /*min:与10的最小差值*/
            for(d[3]=0;d[3]<2;d[3]++)     /*d[]:组合时是否取该数的标志*/
               for(d[4]=0;d[4]<2;d[4]++)
                  for(d[5]=0;d[5]<2;d[5]++)
                  {
                      for(flag=0,x=0,j=5;j>=0;j--)   
                        /*flag:将六个数的组合用对应的一个十进制位表示  x:对应六个数组合的和*/
                      {
                          x+=c[j]*d[j];  flag=flag*10+d[j];
                      }
                      x=((x-10>0)? x-10:10-x);     /*x: 组合的和与10的差*/
                      if(min<0)
                      {
                         min=x;         /*对第一次计算出的差min进行处理*/
                         b[i++]=flag;   /*b[]:有相同的min的flag的数组  i:b[]数组的下标*/
                      }
                      else if(min-x>1.e-6)        /*对新的min的处理*/
                      {
                         min=x; b[0]=flag; i=1;
                      }
                      else if(fabs((double)x-min)<1.e-6)
                         b[i++]=flag;         /*对相等min的处理*/
            }
            for(m= 0;m<i;m++)     /*输出全部i个与10的差值均为min的组合*/
            {
               printf("10(+ -)%.2f=",min);
               for(flag=b[m],j=0;flag>0;j++,flag/=10)
                  if(flag%10)       /*将b[]中存的标记flag还原为各个数的组合*/
                     if(flag>1) printf("%.2f+",c[j]);
                     else printf("%.2f\n",c[j]);
            }
}
*运行结果
      Please enter the prices of 6 books:3.1  1.7  2.0  5.3  0.9  7.2
      10(+ -)0.10=2.00+0.90+7.20
      10(+ -)0.10=1.70+2.00+5.30+0.90
      10(+ -)0.10=3.10+1.70+5.30

*思考题
    可以看出，程序中求六个数所能产生全部组合的算法并不好，使用六重循环进行处理使程序显得不够简洁。可以设计出更通用、优化的算法产生全部组合。

上一篇：{实例}C趣味程序百例(23) 人气:6544
下一篇：{实例}C趣味程序百例(25) 人气:6997

C语言程序设计视频教程