C语言穷举法解决破碎的砝码

1.问题描述

一天商人不小心把40磅重的砝码摔成4部分，发现4部分砝码的重量都是整磅数，而且可以用它们称出任意1-40之间的整数磅质量，问这四块砝码各重多少磅？

2.该问题的数学分析

①必须有1磅的砝码,否则39磅的重量无法称出.
②有了1磅的砝码后,再加上一个3磅的砝码,可称出2~4磅的重量.
③有了1磅和3磅的砝码后,再加上一个9磅的砝码,可称出5~13磅的重量.
④有了1、3、9磅的砝码后,再加上一个27磅的砝码,可称出14~40磅的重量.
所以这4块砝码碎片分别是1、3、9、27磅,即首项为1,公比为3的等比数列.

 1 #include <stdio.h>
 2 
 3 int check(int a,int b,int c,int d,int i);
 4 
 5 int main(int argc, char *argv[])
 6 {
 7     int a,b,c,d,i;            //四块砝码重量
 8     for(a=1;a<40;a++)
 9         for(b=a+1;b<40;b++)
10             for(c=b+1;c<40;c++)
11                 for(d=c+1;d<40;d++)
12                     //使用这种循环可以防止重复,比如1234,和4321数字相同,顺序不同 
13                     if( (a+b+c+d) == 40){
14                         int flag=1;            //标志变量 
15                         for(i=1;i<=40;i++){
16                             if(!check(a,b,c,d,i)) flag=0;    //如果有一个i不符合 
17                         }                         
18                         if(flag)            //flag=1说明所有的i都符合 
19                             printf("%d %d %d %d
",a,b,c,d);    
20                     }
21                     
22     return 0;
23 }
24 
25 //检查四块碎片是否符合条件 
26 int check(int a,int b,int c,int d,int i){
27     int x1,x2,x3,x4;
28         for(x1=-1;x1<=1;x1++)    
29             for(x2=-1;x2<=1;x2++)    
30                 for(x3=-1;x3<=1;x3++)    
31                     for(x4=-1;x4<=1;x4++)
32                         if( (a*x1+b*x2+c*x3+d*x4 == i)) 
33                             return 1;
34                             
35                                     
36         return 0; 
37 }

输出:

1 3 9 27