c语言循环加数组实现汉诺塔问题

目录
  • 简介
  • 递归的汉诺塔解法(c语言)
  • 循环实现汉诺塔问题(c语言)

简介

汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归都可以改成循环,常规的做法是借助堆栈,但是我一想好像用循环加数组也可以实现,于是就有了本文,实现声明,本文最后出来的算法效率不高的,比直接用递归实现还要差很多,追求算法效率的同学就不用看这个了。
题目:假设有3个柱子,分别为A、B、C,A柱子上有数量为n个的空心圆盘,从上到下序号分别为1...n,要求把A柱子中的n个圆盘移动到C柱中,且序号大的盘子必须在在需要小的圆盘下方。
思路:如果只有1个圆盘需要移动,则直接从A柱移动到C柱,如果有n个圆盘(n>1)需要移动,则需要先把n-1个圆盘从A柱移动到B柱,再把第n个圆盘从A柱移动到C柱,最后把原来的n-1个圆盘从B柱移动到C柱。

例如:

将1个圆盘从A柱移动到C柱只需要1个步骤:

1. 把圆盘1从A移动到C

将2个圆盘从A柱移动到C柱需要3个步骤:

1. 把圆盘1从A移动到B
2. 把圆盘2从A移动到C
3. 把圆盘1从B移动到C

将3个圆盘从A柱移动到C柱需要7个步骤:

1. 把圆盘1从A移动到C
2. 把圆盘2从A移动到B
3. 把圆盘1从C移动到B
4. 把圆盘3从A移动到C
5. 把圆盘1从B移动到A
6. 把圆盘2从B移动到C
7. 把圆盘1从A移动到C

递归的汉诺塔解法(c语言)

可以看出下面的递归算法的时间复杂度为O(2^n),因为存在有调用2^n-2次递归调用和1次原生printf;而空间复杂度为O(n),因为运行时栈中最多会同时保存n个函数的调用信息。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void towers(int n, char from, char to, char aux);
int main() {
    towers(3, 'A', 'C', 'B');
    return 0;
}

void showMove (int order, char from, char to) {
    printf("move disk %d from %c to %c\n", order, from, to);
}

void towers(int n, char from, char to, char aux) {
    if (n==1) {
        showMove(n, from, to);
        return;
    }
    towers(n-1, from, aux, to);
        showMove(n, from, to);
    towers(n-1, aux, to, from);
}

解释一下代码中参数的含义,void towers(int n, char from, char to, char aux)的意思是把n个圆盘从from柱子移动到to柱子,中间可以借用aux柱子。

分析一下上面的递归执行过程:

我们已经知道把1个圆盘从from移动到to的步骤是showMove(1, from, to);

而把2个圆盘从from移动到to的步骤是,先照着移动1个圆盘的操作,把前面1个圆盘从from移动到aux,再把第2个圆盘从from移动到to,最后按照移动1个圆盘的操作,把刚才的1个圆盘从aux移动到to。

同理,把3个圆盘从from移动到to的步骤是,先照着移动2个圆盘的操作,把前面2个圆盘从from移动到aux,再把第3个圆盘从from移动到to,最后按照移动2个圆盘的操作,把刚才的2个圆盘从aux移动到to。

所以,把n个圆盘的操作从from移动到to的步骤是,先照着移动n-1个圆盘的操作,把前面n-1个圆盘从from移动到aux,再把第n个圆盘从from移动到to,最后按照移动n-1个圆盘的操作,把刚才的n-1个圆盘从aux移动到to。

因此,我们可以记录移动1个圆盘的步骤,来得到移动2个圆盘的步骤,通过移动2个圆盘的步骤来得到移动3个圆盘的步骤,...最后得到移动n个圆盘的步骤。经过分析可以知道移动n个圆盘一共会有2^n-1个步骤

循环实现汉诺塔问题(c语言)

为了代码更加易懂,这里写了注释,修改了部分变量命名,统一用数组保存步骤集合,最后才输出。
可以看出这个算法的时间复杂度还是O(2^n),一共会执行2^(n+1)-1次setMoveAction语句和2^n-1次,printf语句,比起直接用递归还要复杂一些,而空间复杂度也是O(2^n),属于没什么用的算法,就是随便写写。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void towers(int n, char from, char to, char aux);
int main()
{
    towers(3, 'A', 'C', 'B');
    return 0;
}

void showMove(int order, char from, char to)
{
    printf("move disk %d from %c to %c\n", order, from, to);
}

typedef struct
{
    int order;
    char from;
    char to;
} MoveAction;

void setMoveAction(MoveAction *p, int order, char from, char to)
{
    p->order = order;
    p->from = from;
    p->to = to;
}

char compare_map(char c, char left, char right) {
    if (c == left) {
        return right;
    } else if (c == right) {
        return left;
    }
    return c;
}

void towers(int n, char from, char to, char aux)
{
    MoveAction *actions, action;
    int i, k, size;
    char f, t;

    actions = (MoveAction *)calloc(pow(2, n - 1) - 1, sizeof(MoveAction));
    setMoveAction(&actions[0], 1, from, to);
    size = 1;

    for (i = 2; i <= n; i++)
    {
        //本次循环会将把i个盘子从from移动到to的步骤记录到actions数组中
        // 设size是把i-1个盘子从from移动到to的步骤数,
        // 则本次循环中集合{actions[x] | 0 <= x <= size -1 }就是size是把i-1个盘子从from移动到aux的步骤集合,
        //而action[size]是把第i个盘子从from移到to,
        //而集合{actions[x] | size + 1 <= x <= 2*size }就应该是把i-1个盘存从aux移动到to的步骤集合

        // 倒序,先求解集合{actions[x] | size + 1 <= x <= 2*size }
        for (k = 0; k < size; k++)
        {
            action = actions[k];
            f = compare_map(action.from, from, aux);
            t = compare_map(action.to, from, aux);
            setMoveAction(&actions[k + size + 1], action.order, f, t);
        }
        // 求解action[size]
        setMoveAction(&actions[size], i, from, to);
        // 求解集合{actions[x] | 0 <= x <= size -1 }
        for (k = 0; k < size; k++)
        {
            action = actions[k];
            f = compare_map(action.from, to, aux);
            t = compare_map(action.to, to, aux);
            setMoveAction(&actions[k], action.order, f, t);
        }
        size = size * 2 + 1;
    }

    for (i = 0; i < size; i++)
    {
        showMove(actions[i].order, actions[i].from, actions[i].to);
    }
}

到此这篇关于c语言循环加数组实现汉诺塔问题的文章就介绍到这了,更多相关c语言 汉诺塔内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现汉诺塔游戏

    操作就是:A B 号码A的塔顶一层放在号码B的塔顶.如1(空格) 3 回车. 话说有人能把我这C的代码添加到QT界面框架上去么?  代码写的不好 ,维护性不够,只能玩8层的,写完以后发现很难拓展,软件工程,设计模式有待提高.... 里面提示输入等级的装B用了,没有实现,大家随便输入个个位数就可以玩了. stackfunc.c #include"STACK.h" #include<stdio.h> extern ceng CENG[SIZE]; //数据入栈 void pus

  • 带你理解C语言中的汉诺塔公式

    目录 汉诺塔公式 汉诺塔问题在数学层面的公式: C语言递归公式 两层汉诺塔 三层汉诺塔 总结 汉诺塔公式 汉诺塔问题在数学层面的公式: 不用说,你看到这个公式一定一脸懵逼,我现在来讲解这个公式的作用. 先来回想一下大象放冰箱要几步,三步吧,打开冰箱,放进去,关上门就行了,我们先不要去思考一些细碎的步骤,将一个复杂的问题先简单化,再慢慢去分析. 那汉诺塔问题也是同样的简单三步:(假设有n个盘子) 一.把最大的盘子留在A柱,然后将其他的盘子全放在B柱. 二.把最大的盘子放到C柱. 三.然后将B柱上的

  • C语言实现汉诺塔(图文详解)

    目录 思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码 运行截图 总结 汉诺塔的游戏规则: 有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过中间柱子B(B柱子作为中介)移动到C柱子上 当A只有一个环的时候: A->C 当A只有两个环的时候: A->B A->C

  • C语言编程递归算法实现汉诺塔

    汉诺塔 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔.庙宇和众生也都将同归于尽. 这个传说挺有意思的,这个传说

  • c语言 汉诺塔算法代码

    复制代码 代码如下: #include<stdio.h> void move(char a,char b) {     printf("%c->%c\n",a,b); } void han(int n,char a,char b,char c) {     if(n>0)     {         han(n-1,a,c,b);         move(a,b);         han(n-1,c,b,a);     } } int main() {   

  • C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系 汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,

  • C语言汉诺塔的简单了解

    汉诺塔详解 以4层为例 以下为我的拙见,还希望大佬雅正 要把汉诺塔移动到c 需要把1,2,3层移到b 把4移动到c 在吧123移动到b 但是一次只能动一块 所以我们目前要做的就是把上面三块移动到b 那就需要把1 2移动到c 由此我们可以推出要把1,2移动到c,只需要把1移动到b 这里我们发现有很多重复的自相似动作 我们就可以设计递归 递归需要1,递归体 2 出口. 递归体 移动n-1个盘子和1个盘子和n个盘子过程都是相似的 但是每次放入的杆子不一样. 出口 n=1时只剩一个盘子,直接移动到c即可

  • C语言用递归函数实现汉诺塔

    目录 汉诺塔(Hanoi)是什么? 那么,C语言如何实现汉诺塔呢? 汉诺塔的基本思路是: 具体代码见下(注意点在代码下面): 总结 汉诺塔(Hanoi)是什么? 一个简单的汉诺塔就如上图所示,有三个放置点,放置物必须遵循上小下大的规则,依次将1中的放置物全部放置到3中.就比如该图中有4个放置物,若将A上的放置物全部移至C上,具体的步骤是:A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->

  • C语言递归思想实现汉诺塔详解

    目录 1.递归思想简介 2.汉诺塔问题 3.汉诺塔递归的c语言实现 总结 1.递归思想简介 在c语言中,程序调用自身的编程技巧称为递归( recursion). 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子. /* 递归求n的阶乘 */ int factorial(int n) //定义一个求阶乘的函数叫做factorial(),需要一个整形参数,返回一个整形值 { if (n <= 1) //递归结束的条件 { return 1; } else { ret

  • C语言编写汉诺塔游戏

    目录 汉诺塔的游戏规则: 当A只有一个环的时候: 当A只有两个环的时候: 当A只有三个环的时候: 思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码 运行截图总结 汉诺塔的游戏规则:   有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过C柱子(C柱子作为中介)移动到B柱子

随机推荐