C趣味程序百例(24)可稱1~40磅的4塊砝碼

74.可稱1~40磅的4塊砝碼
     法國數(shù)學(xué)家梅齊亞克在他的《數(shù)字組合游戲》(1962)中提出了一個問題：一位商人有一個重40磅的砝碼，一天不小心將砝碼摔成了四塊。后來商人稱得每塊的重量都是整磅數(shù)，而且發(fā)現(xiàn)這四塊碎片可以在天平上稱1至40磅之間的任意重量。請問這四塊碎片各重多少？
    *問題分析與算法設(shè)計
     本題是上一題的發(fā)展。題目中給出的條件是“在天平上”，這意味著：同一砝碼既可以放在天平的左側(cè)，也可以放在天平的右側(cè)。若規(guī)定重物只能放在天平的左側(cè)，則當(dāng)天平平衡時有：
     重物重量+左側(cè)砝碼重量總和=右側(cè)砝碼重量總和
     由此可得：
     重物重量=右側(cè)砝碼重量總和-左側(cè)砝碼重量總和
     編程時只要根據(jù)以上公式，使“右側(cè)砝碼重量總和-左側(cè)砝碼重量總和”可以表示1到40之間的全部重量即可。編程中要注意的是：怎樣采用一種簡單的方法來表示一個砝碼是在天平的左側(cè)還是在天平的右側(cè)，或是根本沒有使用。
     以下程序采用1、 -1和0分別表示上述三種情況，請注意理解。
    *程序與程序注釋
    #include
    #include
    void main()
    {
     int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag:滿足題意的標(biāo)記*/
     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;
     }
    }
    *運行結(jié)果
     The weight is broke up as following 4 pieces: 1 3 9 27