瑞昱面試的一題益智問題 - 面試

※ 引述《BearJW ( )》之銘言：
: 用若干個砝碼組合出1～100公克，
: 請問砝碼最少數量為幾個?
: 題目本身不好懂，我一開始還誤解了意思= =
: 我在解題的時候一直想到建構式數學，因為我的年代沒學過建構式。
: 不知道有沒有關聯?
: 理論上用100個1公克的砝碼可以組合出1～100個任意公克數。
: 比如說79公克，可以用79個1公克。
: 也可以用一個50公克、一個25公克、一個4公克來組成。
: 也可以用一個75公克、兩個2公克來組成。
: 不知道這題有沒有速解法?因為我是用土法煉鋼兜起來的...@@
有天秤的話是所謂 The Weight Problem of Bachet de Meziriac
http://tinyurl.com/botqgv4 第二題

砝碼有三種狀態, 放天秤左邊相當於 +1, 不放相當於 0, 放右邊相當於 -1.
以三進位代表三種狀態, 2 視同 3 - 1 展開.

100 (十進位) = 10201 (三進位)
= 1 * 3^4 + 0 * 3^3 + 2 * 3^2 + 0 * 3^1 + 1 * 3^0
= 1 * 3^4 + 0 * 3^3 + (3 + -1) * 3^2 + 0 * 3^1 + 1 * 3^0
= 1 * 3^4 + 1 * 3^3 + -1 * 3^2 + 0 * 3^1 + 1 * 3^0

左邊放 81, 27, 1 以及右邊放 9 => 81 + 27 + 1 - 9 = 100
1～100 用 5 個砝碼 (1, 3, 9, 27, 81) 就足夠組合

--