汉诺塔问题【递归】

汉诺塔问题是一个递归的经典问题

问题描述:

  有x,y,z三根柱子,在x柱子上有按照大在下,小在上的规则,放着64个套筒,现在要将64个套筒借助柱子y移到柱子z上,且每次只能移动一个套筒,每个柱子上的套筒每时每刻只能按照大套筒在下面,小套筒在上面的规则放着,请问一共要移动多少次才能完成该项任务?

解题思路:

  我们一般会这样想,先把上面63个套筒从x移到y,然后再将第64个从x移到z,最后再将63个从y移动到z,任务完成。

  那么63个套筒怎么移动呢?同样,先把62个套筒从x移到y.。。。。

代码详解:

1 //一共64个盘子 2 void hanota(char a, char b, char c,int n) { 3 4 if (n == 1) 5 cout << a << "->" << c << endl; //将第64个从a,移到c 6 else { 7 hanota(a, c, b, n - 1);//先将上面63个盘子移到b 8 hanota(a, b, c, 1);//然后将第64个从a,移到c 9 hanota(b, a, c, n - 1);//最后将b上的63个移到c 10 } 11 } 12 13 14 void T014() { 15 char a = 'x'; 16 char b = 'y'; 17 char c = 'z'; 18 hanota(a, b, c, 64); 19 20 }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsxfyy.html