[白俊]1914:ハノイタワー

質問する

に感銘を与える

この問題は遠くのハノイタワーの移動回数を印刷し、円盤数が20個を超えると、移動する柱がどうなるかということです.
まず、ハノイタワーを再理解する上で最も重要なのは、関数を再回帰する場合、再回帰が完了した後、再回帰関数を呼び出す場所に戻ることです!<=このコンセプトが一番!
これにより、呼び出した場所に再帰関数をロードし、再帰ループがすべて終了した後、次のコードを実行します.ハノイタワーは
コードは大きく4つの部分に分かれています.
1.最大ディスク開始->ターゲット(ディスクが1つしか残っていない場合-実際の移動部分)
2.最大ディスク以外のすべてのディスクを開始->2番目(再帰-1.実行まで)
3.最大ディスクの開始->ターゲット(ディスクが1つしか残っていない場合-実際の移動部分)
4.1つのディスク数を除いて、補助->ターゲット(再帰-1.実行まで)
また、衝突を経験した部分は、河内塔の移動回数を求めることです.
数式があるだけです.2 ** (원반 개수) - 1これはカウントダウンする必要はありません
カウントと移動の両方を印刷するために、hanoi関数の戻り値の個数が2つのjuniotupleを資料型としてエラーが発生しました.
いっそレンタカー代をあげました.

ハノイタワー

Pythonコード

MOVE_MESSAGE = "{}번 원반을 {}에서 {}로 이동"


def move(N, start, destination):
    print(MOVE_MESSAGE.format(N, start, destination))


def hanoi(n, start, destination, via):
    """
    하노이의 탑 규칙에 따라 원반을 옮기고,
    옮길 때마다 원반의 시작 위치와 이동한 위치를 출력합니다.
    마지막으로 총 이동 횟수를 반환합니다.
    :params
        n: 총 원반 개수
        start: 시작 기둥
        destination: 도착 기둥
        via: 보조 기둥:
    :return count:
    """
    # 원반이 1개일 때 시작 기둥에서 도착 기둥까지 한 번에 이동
    if n <= 1:
        move(1, start, destination)
        return 1

    count = 0
    # 원반 n-1개를 시작 기둥에서 보조 기둥으로 이동
    count += hanoi(n - 1, start, via, destination)

    # 가장 큰 원반을 시작 기둥에서 도착 기둥으로 이동
    count += 1
    move(n, start, destination)

    # 원반 n-1개를 보조 기둥에서 도착 기둥으로 이동
    count += hanoi(n - 1, via, destination, start)

    return count


if __name__ == '__main__':
    n = 3
    start = 1
    destination = 3
    via = 2

    total_count = hanoi(n, start, destination, via)
    print('총 이동 횟수:', total_count)


'''
출력 결과

1번 원반을 1에서 3로 이동
2번 원반을 1에서 2로 이동
1번 원반을 3에서 2로 이동
3번 원반을 1에서 3로 이동
1번 원반을 2에서 1로 이동
2번 원반을 2에서 3로 이동
1번 원반을 1에서 3로 이동
총 이동 횟수: 7
'''

コメントサイト
https://www.acmicpc.net/problem/1914

正しいコード

import sys

def move(s,d):
    print(s, d, sep =" ")

def hanoi(n, s, d, v):
    m = '' # 어디에서 어디로 이동했는지 저장
    if n <= 1:
        move(s, d)
        return 1
    
    count = 0
    count += hanoi(n-1, s, v, d) # n-1개를 시작 -> 보조
    
    count += 1 # 가장 큰 원반: 시작 -> 목표
    move(s,d)
    
    count += int(hanoi(n-1, v, d, s)) # n-1개를 보조 -> 목표
    
    return count

n = int(sys.stdin.readline())
s = 1
d = 3
v = 2

print(2**n-1) # 원반이 n개일 때 움직이는 횟수는 2의 n승 -1!

if n <= 20:
    hanoi(n, s, d, v) # 20 이하일 때 하노이 함수를 실행하면 move() 함수에서 알아서 print가 됨!

数式を使わずに回数を求める方法

def m(n):
	if n == 1:
    	return 1 # 마지막 원반은 어디든지 한 번만 움직이면 되므로 1을 리턴해줌
    return 2 * m(n-1) + 1
    # 1을 더해준 건 가장 큰 원반을 처음 -> 끝
    # 2를 곱해준 건 재귀를 실행해주는 게 두 번이어서

2つのコールバック値エラーコード

import sys

def hanoi(n, s, d, v):
    m = '' # 어디에서 어디로 이동했는지 저장
    if n <= 1:
        m += str(s) + " " + str(d) + "\n"
        return 1
    
    count = 0
    count += hanoi(n-1, s, v, d) # n-1개를 시작 -> 보조
    
    count += 1 # 가장 큰 원반: 시작 -> 목표
    m += str(s) + " " + str(d) + "\n"
    
    count += int(hanoi(n-1, v, d, s)) # n-1개를 보조 -> 목표
    
    return m, count

n = int(sys.stdin.readline())
s = 1
d = 3
v = 2

m, count = hanoi(n, s, d, v)
print(count)
print(m)