Question

一位商人有9枚銀元，其中有1枚略輕的是假銀元，你能用天平（不用砝碼）將假銀元找出來嗎？

Answer 1

思路解析：最容易想到的解決這個問題的一種方法是：把9枚銀元按順序排成一列，先稱前2枚，若不平衡，則可找出假銀元；若平衡，則2枚銀元都是真的，再依次與剩下的銀元比較，就能找出假銀元.

    同一個問題可能存在著多種算法，其中一些可能要比另一些好.在實際問題和算法理論中，找出好的算法是一項重要的工作.

解：其算法如下：

    算法一：第一步：任取2枚銀元分別放在天平的兩邊，如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則進行第二步.

    第二步：取下右邊的銀元放在一邊，然后把剩余的7枚銀元依次在右邊進行稱量，直到天平不平衡，偏輕的那一枚就是假銀元.

    探究1：上述算法最少要稱1次，最多稱7次，我們可以采用下面的辦法，使稱量數(shù)少一些.

    算法二：第一步：任取2枚銀元分別放在天平的兩邊，如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則進行第二步.

    第二步：從余下的7枚銀元中再任取2枚分別放在天平的兩邊，如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則進行第三步.

    第三步：從余下的5枚銀元中再任取2枚分別放在天平的兩邊，如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則進行第四步.

    第四步：從余下的3枚銀元中再任取2枚分別放在天平的兩邊，如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則最后剩下的還未稱的1枚銀元就是假銀元.

    探究2：上述算法最少要稱1次，最多稱4次，那有沒有辦法使稱的最多次數(shù)少于4次的呢？

    算法三：第一步：任取4枚銀元分別放在天平的兩邊各2枚，如果天平左右不平衡，則輕的一邊中含有假銀元,并進行第二步；如果天平平衡，則進行第三步.

    第二步：將輕的一邊的兩枚銀元各1個分別放入天平的兩邊，則輕的一邊的那枚銀元就是假銀元.稱法結(jié)束.

    第三步：從余下的5枚銀元中再任取4枚分別放在天平的兩邊各2枚，如果天平左右不平衡，則輕的一邊就是假銀元，并轉(zhuǎn)第二步；如果天平平衡，則最后剩下的還未稱的1枚銀元就是假銀元，稱法結(jié)束.

    探究3：上述算法最少要稱兩次，最多稱3次，是否還有更好的算法呢？

    算法四：

    第一步：把銀元分成3組，每組3枚.

    第二步：先將兩組分別放在天平的兩邊，如果天平不平衡，那么假銀元就在輕的那一組；如果天平左右平衡，則假銀元就在未稱的第3組里.

    第三步：取含假銀元的那一組，從中任取兩枚銀元放在天平的兩邊，如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則未稱的那一枚就是假銀元.