Python은 하노이 타워 재귀 알고리즘을 구현합니다.

제가 재귀를 배울 때 하노이 타워라는 운동이 있었습니다. 하노이 타워는 컴퓨터 재귀 알고리즘을 배우기 위한 고전적인 입문 사례여야 하므로 블로그에 제 의견을 표현해야겠다고 생각했습니다. 아직 이 마크다운 에디터를 어떻게 사용하는지 모르겠고, 형식이 좀 못생겼을 수도 있으니 양해 부탁드립니다.

인터넷에서 하노이 탑 사진을 발견했는데, 하노이 탑은 가운데 기둥을 이용하여 가장 왼쪽 기둥에 원반을 큰 것부터 작은 것 순으로 쌓아서 사용합니다. 직설적으로 말하면 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 중국어 웹사이트를 주목하세요!