当前位置：首页 > news >正文

讨论汉诺塔之谜

news 来源：原创 2024/5/6 18:48:43

汉诺塔是数学上的一个谜题。有三根杆子，一些不同大小的中间有孔的圆盘，可以按大小顺序套在杆子上，最小的在最上面，堆成类似锥形的结构。问题是怎么把一根杆子上的一堆圆盘移动到另一根杆子上，限定条件如下：

一次只能移动一个圆盘。

每一次移动步骤包括将一根杆子最上面的圆盘移开放到另一根杆子上圆盘的最上层（不能动下面的盘子）。

所有大圆盘的下面不能有比他小的圆盘。

算法步骤（有n个圆盘，三根杆子分别为A，B，C，要将所有盘子从A上移动到B上）

将A上面的n-1个圆盘移动到C上。

将A上面最后一个圆盘移动到B上。

将C上面的n-1个圆盘移动到B上。

从C上移动n-1个圆盘到B上我们如法炮制。一旦我们解决n=3的情况，我们就能解决任何数量的盘子了。

void towerOfHanoi(int n, char fromPeg, char toPeg, char auxPeg)
{
    //If only one disk, make a move and return :: base case
    if(n == 1)
    {
        printf("Move disk 1 from peg %c to peg %c ",fromPeg, toPeg);
        return;
    }
    //Move top n-1 disks from A to B, using C as auxiliary
    towerOfHanoi(n-1, fromPeg, auxPeg, toPeg);
 
    //Move remaining disks from A to C
    printf("\nMove disk %d from peg %c to peg %c ",n, fromPeg, toPeg);
 
    //Move n-1 disks from B to C using A as the auxiliary
    towerOfHanoi(n-1, auxPeg, toPeg, fromPeg);
}

假设我们传递这样的参数：

towerOfHanoi(3, 'A'. 'B', 'C');

输出如下：

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

注：代码不长，但理解代码的运行过程可能需要动一些脑筋，我在最后附上完整代码，或许你需要参考我前面的内容递归和内存分配（可视化）

#include<stdio.h>
#include<stdlib.h>
/*
Code obtained from

http://www.studyalgorithms.com
*/
void towerOfHanoi(int n, char fromPeg, char toPeg, char auxPeg)
{
    //If only one disk, make a move and return :: base case
    if(n == 1)
    {
        printf("Move disk 1 from peg %c to peg %c \n",fromPeg, toPeg);
        return;
    }
    //Move top n-1 disks from A to B, using C as auxiliary
    towerOfHanoi(n-1, fromPeg, auxPeg, toPeg);
 
    //Move remaining disks from A to C
    printf("Move disk %d from peg %c to peg %c \n",n, fromPeg, toPeg);
    /*
    Feel free to copy but please acknowledge studyalgorithms.com
    */
 
    //Move n-1 disks from B to C using A as the auxiliary
    towerOfHanoi(n-1, auxPeg, toPeg, fromPeg);
}

int main(void)
{
    printf("Enter the number of disks:- ");
    int disks;
    scanf("%d",&disks);
    towerOfHanoi(disks,'A','B','C');
    return 0;
}