## 2018年12月15日土曜日

### 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 hanoi1(ring_number: int, peg1: int, peg2: int, peg3: int, peg4: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi1(ring_number - 2, peg1, peg3, peg4, peg2)
print(f'Move ring {ring_number - 1} from peg {peg1} to peg {peg3}')
num_moves += 1
print(f'Move ring {ring_number} from peg {peg1} to peg {peg4}')
num_moves += 1
print(f'Move ring {ring_number - 1} from peg {peg3} to peg {peg4}')
num_moves += 1
num_moves += hanoi1(ring_number - 2, peg2, peg1, peg3, peg4)
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 += hanoi1(ring_number // 2, peg1, peg2, peg3, peg4)
num_moves += hanoi(ring_number // 2, ring_number // 2,
peg1, peg2, peg3)
num_moves += hanoi1(ring_number // 2, peg4, peg1, peg2, peg3)
return num_moves

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

```\$ ./sample2.py
Move ring 1 from peg 1 to peg 4
Move ring 2 from peg 1 to peg 2
Move ring 1 from peg 4 to peg 2
Move ring 3 from peg 1 to peg 3
Move ring 4 from peg 1 to peg 4
Move ring 3 from peg 3 to peg 4
Move ring 1 from peg 2 to peg 3
Move ring 2 from peg 2 to peg 4
Move ring 1 from peg 3 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 3
Move ring 2 from peg 4 to peg 1
Move ring 1 from peg 3 to peg 1
Move ring 3 from peg 4 to peg 2
Move ring 4 from peg 4 to peg 3
Move ring 3 from peg 2 to peg 3
Move ring 1 from peg 1 to peg 2
Move ring 2 from peg 1 to peg 3
Move ring 1 from peg 2 to peg 3
33 True
\$
```