砝碼稱重問題

轉載自：http://blog.csdn.net/livelylittlefish/archive/2009/01/29/3854702.aspx

問題：4個砝碼，每個重量都是整數克，總重量為40克，放在天平上可以稱出1～40克的物體。求這4個砝碼各多少克。

1. 問題分析

設4個砝碼的重量分別為w1、w2、w3、w4，則w1+w2+w3+w4=40，且w1,w2,w3,w4均為正整數。
假設不相等(假設w1<w2<w3<w4)，故砝碼中最大為34克。

稱重的天平有物體盤和砝碼盤，稱重時，若砝碼只放在砝碼盤，則
物體質量=砝碼盤砝碼質量
但若砝碼盤和物體盤中都放置了砝碼，則
物體質量=砝碼盤砝碼質量-物體盤砝碼質量

從1～40，任意一個數，都應該能找到相應的砝碼放置方法。砝碼只有4個，且每次稱重時，這4個砝碼只能出現0次或者1次，且砝碼要麼在物體盤，要麼在砝碼盤，要解該問題，應該轉換思路。
假設砝碼在物體盤，認定其出現-1次
假設砝碼在砝碼盤，認定其出現1次
若該次稱重，不需要該砝碼，認定其出現0次

設4個砝碼在每次稱重中出現的次數分別為x1,x2,x3,x4，則只有-1、0、1這三種取值

如上分析，找到的砝碼組合個數應該為40個（即1～40中的任意一個數都有對應的砝碼組合）

2. C++

1. /*******************************************************************
   
2.  * 4個砝碼，每個重量都是整數克，總重量為40克，放在天平上可以稱出1～40克的 
3.  * 物體。求這4個砝碼各多少克。 
4.  * C++版 
5.  ********************************************************************/  
6. #include <stdio.h>  
7.   
8. class CWeight  
9. {  
10.     int w1,w2,w3,w4;    //砝碼的重量  
11.   
12.     //砝碼總重量  
13.     static const int TOTALWEIGHT=40;  
14.   
15.     //4個砝碼,w1+w2+w3+w4=40,且w1,w2,w3,w4均為整數,假設不相等(假設w1<w2<w3<w4)故最大為34  
16.     static const int MAXWEIGHT=34;  
17. public:  
18.     CWeight(){w1=w2=w3=w4=0;}  
19.     ~CWeight(){}  
20.   
21.     void Calculate();  
22.     bool weight(int w1,int w2,int w3,int w4);  
23.     void output(int w1,int w2,int w3,int w4);  
24. };  
25.   
26. void CWeight::Calculate()  
27. {  
28.     int w1,w2,w3,w4;  
29.     for (w1=1;w1<=MAXWEIGHT;w1++)  
30.     {  
31.         for (w2=w1+1;w2<=MAXWEIGHT;w2++)  
32.         {  
33.             for (w3=w2+1;w3<=MAXWEIGHT;w3++)  
34.             {  
35.                 for (w4=w3+1;w4<=MAXWEIGHT;w4++)  
36.                 {  
37.                     if (w1+w2+w3+w4==TOTALWEIGHT)  
38.                     {  
39.                         if (weight(w1,w2,w3,w4))  
40.                         {  
41.                             printf("w1=%d w2=%d w3=%d w4=%d\n",w1,w2,w3,w4);  
42.                             output(w1,w2,w3,w4);  
43.                         }                         
44.                     }  
45.                 }  
46.             }  
47.         }  
48.     }  
49. }  
50.   
51. //從1～40，不管哪個重量都要找到相應的砝碼放置方法  
52. //w1,w2,w3,w4分別為4個砝碼的重量  
53. bool CWeight::weight(int w1,int w2,int w3,int w4)  
54. {  
55.     int w;  //物體重量  
56.       
57.     //砝碼只有4個，且每次稱重時，這4個砝碼只能出現0次或者1次  
58.     //出現時，砝碼要麼在物體盤，要麼在砝碼盤，要解該問題，轉換思路  
59.     //假設砝碼在物體盤，認定其出現-1次  
60.     //假設砝碼在砝碼盤，認定其出現1次  
61.     //若該次稱重，不需要該砝碼，認定其出現0次  
62.     //4個砝碼在每次稱重中出現的次數  
63.     int x1,x2,x3,x4;    //只有-1，0，1這三種取值  
64.   
65.     int count=0;        //找到的砝碼組合個數  
66.   
67.     //對1～40中的每個重量，都要找到相應的砝碼組合  
68.     //若有一個w(1<=w<=TOTALWEIGHT)沒有找到相應的砝碼組合，則表明該組砝碼值不是所求  
69.     for (w=1;w<=TOTALWEIGHT;w++)   
70.     {  
71.         for (x1=-1;x1<=1;x1++)  
72.         {  
73.             for (x2=-1;x2<=1;x2++)  
74.             {  
75.                 for (x3=-1;x3<=1;x3++)  
76.                 {  
77.                     for (x4=-1;x4<=1;x4++)  
78.                     {  
79.                         if (w1*x1+w2*x2+w3*x3+w4*x4==w)  
80.                         {  
81.                             count++;  
82.   
83.                             //找到該重量對應的砝碼組合後，繼續下一個重量  
84.                             x1=x2=x3=x4=2;  
85.                         }  
86.                     }  
87.                 }  
88.             }  
89.         }  
90.     }  
91.   
92.     //如果找到所有的1~TOTALWEIGHT的砝碼組合,則該組砝碼值即為所求  
93.     if (count==TOTALWEIGHT)  
94.         return true;  
95.     else  
96.         return false;  
97. }  
98.   
99. //輸出1～40中每個重量對應的砝碼組合（負數表示該砝碼放在物體盤）  
100. void CWeight::output(int w1,int w2,int w3,int w4)  
101. {  
102.     int w;  //物體重量  
103.     int x1,x2,x3,x4;    //只有-1，0，1這三種取值  
104.   
105.    //對1～TOTALWEIGHT中的每個重量，都要找到相應的砝碼組合  
106.     for (w=1;w<=TOTALWEIGHT;w++)   
107.     {  
108.         for (x1=-1;x1<=1;x1++)  
109.         {  
110.             for (x2=-1;x2<=1;x2++)  
111.             {  
112.                 for (x3=-1;x3<=1;x3++)  
113.                 {  
114.                     for (x4=-1;x4<=1;x4++)  
115.                     {  
116.                         if (w1*x1+w2*x2+w3*x3+w4*x4==w)  
117.                         {  
118.                             printf("w=%2d: ",w);  
119.                             if (x1!=0)  
120.                                 printf("%d ",w1*x1);  
121.                             if (x2!=0)  
122.                                 printf("%d ",w2*x2);  
123.                             if (x3!=0)  
124.                                 printf("%d ",w3*x3);  
125.                             if (x4!=0)  
126.                                 printf("%d ",w4*x4);  
127.                             printf("\n");  
128.   
129.                             //繼續下一個重量  
130.                             x1=x2=x3=x4=2;  
131.                         }  
132.                     }  
133.                 }  
134.             }  
135.         }  
136.     }  
137. }  
138.   
139. int main()  
140. {  
141.     CWeight wei;  
142.     wei.Calculate();  
143.   
144.     return 0;  
145. } 
     

3. 執行結果

說明：第一行表示4個砝碼的質量分別為1，3，9，27

         其他行，負數表示該砝碼放在物體盤，正數表示該砝碼放在砝碼盤

w1=1 w2=3 w3=9 w4=27
w= 1: 1
w= 2: -1 3
w= 3: 3
w= 4: 1 3
w= 5: -1 -3 9
w= 6: -3 9
w= 7: 1 -3 9
w= 8: -1 9
w= 9: 9
w=10: 1 9
w=11: -1 3 9
w=12: 3 9
w=13: 1 3 9
w=14: -1 -3 -9 27
w=15: -3 -9 27
w=16: 1 -3 -9 27
w=17: -1 -9 27
w=18: -9 27
w=19: 1 -9 27
w=20: -1 3 -9 27
w=21: 3 -9 27
w=22: 1 3 -9 27
w=23: -1 -3 27
w=24: -3 27
w=25: 1 -3 27
w=26: -1 27
w=27: 27
w=28: 1 27
w=29: -1 3 27
w=30: 3 27
w=31: 1 3 27
w=32: -1 -3 9 27
w=33: -3 9 27
w=34: 1 -3 9 27
w=35: -1 9 27
w=36: 9 27
w=37: 1 9 27
w=38: -1 3 9 27
w=39: 3 9 27
w=40: 1 3 9 27