天秤で 1g, 3g, 9g, 27g の分銅を用いて 1~40g の重さを量る方法について.
※2013年12月頃に Python 手習のため書いた短いコードをまとめたもの.
天秤と 1g, 3g, 9g, 27g の4つの分銅があれば 1〜40g の重さを量ることができる.
左 | 右 | |
---|---|---|
1 | = | 1 |
2 + 1 | = | 3 |
3 | = | 3 |
4 | = | 1 + 3 |
5 + 1 + 3 | = | 9 |
6 + 3 | = | 9 |
7 + 3 | = | 1 + 9 |
8 + 1 | = | 9 |
9 | = | 9 |
10 | = | 1 + 9 |
... |
一般に 30g, 31g, ..., 3n-1g の n 個の分銅があれば 1 〜 (3n - 1)/2g の重さを量ることができる.
これは平衡三進法 (balanced ternary) で説明できる.
Balanced ternary - Wikipedia [en]
通常の三進法では 0, 1, 2 の3つの数字で表現するところを, 平衡三進法では -1, 0, 1 の3つで表現する.
位取りは通常の三進法と同じで, 右から1の位, 3の位, 9の位, 27の位, …となる.
平衡三進法による 1〜10 を次表に示す. ただし 1 を "+", -1 を "-" と表記する.
数 | 平衡三進法による表現 |
---|---|
1 | + |
2 | +- |
3 | +0 |
4 | ++ |
5 | +-- |
6 | +-0 |
7 | +-+ |
8 | +0- |
9 | +00 |
10 | +0+ |
... | ... |
1の位が 1g の分銅、3の位が 3g の分銅、... に対応し, "+" は右の皿に、 "-" は左の皿に分銅を乗せることに対応する.
左 | 右 | 平衡三進法による表現 | |
---|---|---|---|
1 | = | 1 | + |
2 + 1 | = | 3 | +- |
3 | = | 3 | +0 |
4 | = | 3 + 1 | ++ |
5 + 3 + 1 | = | 9 | +-- |
6 + 3 | = | 9 | +-0 |
7 + 3 | = | 1 + 9 | +-+ |
8 + 1 | = | 9 | +0- |
9 | = | 9 | +00 |
10 | = | 9 + 1 | +0+ |
... |
任意の入力値を平衡三進法で表現する関数 btern()
を何通りかの方法で実装した.
btern1.py
: 最初の実装. いったん通常の三進数を経由する.
例: 8 の場合. 8 + (1 + 3 + 9) = 20 の三進数表現は 210. この各桁から 1 を引いて(つまり合計 9 + 3 + 1 を引いて)+0-.
まどろっこしい.btern2.py
: 平衡三進法の素朴な実装. リスト型で作成してから文字列に変換.btern3.py
:divmod
を使うとかなり短縮できることに気づく.btern4.py
: さらにジェネレータを駆使し短く書く.btern5.py
: 再帰を利用して1行で書けた.
btern()
を利用して天秤問題の解となる等式を出力する関数 solve()
を実装.
solve1.py
: 素朴に if 分岐で左辺と右辺に分銅を乗せていく.solve2.py
: 少しひねった書き方. 辞書 (dict) を使用.
最後に, できるだけ短く書く挑戦.
solve3_golf.py
(130 bytes) : 1〜40g の解を表示する.btern4()
のジェネレータを応用した.
$ python solve3_golf.py
1 = 1
2 + 1 = 3
3 = 3
4 = 1 + 3
5 + 1 + 3 = 9
6 + 3 = 9
7 + 3 = 1 + 9
8 + 1 = 9
9 = 9
10 = 1 + 9
11 + 1 = 3 + 9
12 = 3 + 9
13 = 1 + 3 + 9
14 + 1 + 3 + 9 = 27
15 + 3 + 9 = 27
16 + 3 + 9 = 1 + 27
17 + 1 + 9 = 27
18 + 9 = 27
19 + 9 = 1 + 27
20 + 1 + 9 = 3 + 27
21 + 9 = 3 + 27
22 + 9 = 1 + 3 + 27
23 + 1 + 3 = 27
24 + 3 = 27
25 + 3 = 1 + 27
26 + 1 = 27
27 = 27
28 = 1 + 27
29 + 1 = 3 + 27
30 = 3 + 27
31 = 1 + 3 + 27
32 + 1 + 3 = 9 + 27
33 + 3 = 9 + 27
34 + 3 = 1 + 9 + 27
35 + 1 = 9 + 27
36 = 9 + 27
37 = 1 + 9 + 27
38 + 1 = 3 + 9 + 27
39 = 3 + 9 + 27
40 = 1 + 3 + 9 + 27
$