法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)
中提出了一个问题：
 一位商人有一个重40磅的砝码，一天不小心将砝码摔成了
 四块。后来商人称得每块的重量都是整磅数，而且发现这
 四块碎片可以在天平上称1至40磅之间的任意重量。请问
 这四块碎片各重多少？
 问题分析与算法设计
 题目中给出的条件是“在天平上”，这意味着：同一砝码
 既可以放在天平的左侧，也可以放在天平的右侧。若规定
 重物只能放在天平的左侧，则当天平平衡时有：
 重物重量+左侧砝码重量总和=右侧砝码重量总和
 由此可得：
 重物重量=右侧砝码重量总和-左侧砝码重量总和
 编程时只要根据以上公式，使得
 右侧砝码重量总和-左侧砝码重量总和
 可以表示1到40之间的全部重量即可。编程中要注意的是：
 怎样采用一种简单的方法来表示一个砝码是在天平的左侧
 还是在天平的右侧，或是根本没有使用。
 以下程序采用1、 -1和0分别表示上述三种情况。
 程序与程序注释
**************************************************/

 
#include<stdio.h>
#include<math.h>
int main(void)
{
    int weight1,weight2,weight3,weight4;//摔坏的四块砝码的重量
    int d1,d2,d3,d4;//四块砝码是放在左盘还是右盘,或者根本没有使用
    int x,flag;//x:可用四块砝码称出的重量,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;
                }
    system("pause");
    return 0;
}

/*******************************************************
 *运行结果
 *The weight is broke up as following 4 pieces: 1 3 9 27
 *******************************************************/

评论