入門-ハノイのタワーを移動

n個のディスクのハノイタワーを移動するためのディスク移動順序のアルゴリズムを出力する。

ハノイのタワールール

•始点柱から終点柱にn個の大きさの異なる円盤を移動する必要があります.
一度に1つのディスクしか移動できません.
•円盤を移動する場合は、1つの柱の上部から円盤を抽出し、それを別の柱の上部にのみ移動することができます(柱の中央から円盤を取り出すことはできません.また、抽出した円盤を別の柱の中央に挿入することはできません).
•ディスクを移動するときは、大きなディスクを小さなディスクに持ち上げることはできません.

ハノイのタワー

円板が1つの場合(1回掛け)
1番柱の円盤を3番柱に移すと終わりです.(1 → 3)

ディスクが2つの場合(3回掛け)
1番柱の一番上の円盤を2番柱に移します.(1 → 2)
1番柱に残っている大きな円盤を3番柱に移します.(1 → 3)
2番柱に残っている円盤を3番柱に移す.(2 → 3)

3つの

円板の場合(3+1+3=7回)
ハノイの塔規によると、一度に2つの円盤を運ぶことはできないが、私たちはすでに2つの円盤の時、ハノイの塔がどのように解けたのかを知っていて、その方法に従えばいい.
1番柱の3つの円盤のうち、上の2つの円盤を空の2番柱(補助柱)に移動します.(1→3、1→2、3→2)実際に円盤が3回移動しています
1号機に残っている大きな円盤を3番柱に移す.(1 → 3)
今回は2番柱の2つの円盤を3番柱に移します.(2→1,2→3,1→3)実際に円盤が3回移動した

n回汎用>>再帰呼び出しを使用可能

n個の円盤が

であるとき、

1号柱のn-1個の円盤を2号柱に移動します(n-1個のハノイ塔の問題を解きます).

1号柱に残っている最大円盤を3号柱(1→3)に移す.

2号柱のn−1個の円盤を3号柱に移動した(n−1個のハノイ塔の問題を解く).

ディスクが1つある場合は移動が終了します(終了条件)

ハノイのtopアルゴリズム

ディスクが1つしかない場合は、[終了条件](End Condition)になります.n個のディスク問題を解くにはn−1個のディスク問題を解く必要があり,これが「より小さな値で自分を呼び出す」プロセスである.従って、この問題は典型的な再帰呼び出しアルゴリズムに相当する.

# 하노이의 탑
# 입력: 옮기려는 원반의 개수 n
#       옮길 원반이 현재 있는 출발점 기둥 from_pos
#       원반을 옮길 도착점 기둥 to_pos
#       옮기는 과정에서 사용할 보조 기둥 aux_pos
# 출력: 원반을 옮기는 순서
 
def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1: # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
        print(from_pos, ”->“, to_pos)
        return
 
    # 원반 n -1개를 aux_pos로 이동(to_pos를 보조 기둥으로)
    hanoi(n -1, from_pos, aux_pos, to_pos)
    # 가장 큰 원반을 목적지로 이동
    print(from_pos, ”->“, to_pos)
    # aux_pos에 있는 원반 n -1개를 목적지로 이동(from_pos를 보조 기둥으로)
    hanoi(n - 1, aux_pos, to_pos, from_pos)
 
print(“n = 1”)
hanoi(1, 1, 3, 2) # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)

print(“n = 2”)
hanoi(2, 1, 3, 2) # 원반 두 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)

print(“n = 3”)
hanoi(3, 1, 3, 2) # 원반 세 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)

運転結果

n = 1		# hanoi(1, 1, 3, 2)
1 -> 3		# print(1,”->“,3)

n = 2		# hanoi(2, 1, 3, 2)  
1 -> 2		# hanoi(1, 1, 2, 3)  
1 -> 3		# print(1,”->“,3)
2 -> 3		# hanoi(1, 2, 3, 1)

n = 3
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

アルゴリズム解析

入力サイズ、すなわち、タワーの層数が高いほど、円盤がより多く移動します.
n階のハノイタワーを運ぶには、原盤を(2 nリットル-1)回運ぶ.同様に,nが大きくなると−1はあまり意味がなく,O(2 n)で表すことができる.これは2にnを乗じた値で,nが大きくなるにつれて幾何級数が増加する.
移動回数:2 x H(n-1)+1
H(n) = 2H(n-1) + 1
H(1) = 1
H(2) = 2 H(1) + 1 = 2 + 1 = 3
H(3)=2 H(2)+1=2 x 3+1=4(2の2勝)+2+1=7
H(4)=2 H(3)+1=2 x 7+1=8(2の3勝)+4(2の2勝)+2+1=1=15…

等比数列の和式

を用いる