開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の12章(ひねりを加えたバラモンの塔)、練習問題(パズル問題3)を取り組んでみる。
コード(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
def clockwise(ring_number: int, start_peg: int) -> int:
num_moves = 0
if ring_number > 0:
end_peg = start_peg % 3 + 1
other_peg = 6 - start_peg - end_peg
num_moves += counterclockwise(ring_number - 1, start_peg)
print(f'Move ring {ring_number} from peg {start_peg} to peg {end_peg}')
num_moves += 1
num_moves += counterclockwise(ring_number - 1, other_peg)
return num_moves
def counterclockwise(ring_number: int, start_peg: int) -> int:
num_moves = 0
if ring_number > 0:
other_peg = start_peg % 3 + 1
end_peg = 6 - start_peg - other_peg
num_moves += counterclockwise(ring_number - 1, start_peg)
print(
f'Move ring {ring_number} from peg {start_peg} to peg {other_peg}')
num_moves += 1
num_moves += clockwise(ring_number - 1, end_peg)
print(
f'Move ring {ring_number} from peg {other_peg} to peg {end_peg}')
num_moves += 1
num_moves += counterclockwise(ring_number - 1, start_peg)
return num_moves
def hanoi_ring(n: int) -> int:
num_moves = clockwise(n, 1)
return num_moves
if __name__ == '__main__':
num = hanoi_ring(3)
print(num, num == 15)
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample3.py Move ring 1 from peg 1 to peg 2 Move ring 1 from peg 2 to peg 3 Move ring 2 from peg 1 to peg 2 Move ring 1 from peg 3 to peg 1 Move ring 2 from peg 2 to peg 3 Move ring 1 from peg 1 to peg 2 Move ring 1 from peg 2 to peg 3 Move ring 3 from peg 1 to peg 2 Move ring 1 from peg 3 to peg 1 Move ring 1 from peg 1 to peg 2 Move ring 2 from peg 3 to peg 1 Move ring 1 from peg 2 to peg 3 Move ring 2 from peg 1 to peg 2 Move ring 1 from peg 3 to peg 1 Move ring 1 from peg 1 to peg 2 15 True $
0 コメント:
コメントを投稿