## 2018年12月14日金曜日

### Algorithm - Python - ひねりを加えたバラモンの塔(棒が4本の場合のハノイの塔、分割、手数、再帰的に1つ減らして探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

def hanoi(ring_number: int, origin: int,
peg1: int, peg2: int, peg3: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi(ring_number - 1, origin, peg1, peg3, peg2)
print(
f'Move ring {ring_number + origin} from peg {peg1} to peg {peg3}')
num_moves += 1
num_moves += hanoi(ring_number - 1, origin, peg2, peg1, peg3)
return num_moves

def hanoi_four_peg(ring_number: int,
peg1: int, peg2: int, peg3: int, peg4: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi(ring_number // 2, 0, peg1, peg2, peg4)
origin = ring_number // 2
num_moves += hanoi(ring_number // 2, origin, peg1, peg2, peg3)
num_moves += hanoi(ring_number // 2, 0, peg4, peg1, peg3)
return num_moves

if __name__ == '__main__':
num = hanoi_four_peg(8, 1, 2, 3, 4)
print(num, num == 45)
```

```\$ ./sample1.py
Move ring 1 from peg 1 to peg 2
Move ring 2 from peg 1 to peg 4
Move ring 1 from peg 2 to peg 4
Move ring 3 from peg 1 to peg 2
Move ring 1 from peg 4 to peg 1
Move ring 2 from peg 4 to peg 2
Move ring 1 from peg 1 to peg 2
Move ring 4 from peg 1 to peg 4
Move ring 1 from peg 2 to peg 4
Move ring 2 from peg 2 to peg 1
Move ring 1 from peg 4 to peg 1
Move ring 3 from peg 2 to peg 4
Move ring 1 from peg 1 to peg 2
Move ring 2 from peg 1 to peg 4
Move ring 1 from peg 2 to peg 4
Move ring 5 from peg 1 to peg 2
Move ring 6 from peg 1 to peg 3
Move ring 5 from peg 2 to peg 3
Move ring 7 from peg 1 to peg 2
Move ring 5 from peg 3 to peg 1
Move ring 6 from peg 3 to peg 2
Move ring 5 from peg 1 to peg 2
Move ring 8 from peg 1 to peg 3
Move ring 5 from peg 2 to peg 3
Move ring 6 from peg 2 to peg 1
Move ring 5 from peg 3 to peg 1
Move ring 7 from peg 2 to peg 3
Move ring 5 from peg 1 to peg 2
Move ring 6 from peg 1 to peg 3
Move ring 5 from peg 2 to peg 3
Move ring 1 from peg 4 to peg 1
Move ring 2 from peg 4 to peg 3
Move ring 1 from peg 1 to peg 3
Move ring 3 from peg 4 to peg 1
Move ring 1 from peg 3 to peg 4
Move ring 2 from peg 3 to peg 1
Move ring 1 from peg 4 to peg 1
Move ring 4 from peg 4 to peg 3
Move ring 1 from peg 1 to peg 3
Move ring 2 from peg 1 to peg 4
Move ring 1 from peg 3 to peg 4
Move ring 3 from peg 1 to peg 3
Move ring 1 from peg 4 to peg 1
Move ring 2 from peg 4 to peg 3
Move ring 1 from peg 1 to peg 3
45 True
\$
```