精华内容
下载资源
问答
  • 汉诺塔非递归实现

    2011-11-15 16:35:16
    汉诺塔非递归实现,估计课后作业应该有的O(∩_∩)O~
  • 汉诺塔非递归实现 C语言版

    千次阅读 多人点赞 2019-11-01 00:10:51
    汉诺塔非递归实现 C语言版 我上一篇博客是汉诺塔C语言递归实现,非递归和递归想法一样。这里不再赘述,直接链接转到: 汉诺塔递归实现 C语言版 递归实现固然好理解,但是n的值越大,空间和时间上都是极大的消耗,...

    汉诺塔非递归实现 C语言版

    我上一篇博客是汉诺塔C语言递归实现,非递归和递归想法一样。这里不再赘述,直接链接转到:

    汉诺塔递归实现 C语言版

    递归实现固然好理解,但是n的值越大,空间和时间上都是极大的消耗,最终可能导致程序直接崩溃。
    在以后的做题或者是面试中,不推荐用递归方法做,所以要写出对应的非递归方法。

    某次上课无意间听到老师说了这样一句话:任何递归法都可以用循环的方法进行非递归实现,然后回头找了找汉诺塔非递归的资料,整理整理,搞出了一个c实现的非递归方法

    #include<stdio.h>
    #include <stdlib.h>
    #define MaxSize 100
    typedef struct{
         int N;
         char A;        //起始柱
         char B;        //借助柱
         char C;        //目标柱
    }ElementType;
    typedef struct {
        ElementType Data[MaxSize];
        int top;
    }Stack;//汉诺塔问题的结构类型
    void Push(Stack *PtrS, ElementType item){
         //入栈操作
         if (PtrS->top == MaxSize)
         {
             printf("The stack is full!\n");
             return;
         }
         else
         {
             PtrS->Data[++(PtrS->top)] = item;
             return;
         }
    }
    ElementType Pop(Stack *PtrS){
        if (PtrS->top == -1)
          {
              printf("The stack is empty!\n");
              exit(1);   //直接终止程序,一般不会出现这个错误
          }
          else
          {
              PtrS->top--;
             return (PtrS->Data[PtrS->top + 1]);        //或者是return PtrS->Data[PtrS->top--];
          }
    }
    //借助栈的非递归实现
     void Hanoi(int n){
        ElementType P, toPush;
        Stack S;
         
        P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';
        S.top = -1;
    
         Push(&S, P);
         while (S.top != -1)        //当堆栈不为空时
         {
             P = Pop(&S);//出栈
             if (P.N == 1)//当只剩一个盘子时,直接由当前柱移动到目的柱
                 printf("%c -> %c\n", P.A, P.C);
             else
             {
                 toPush.N = P.N - 1;
                 toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;
                 Push(&S, toPush);        //将第三步(n - 1, b, a, c)入栈
                 toPush.N = 1;
                 toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;
                 Push(&S, toPush);        //将第二步1, a, b, c)入栈
                 toPush.N = P.N - 1;
                 toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;
                 Push(&S, toPush);        //将第一步(n - 1, a, c, b)入栈
             }
         }
     }
    int main(){
        int n;
        scanf("%d", &n);
        if (n <= 0)return 0;
        else Hanoi(n);
    }
    

    还是三个步骤:
    1.将n-1个盘子由a柱借助c柱移动到b柱
    2.将最下面的盘子由a柱直接移动到c柱
    3.将那n-1个盘子在由b柱借助a柱移动到c柱

    因为这个是出栈时的操作,所以入栈时要到着写

    简要解释一下(因为跟递归思路差不多)

    如果n不等于一时,就意味着,以上的n-1个盘子,都要做上述所说的三个步骤,知道n等于1时,直接移动到目的柱。
    因此,移动次数最多的是最上边的那个盘子,移动次数最少的是最下面的那个盘子,只需要移动一次

    利用结构体数组更便于理解。

    本文为原创,如有问题欢迎评论区留言。

    展开全文
  • #include stdio.h>#include dos.h>#include stdio.h>#define JISHU 1#define OUSHU 2#define MAX 9#define LEFT -1#define RIGHT 1/* /* ////////////////////////////////////////////////////////// */ */void ini

    #include <stdio.h>
    #include <dos.h>
    #include <stdio.h>
    #define JISHU 1
    #define OUSHU 2
    #define MAX 9
    #define LEFT -1
    #define RIGHT 1

    /* /* // */ */

    void init(int plate, char far *p); /* initialize the graph */
    void move(int id,int type, char far *p); /* move the plate */
    void power(int plate,long power_s[]); /* initialize the power_s[] */
    void start(char far *p); /* start moving */
    int scan(int base, char far *p);
    void draw (int base, int length, char far *p);

    int plate=100; /* the number of the plate */
    int type=JISHU; /* 判断plate是奇数还是偶数 */
    long power_s[MAX+1]={0}; /* 提前记录间隔数,以降低调用函数的损耗*/
    int count = 0;

    int base_1[31]={0};
    int base_2[31]={0};
    int base_3[31]={0};
    int n_1=0,n_2=0,n_3=0;
    int time;
    /* /* /*/ */

    void main(void)
    {
        char far *p;
        union REGS r;
        r.h.al=0x13;
        r.h.ah=0;
        int86(0x10,&r,&r) ;
        p=(char far *)(0xa0000000l);
        
        while(plate>MAX || plate<1)
        {
            printf("please input the number of the plate(1~%d)",MAX);
            scanf("%d",&plate);
        }

        printf("please input the delay time(0~~~10000):");
        scanf("%d",&time);

        init(plate, p); /* 初始化图形 */

        if(plate%2==0)
            type=OUSHU;
        else type=JISHU;

        power(plate,power_s);
        start(p); /* 开始移动 */
        getchar();
    }

    /* /* */ */

    void start(char far *p)
    {
        int temp[1024]; /* 把移动步骤放入temp中*/
        long i=1; /* 循环变量 */
        long n=1; /* 首次将要移动的盘子 */
        
        for(n=1;n<=plate;n++)
        {
          for(i=power_s[n-1]+1;i<power_s[plate]+1;)/* 第n个盘子将在第i次移动 */
            {
                temp[i]=n;
                i=i+power_s[n]+1;
            }
        }
        for(i=1;i<=power_s[plate];i++) /* 开始移动*/
        {
            move(temp[i],type,p);
        }
    }

    /* / */
    /* */
    /* */
    /* 以下为图像处理部分 */
    /* */
    /* / */
    void init(int plate, char far *p)
    {
        int i=0;
        int k;

        system("cls");
        for (;i<=200; i++) /* 1 */
        {
            *(p+50+320+320*i)=3;
        } /* 2 */
        for (i=0;i<=200; i++)
        {
            *(p+160+320+320*i)=3;
        }
        for (i=0;i<=200; i++) /* 3 */
        {
            *(p+265+320+320*i)=3;
        }


        for (k=0; k<plate; k++)
        {
            for (i=k; i<=100-k; i++)
            {
                *(p+i+320*(195-4*k))=1;
            }
            delay (time);
        }
        k=0;
        for (i=plate;i>=1;i--)
        {
            base_1[k++] = i;
        }
        n_1 = k-1;
    }

    /* /* / */ */


    int scan(int base, char far *p)
    {
        int x = 0;
        int y = 0;
        int x_l;
        int length = 0;

        if (base == 1)
            x = 49;
        if (base == 2)
            x = 159;
        if (base == 3)
            x = 264;

        for (y=0; y<=199; y++) /*scan the y*/
        {
            if (*(p+x+320*y) == 1)
                break;
        }

        x_l = x-49; /*scan the length*/
        for (;;)
        {
            if (*(p+x_l+320*y)==1)
                break;
            x_l++;
        }
        for (;;)
        {
            if (*(p+x_l+320*y)!=0)
            {
                *(p+x_l+320*y)=0;
                delay (time);
                x_l++;
                length++;
            }
            else
                break;
        }
        length--;

        return length;

    }

    void draw (int base, int length, char far *p)
    {
        int x = 0;
        int y = 0;
        int x_l;

        if (base == 1)
            x = 49;
        if (base == 2)
            x = 159;
        if (base == 3)
            x = 264;

        for (y=0; y<=200; y++) /*scan the y*/
        {
            if (*(p+x+320*y) == 1)
                break;
        }

        y-=4;

        x_l = x-49+(100-length)/2;

        for (;length>=0;length--)
        {
            *(p+x_l+320*y)=1;
            x_l++;
            delay (time);
        }
        

    }

    void move(int id, int type, char far *p)
    {
        int base;
        int length;
        int direct;

        if(type==OUSHU)
        {
            if(id % 2==0)
                direct=LEFT;
            else
                direct=RIGHT;
        }
        else
        {
            if(id % 2==0)
                direct=RIGHT;
            else
                direct=LEFT;
        }

        if (id == base_1[n_1]) /*which base has the id plate*/
            base = 1;
        else if (id == base_2[n_2])
            base = 2;
        else if (id == base_3[n_3])
            base = 3;
        else
        {
            printf ("Guozhen is GuaWaZi/n");
            getchar();
            exit (0);
        }

        length = scan (base, p); /*scan the length of the id plate and disdraw the plate*/

        if (base == 1) /*clear the stack*/
            n_1--;
        else if (base == 2)
            n_2--;
        else
            n_3--;

        if (direct == LEFT)
        {
            if (base == 1)
                base = 3;
            else
                base --;
        }
        else
        {
            if (base == 3)
                base = 1;
            else
                base ++;
        }

        draw (base, length, p); /*draw the plate*/

        if (base == 1) /*add the stack*/
        {
            n_1++;
            base_1[n_1]=id;
        }
        else if (base == 2)
        {
            n_2++;
            base_2[n_2]=id;
        }
        else
        {
            n_3++;
            base_3[n_3]=id;
        }

        count++;
        printf ("/b/b/b/b/b/b%d",count);
    }

    /* /* //*/ */

    void power(int plate,long power_s[])
    {
        int i=1;

        for(i=1;i<=plate;i++)
        {
            power_s[i]=(power_s[i-1]+1)*2-1;
        }
    }

     
    展开全文
  • Hanio 汉诺塔的递归及非递归实现
  • 汉诺塔的递归实现与非递归实现C++递归实现C++非递归实现 我是一名计算机专业学生,做汉诺塔问题的非递归实现遇到了很多问题,来CSDN找到了答案,觉得这个社区非常不错,我也准备在这上面记录下我的代码历程。 这位...

    汉诺塔的递归实现与非递归实现

    我是一名计算机专业学生,做汉诺塔问题的非递归实现遇到了很多问题,来CSDN找到了答案,觉得这个社区非常不错,我也准备在这上面记录下我的代码历程。
    这位大佬写得非常详细,我就不再画蛇添足了,大家可以去参观参观他(她)的个人博客和CSDN。
    

    链接: link.

    C++递归实现

    下面展示代码。

    #include<iostream>
    #include<iomanip>
    void hanoi(int n, char a, char b, char c);
    void move(char a, char b);
    
    using namespace std;
    
    int main() {
    	int N = 0;
    	cin >> N;
    	hanoi(N, 'a', 'b', 'c');
    	return 0;
    }
    
    void hanoi(int n, char a, char b, char c) {
    	if (n == 1)
    		cout << a << "-->" << b << endl;
    	else {
    		hanoi(n - 1, a, c, b);
    		move(a, b);
    		hanoi(n - 1, c, b, a);
    	}
    }
    void move(char a, char b) {
    	cout << a << "-->" << b << endl;
    }
    

    C++非递归实现

    下面展示 代码

    #include<iostream>
    #include<iomanip>
    
    using namespace std;
    
    int main() {
    	unsigned short int N{ 0 };
    	cin >> N;
    	long long int move_times{ 1 };
    	unsigned short int plate_number{ 1 };
    	long long int plate_move_times{ 1 };
    	long long int t{ 2 };
    	for (unsigned short int i{ 0 }; i < N; i++) {
    		move_times *= 2;
    	}
    	for (long long int i{ 1 }; i < move_times; i++) {
    		for (t = 2,plate_number = 1; plate_number <= N; plate_number++, t *= 2) {
    			if (i % t == t / 2) {
    				break;
    			}
    		}
    		plate_move_times = i / t;
    		if (N % 2 == plate_number % 2) {
    			if ((plate_move_times + 1) % 3 == 0) {
    				cout << "b -> a\n";
    			}
    			else if ((plate_move_times + 1) % 3 == 1) {
    				cout << "a -> c\n";
    			}
    			else if ((plate_move_times + 1) % 3 == 2) {
    				cout << "c -> b\n";
    			}
    		}
    		else {
    			if ((plate_move_times + 1) % 3 == 0) {
    				cout << "c -> a\n";
    			}
    			else if ((plate_move_times + 1) % 3 == 1) {
    				cout << "a -> b\n";
    			}
    			else if ((plate_move_times + 1) % 3 == 2) {
    				cout << "b -> c\n";
    			}
    		}
    	}
    	return 0;
    }
    
    需要注意的是数据类型,有的需要定义为 long long (int)才会符合要求。
    然后就是时间限制的问题,在c++中的输出流cout 和 endl 耗时会比较长,有两个解决方案,要么解绑,要么使用c的输出方法。可惜我都不会。。。
    
    展开全文
  • 3. 柱子上的盘子始终必须是大的在下面image.png汉诺塔问题的经典实现算法步骤如下:1.把 前N-1个盘子移动到过渡柱b2.把最低下的盘子从起始柱a移到终点柱c3.然后把b柱的N-1个盘子也移到终点柱c实现过程是一个递归的...

    一、问题描述及算法步骤

    汉诺塔问题的大意是有三根柱子a, b, c,现在a柱有N个盘子从下往上尺寸递减排列,要求:

    1. 将a上的盘子移动到c柱上;

    2. 每次移动一个盘子;

    3. 柱子上的盘子始终必须是大的在下面

    8e8a89a7c42f

    image.png

    汉诺塔问题的经典实现算法步骤如下:

    1.把 前N-1个盘子移动到过渡柱b

    2.把最低下的盘子从起始柱a移到终点柱c

    3.然后把b柱的N-1个盘子也移到终点柱c

    实现过程是一个递归的过程,递归公式为下:

    g(n) = 2g(n-1) + 1

    g(1) = 1

    (实际上可以通过解该递归方程得出 g(n) = 2^n - 1)

    二、编程实现

    python语言实现代码:

    def Hanoi(num, a, b, c):

    global count

    if num == 1:

    count += 1

    print "第%d步:盘%d 从%s柱-->柱%s" % (count, num, a, c)

    else:

    Hanoi(num - 1, a, c, b) # 以c作为过渡柱,将前N-1个盘子从a移到b

    # Hanoi(1,a,b,c)

    count += 1

    print "第%d步:盘%d 从%s柱-->柱%s" % (count, num, a, c) # 将最后一个盘子从a柱移到c柱

    Hanoi(num - 1, b, a, c) # 将b柱上的N-1个盘子移到c柱

    if __name__ == '__main__':

    count = 0

    n = input("请输入盘子的数目\n")

    Hanoi(n, 'A', 'B', 'C')

    print "总步数为%d" % count

    注:另外,汉诺塔问题也可以使用堆栈进行非递归实现。

    展开全文
  • 汉诺塔(递归实现与非递归实现

    千次阅读 2017-09-29 12:11:15
    汉诺塔 汉诺塔(又称河内塔)问题是源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片...我的代码(非递归实现): #include #include using namespace
  • 汉诺塔递归实现:#include&lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;string.h&gt; #include&lt;algorithm&gt; using namespace std; void dfs(int n,int now,int to,...
  • 适应于大学生学习算法
  • 当然,目前本菜鸟不知道怎么降低时间复杂度,现在只知道把汉诺塔递归转换成栈。(其实本质没变,时间复杂度不变,只是节省了一丢丢空间) //今天懒,细节先不说了。大概要注意一下入栈和出栈顺序是反着的。
  • 汉诺塔非递归实现

    2019-10-19 22:35:53
    基于C++的汉诺塔非递归实现 (PTA习题) 借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为“c”),并保证每个移动...
  • 汉诺塔(Hanoi) 算法Java实现。通过三个函数,分别对Hanoi进行递归、非递归非递归规律实现
  • 汉诺塔的递归和非递归实现 借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为“c”),并保证每个移动符合汉诺塔...
  • 汉诺塔递归实现

    2021-03-15 10:01:56
    7-17 汉诺塔递归实现 (25 分) 借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为“c”),并保证每个移动符合...
  • C#汉诺塔非递归

    2015-01-05 11:47:30
    非递归算法,用栈解决问题,C#语言,来解决汉诺塔移动问题
  • 汉诺塔递归与非递归实现 背景介绍 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天...
  • 汉诺塔-汉诺塔非递归实现源码和原理讲解---从网上整理的
  • 利用二叉树法,实现汉诺塔非递归,根据盘子数和第几步,快速得到每一步移动的操作,速度快,省内存。已经经过调试运行,算法思想参见http://wenku.baidu.com/view/81a05a80e53a580216fcfeba.html,本人源码是根据...
  • 汉诺塔非递归算法分析与实现

    千次阅读 2015-07-21 22:37:25
    下面,本文讨论了汉诺塔问题的非递归算法,核心内容就是栈的使用技巧。 首先,对于每个柱子来说,就是一个栈,这个栈有个特点就是,大数放在下面,小数放在上面。在首次建立栈时,我们可以先存储好这些数据,假设...
  • 用栈来实现汉诺塔,要明白递归就是栈的重要应用之一,递归是系统自动调用栈来处理。
  • 汉诺塔绝对是递归最经典的例子,具体的解释不多说了,直接上代码: #include <iostream> #include <cstdio> #include <cmath> using namespace std; void move(int id, char x, char y) { ...
  • 汉诺塔非递归实现,c++实现的,很简单,只有50多行,从递归的汉诺塔改编而来,将原来递归时的参数状态保存在栈中,入栈代替递归,出栈代替递归返回。
  • 汉诺塔问题的非递归实现及其思考 文章目录汉诺塔问题的非递归实现及其思考递归实现非递归实现思考 有关问题的递归实现和非递归实现其实是我们理解计算机,或者说编程语言中关于函数调用的方式最好的方式之一,它让...
  • 汉诺塔非递归算法

    2017-11-08 01:09:00
    这两天讲《Web程序设计》,用JavaScript写了个汉诺塔非递归算法,觉得有点意思,放在这里吧! 传统的递归算法: <htmlxmlns="http://www.w3.org/1999/xhtml"> <head> <meta...
  • PTA 汉诺塔非递归实现 7-11 汉诺塔非递归实现 (25分) 借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,657
精华内容 1,462
关键字:

汉诺塔的非递归实现