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

※ 引述《wolfpig (wolfpig)》之銘言：
: ※ 引述《BearJW ( )》之銘言：
: : 用若干個砝碼組合出1～100公克，
: : 請問砝碼最少數量為幾個?
: : 題目本身不好懂，我一開始還誤解了意思= =
: : 我在解題的時候一直想到建構式數學，因為我的年代沒學過建構式。
: : 不知道有沒有關聯?
: : 理論上用100個1公克的砝碼可以組合出1～100個任意公克數。
: : 比如說79公克，可以用79個1公克。
: : 也可以用一個50公克、一個25公克、一個4公克來組成。
: : 也可以用一個75公克、兩個2公克來組成。
: : 不知道這題有沒有速解法?因為我是用土法煉鋼兜起來的...@@
: lg(100) ~ 7
: 1g, 2g, 4g, 8g, 16g, 32g, 64g.
: 以上七個砝碼可以組成任意公克數
如果題目是1g, 2g, 4g, 8g, 16g, 32g, 64g，這是科技業的考法。

如果題目是1g, 5g, 10g, 20g, 25g，這是資訊軟體業的考法。

沒有好與不好，各自有著重的點。

但是如果是資訊軟體業的考法，一定是用DP求出最佳化的解。

至於第一種考法，把剩餘的數量一直除最大的就可以了。

太久沒寫這類題目，給出代碼，有錯再說。

https://gist.github.com/4114601



--