Re: [請益] 瑞昱面試的一題益智問題
※ 引述《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) 就足夠組合
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.225.238
推
11/21 10:18, , 1F
11/21 10:18, 1F
推
11/21 10:24, , 2F
11/21 10:24, 2F
推
11/21 12:20, , 3F
11/21 12:20, 3F
推
11/21 14:34, , 4F
11/21 14:34, 4F
推
11/21 15:54, , 5F
11/21 15:54, 5F
推
11/21 21:41, , 6F
11/21 21:41, 6F
推
11/21 21:58, , 7F
11/21 21:58, 7F
推
11/22 01:30, , 8F
11/22 01:30, 8F
推
11/22 05:05, , 9F
11/22 05:05, 9F
→
11/22 06:05, , 10F
11/22 06:05, 10F
→
11/22 06:05, , 11F
11/22 06:05, 11F
→
11/22 06:05, , 12F
11/22 06:05, 12F
討論串 (同標題文章)