質問する

に答える

この問題は基本的に再帰関数を用いる問題なので,私は再帰的な方法で解決した.
円板が1つの場合、スタート->ゴールポストで1回移動したことがわかります.
コードで表現すれば

def hanoi (원판개수, 시작, 보조, 목표)
	if 원판개수 == 1:
    	print(시작, 목표)

このように表現することができます.
では、2つのオリジナル(開始->アシスト、開始->ターゲット、アシスト->開始)では、コードでどのように実装されているかを見て、そのダイナミックさを見ることができます.
まず最初の円板移動を実現する(始点柱->補助柱)
最初に作成した関数(始点柱->ターゲット柱)の円板
オリジナルが2つの場合は、(始点柱->補助柱)に変更します.
すなわち、円板が1つの場合、2番目の柱が補助柱であり、円板が2つの場合、3番目の柱が補助柱である.これをコードとして実装すると、

def hanoi (원판개수, 시작, 보조, 목표)
	if 원판개수 == 1:
    	print(시작, 목표)
            
    # 목표지점이 보조지점으로 가고 보조지점이 목표지점으로 바꾼다
    hanoi(원판개수 - 1, 시작, 목표, 보조) 

このように体現することができます.
次に、コードで2番目の円板(始点->ターゲット点)を実現します.

def hanoi (원판개수, 시작, 보조, 목표)
	if 원판개수 == 1:
		print(시작, 목표)
    hanoi(원판개수 - 1, 시작, 목표, 보조) 
    
    # (시작 -> 목표)는 hanoi함수의 매개변수명과 같으니 그냥 사용해도 된다
	print(시작, 목표)

次に、最初の円板が補助柱に、2番目の円板がターゲット柱にあります.
では、2本目の柱の上の1枚目の円板(補助柱->ターゲット柱)で動かすだけです.

def hanoi (원판개수, 시작, 보조, 목표)
	if 원판개수 == 1:
    	print(시작, 목표)
        
   	hanoi(원판개수 - 1, 시작, 목표, 보조) 
	print(시작, 목표)
    
    # 시작을 보조기둥으로 목표는 목표기둥으로 한다면 다음과 같이 전달인자를 정의할수 있다.
    hanoi(원판개수 - 1, 보조, 시작 ,목표)

このようにコードで実現することができます.
Youtuber【Python Class】の【Python】アルゴリズムストーリー(01.ハノイタワー)
パイソンの授業で話した内容を見ると、もっと直感的に理解できます.

バックグラウンドの移動回数

すなわちk=1+(2 xhanoi(n-1))の式が得られる
hanoi(1)=1なので、上の式にn(原版個数)を代入すると
n = 1 -> k = 1
n = 2 -> k = 3
n = 3 -> k = 7
n = 4 -> k = 15
n = 5 -> k = 31
...
すなわちkは2のn乗−1の式である

コード実装

def hanoi(n, 시작, 보조, 목표):
  if n == 1:
    print(시작, 목표)
    return
  hanoi(n - 1, 시작, 목표, 보조)
  print(시작, 목표)
  hanoi(n - 1, 보조, 시작, 목표)

n = int(input())
print((2 ** n) - 1) # 총 옮긴 횟수
hanoi(n, 1, 2, 3)