【数据结构复习】汉诺塔：快速回忆汉诺塔问题

2023-07-09 21:01| 来源: 网络整理| 查看: 265

题目

百度百科题目

题解

众所周知这是一个递归问题（我们只需要注意两点：①什么时候退出递归 ②怎么从n-1推出n

①什么时候退出递归：很明显啦，n==1的时候，我们直接把A位置的唯一盘子移到C上，大功告成。 ②怎么从n-1推出n：要完成第n步的转移，我们可以——— 1》把n-1个盘子从A移到B，借助C 2》把剩下的唯一一个盘子，也就是第n个盘子从A移到C 3》把n-1个盘子从B移到C，借助A 第一步和第三步其实就是一个n-1的汉诺塔问题，这样我们就写好了递归啦！大功告成，代码如下：

#include void hanoi(int n, char source, char target, char auxiliary) { // 递归基 if (n == 1) { printf("Move disk 1 from %c to %c\n", source, target); return; } // 将 n-1 个盘子从源柱移动到辅助柱 hanoi(n - 1, source, auxiliary, target); // 将最大盘子从源柱移动到目标柱 printf("Move disk %d from %c to %c\n", n, source, target); // 将 n-1 个盘子从辅助柱移动到目标柱 hanoi(n - 1, auxiliary, target, source); } int main() { int n; printf("Enter the number of disks: "); scanf("%d", &n); printf("Steps to solve the Hanoi Tower problem with %d disks:\n", n); hanoi(n, 'A', 'C', 'B'); return 0; }

【本文地址】

公司简介

联系我们