제가 재귀를 배울 때 하노이 타워라는 운동이 있었습니다. 하노이 타워는 컴퓨터 재귀 알고리즘을 배우기 위한 고전적인 입문 사례여야 하므로 블로그에 제 의견을 표현해야겠다고 생각했습니다. 아직 이 마크다운 에디터를 어떻게 사용하는지 모르겠고, 형식이 좀 못생겼을 수도 있으니 양해 부탁드립니다.
인터넷에서 하노이 탑 사진을 발견했는데, 하노이 탑은 가운데 기둥을 이용하여 가장 왼쪽 기둥에 원반을 큰 것부터 작은 것 순으로 쌓아서 사용합니다. 직설적으로 말하면 c는 원래의 a와 같아야 합니다
쓸데없는 소리는 그만하고 먼저 코드를 보여주자
def move(n, a, buffer, c): if(n == 1): print(a,"->",c) return move(n-1, a, c, buffer) move(1, a, buffer, c) move(n-1, buffer, a, c) move(3, "a", "b", "c")
먼저 이동 함수가 정의되고, 4개의 매개변수는 , 버퍼는 b 열이며 이름에서 알 수 있듯이 a를 c로 이동하는 버퍼입니다.
함수 코드를 읽어 보겠습니다
일반적인 재귀 작성 방법은 반드시 정지가 있어야 합니다. 재귀 루프의 조건이므로 a열의 플레이트 수가 1이라고 판단되면, 플레이트가 1개만 있을 때 재귀를 종료하고 반환할 수 있습니다. a열의 a는 c로 옮겨져야 합니다.재귀는 실제로 매우 추상적인 알고리즘입니다.A의 판을 생각하려면 추상적인 사고가 필요합니다. 즉, 윗판과 아랫판을
으로 표시하면 접시가 몇 개인지 상관없습니다. 우리의 작업은 매번 b 컬럼의 버퍼를 통해 c 컬럼으로 하단 플레이트를 이동하는 것입니다.
아이들은 장자가 왜 움직이는지 고민하고 있을 텐데요. 사실 이건 하노이 탑 게임을 직접 해보시면 규칙을 발견하게 되실 겁니다. 사실 이 게임은 위의 모든 방법을 끊임없이 생각하는 게임입니다. . b에 있는 것을 b로 옮기고, 마지막이자 가장 큰 것을 a에서 c로 옮긴 다음, b에 있는 것을 c로 옮기려고 노력하세요. b는 또한 빈 항목, 즉 a를 먼저 통과해야 합니다. 현재 b 위에 n-1개 항목을 저장한 다음 b 중 가장 큰 항목과 마지막 항목을 c로 이동하려면 규칙이 여기에 반영됩니다.
이제 추상적인 사고를 이용하여 나머지 코드를 해석해 보도록 하겠습니다.
move(n-1) , a, c, buffer)
이 코드는 방금 언급한 a열 위의 n-1개 항목이 먼저 작은 것부터 큰 것까지의 규칙에 따라 c를 거쳐 버퍼로 이동한다는 의미입니다. . 이 함수는 재귀로 들어갑니다.
move(1, a, buffer, c)
위 명령문이 실행되면, 즉 n-1 플레이트의 재귀적 이동이 완료된 후, Execution this 문은 a열의 판을 c열로 옮기는 것인데, 소위 밑판
move(n-1, buffer, a, c)
마지막 단계는 a에 있는 n-1 항목을 모두 버퍼로 옮기는 것이고, 하노이 타워 전체의 이동을 완료하려면 a에서 c로 이동해야 하므로 마지막 단계는 당연히 n-1을 옮기는 것입니다. 지금은 버퍼가 a를 통해 c열로 이동할 때
a열의 3을 예로 들어 전체 이동 과정을 적어보겠습니다
/** 我把3个盘子的汉诺塔全部通过代码演示,按缩进原则,每一个缩进即进一个递归函数,每打印一次即中止当前递归,也就是每个print 说明: 1.n = 3, n = 2, n = 1是每次执行if(n == 1)的结果,这里就不写判断了,相信童鞋们也能看懂,也就是n不等与1时就减1进入递归 2.请注意a,b,c柱每次进入函数的顺序,不要被形参带错路了,看准每次函数参数的实参 **/ move(3, "a", "b", "c") n=3: //开始从a上移动n-1即2个盘子通过c移动到b,以腾出c供a最后一个盘子移动 move(2, "a","c","b") n=2: //开始进行n=2的一个递归,把当前a('a')柱上的n-1个盘子通过c('b')移动到b('c') move(1, "a", "b", "c") n=1: //n=2的第一个递归完成,打印结果,执行当前子函数剩余代码 print("a", "->", "c") move(1, "a", "c", "b") n=1: print("a", "->", "b") move(1, "c", "a", "b") n=1: print("c", "->", "b") //到这里完成了a柱上面的n-1即是2个盘子的移动 //开始把a柱上最后一个盘子移动到c柱上 move(1, "a", "b", "c") n=1: print("a", "->", "c") //到这里完成移动a柱上的最后一个盘子到c柱上 move(2, "b", "a", "c") n=2: //开始进行n=2的第二个递归,即把当前b('b')的盘子(n-1个)通过a('a')移动到c('c')上 move(1, "b", "c", "a") n=1: //n=2 的第二个递归完成,打印结果并执行当前子函数的剩余代码 print("b", "->", "a") move(1, "b", "a", "c") n=1: print("b", "->", "c") move(1, "a", "b", "c") n=1: print("a", "->", "c") //到这里把b上的盘子通过a移动到c, //整个代码执行完毕,汉诺塔移动完成
최종 인쇄 결과는 다음과 같습니다.
아이들이 하노이 탑의 재귀 알고리즘 원리를 이해한 후 다음과 같이 작성할 수 있습니다. 여기 파이썬으로 재귀를 배웠기 때문에 아이들이 다른 언어를 사용해 구현할 수 있습니다. 하노이 타워는 프로그래밍에서 재귀의 원리를 이해하는 데 정말 도움이 됩니다. 자명하다!
하노이탑 재귀 알고리즘의 Python 구현과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!