Question

一位商人有9枚銀元，其中有1枚略輕的是假銀元，你能用天平(無(wú)砝碼)將假銀元找出來(lái)嗎？寫出解決這一問題的一種算法．

Answer 1

答案：略
解析：

解法1：算法步驟如下： 第一步：任取2枚銀元分別放在天平的兩邊，如果天平左右不平衡，那么輕的那一邊就是假銀元；如果天平平衡，那么進(jìn)行第二步； 第二步：取下右邊的銀元，放在一邊，然后把剩下的7枚銀元依次放在右邊進(jìn)行稱量，直到天平不平衡，偏輕的那一邊就是假銀元． 解法2：算法步驟如下： 第一步：把9枚銀元平均分成3組，每組3枚； 第二步：先將其中兩組放在天平的兩邊，如果天平不平衡，那么假銀元就在輕的那一組；如果天平左右平衡，則假銀元就在未稱量的那一組里； 第三步：取出含假銀元的那一組，從中任取2枚銀元放在左右天平兩邊進(jìn)行稱量，如果天平不平衡，則假銀元在輕的那一邊；若天平平衡，則未稱的那一枚就是假銀元． 這樣利用上述算法，只需兩次稱量就可以將假銀元找出來(lái)，顯然要比第一種算法簡(jiǎn)捷、有效．

提示：

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