Question

一位商人有9枚銀元，其中有1枚略輕的是假銀元.你能用天平（無砝碼）將假銀元找出來嗎？寫出解決這一問題的一種算法.

Answer 1

思路分析：對于這種非數(shù)值性問題的算法的設(shè)計(jì)問題，應(yīng)首先建立過程模型，根據(jù)過程設(shè)計(jì)步驟，完成算法.最容易想到的解決該問題的辦法是：把9枚銀元按順序排成一列，先稱前2塊，若不平衡，則可找出假銀元；若平衡，則這2塊都是真的，再依次與剩下的銀元作稱量比較，就能找出假銀元.這種辦法最少要稱量1次，最多則要稱量7次，仔細(xì)分析，我們還可以用分組的方法進(jìn)行稱量，從而有以下兩種解法.

解法1  算法步驟如下：

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

第二步：取下右邊的銀元，放在一邊，然后把剩下的7枚銀元依次放在右邊進(jìn)行稱量，偏輕的那一邊就是假銀元.

解法2  分組稱量設(shè)計(jì)的算法如下：

第一步：把9枚銀元平均分成3組，每組3枚；

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

第三步：取出含假銀元的那一組，從中任取2枚放在天平兩邊進(jìn)行稱量，如果天平不平衡，那么假銀元就在輕的那一邊；如果天平左右平衡，則未稱的那一枚就是假銀元.