C語言經典算法 - 八枚銀幣問題
說明現有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或
較重，如何使用天平以最少的比較次數，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。
解法單就求假幣的問題是不難，但問題限制使用最少的比較次數，所以我們不能以單純的回
圈比較來求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來協助求解。一個簡單
的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個
較重，如果g較重，再與a比較（a是真幣），如果g等于a，則g為真幣，則h為假幣，由于h比g輕
而g是真幣，則h假幣的重量比真幣輕。

#include <stdio.h>

include <stdlib.h>
include <time.h>
void compare(int[], int, int, int);
void eightcoins(int[]);
int main(void)
{
  int coins[8] =
  {
    0
  };
  int i;
  srand(time(NULL));
  for (i = 0; i < 8; i++)
    coins[i] = 10;
  printf("\n輸入假幣重量(比10大或小)：");
  scanf("%d", &i);
  coins[rand() % 8] = i;
  eightcoins(coins);
  printf("\n\n列出所有錢幣重量：");
  for (i = 0; i < 8; i++)
    printf("%d ", coins[i]);
  printf("\n");
  return 0;
}
void compare(int coins[], int i, int j, int k)
{
  if (coins[i] > coins[k])
    printf("\n假幣%d 較重", i + 1);
  else
    printf("\n假幣%d 較輕", j + 1);
}
void eightcoins(int coins[])
{
  if (coins[0] + coins[1] + coins[2] == coins[3] + coins[4] + coins[5])
  {
    if (coins[6] > coins[7])
      compare(coins, 6, 7, 0);
    else
      compare(coins, 7, 6, 0);
  }
  else if (coins[0] + coins[1] + coins[2] > coins[3] + coins[4] + coins[5])
  {
    if (coins[0] + coins[3] == coins[1] + coins[4])
      compare(coins, 2, 5, 0);
    else if (coins[0] + coins[3] > coins[1] + coins[4])
      compare(coins, 0, 4, 1);
    if (coins[0] + coins[3] < coins[1] + coins[4])
      compare(coins, 1, 3, 0);
  }
  else if (coins[0] + coins[1] + coins[2] < coins[3] + coins[4] + coins[5])
  {
    if (coins[0] + coins[3] == coins[1] + coins[4])
      compare(coins, 5, 2, 0);
    else if (coins[0] + coins[3] > coins[1] + coins[4])
      compare(coins, 3, 1, 0);
    if (coins[0] + coins[3] < coins[1] + coins[4])
      compare(coins, 4, 0, 1);
  }
}</pre>