问题陈述：

　　现有八枚银币a b c d e f g h，已知其中一枚是假币，其质量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，判断出哪枚是假币，并得知假币比真币较轻或较重？

问题解法：

　　单求假币的问题并不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树(decision tree)，使用分析与树状图协助求解。一个简单的状况是这样的，我们比较a+b+c与d+e+f，如果相等，则比较g和h；如果不相等，则比较a+d与b+e，以此类摧。

 

代码详解：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7  8 void compare(int[], int, int, int); 9 void eightCoins(int[]);10 11 int main()12 {13     int i;14     int coins[8] = {
   0};15 16     srand(time(NULL));17 18     for(i=0; i<8; i++) {19         coins[i] = 10;20     }21 22     printf("请输入假币质量(>10||<10): ");23     scanf("%d", &i);24     coins[rand()%8] = i;25 26     eightCoins(coins);27 28     printf("列出所有银币质量:\n");29     for(i=0; i<8; i++) {30         printf("%d ", coins[i]);31     }32     return 0;33 }34 //coins[i]>coins[j] k为真币35 void compare(int coins[], int i, int j, int k) {36     if(coins[i] > coins[k]) {37         printf("假币 %d 较重\n", i+1);38     }else {39         printf("假币 %d 较轻\n", j+1);40     }41 }42 43 void eightCoins(int coins[]) {44     if(coins[0]+coins[1]+coins[2] == coins[3]+coins[4]+coins[5]) {45         if(coins[6] > coins[7]) {46             compare(coins, 6, 7, 0);47         }else {48             compare(coins, 7, 6, 0);49         }50     }else if(coins[0]+coins[1]+coins[2] > coins[3]+coins[4]+coins[5]) {51         //coins[2] > coins[5]52         if(coins[0]+coins[3] == coins[1]+coins[4]) {53             compare(coins, 2, 5, 0);54         //1,3真币 coins[0]>coins[4]55         }else if(coins[0]+coins[3] > coins[1]+coins[4]) {56             compare(coins, 0, 4, 1);57         //0,4真币 coins[3]
         
          coins[1]66         }else if(coins[0]+coins[3] > coins[1]+coins[4]) {67             compare(coins, 3, 1, 0);68         //1,3真币 coins[0]
         
        
       
      
     

 

转载请注明出处：