首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 关于递归的问题！ [已结贴,结贴人:mei1977mei]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mei1977mei
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 揭贴率：
    发表于：2008-08-20 12:48:16 楼主
    Hanoi塔问题

        一块板上有三根针，A，B，C。A针上套有64个大小不等的圆盘，大的在下，小的在上。如图5.4所示。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。

    move(int n,int x,int y,int z)

    {

        if(n==1)

          printf("%c-->%c\n",x,z);

        else

        {

          move(n-1,x,z,y);

          printf("%c-->%c\n",x,z);

          move(n-1,y,x,z);

        }

    }

    main()

    {

        int h;

        printf("\ninput number:\n");

        scanf("%d",&h);

        printf("the step to moving %2d diskes:\n",h);

        move(h,'a','b','c');

    }

    这个程序实在想不明白！

    假设n=2；进入程序以后，首先它不满足f(i==1)，程序往下走，执行else，调用函数move(n-1,x,z,y);然后n=1执行if语句 输出a->b；这个时候程序该怎么走？做那件事情？这个程序的算法我明白，就是不知道程序具体怎么走！把a->b以后，程序是怎么把a->c，再把b->c的？

    想了很久都没想明白！自学真的很难！希望懂的朋友能够给个答案！

    先谢谢大家！


    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • babyvox1999
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 13:13:341楼 得分:0
    单步跟踪执行
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hqin6
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 13:32:532楼 得分:0
    汗，这不是汉诺塔问题么？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hqin6
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 13:33:223楼 得分:0
    典型的递归算法！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hqin6
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 13:37:524楼 得分:20
    假设n=2；进入程序以后，首先它不满足f(i==1)，程序往下走，执行else，调用函数move(n-1,x,z,y);---这里我们记个标记T

    然后n=1执行if语句 输出a->b；

    然后返回到标记T执行下面两句：

    printf("%c-->%c\n",x,z);

    move(n-1,y,x,z);

    就相当于：

    ----->move --------->
          |  \
          |  \
          |    \
          |    \
          printf()-
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hqin6
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 13:39:415楼 得分:0
    C/C++ code
    

----->move ---------> printf()---------->move()---------->
      ¦  \                                 |  \ 
      ¦   \                                |   \
      ¦    \                               |    \
      ¦     \                              |     \   
      printf()-                            printf()
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • k2eats
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 14:05:106楼 得分:0
    move(int n,int x,int y,int z)

    {

        if(n==1)

          printf("%c-->%c\n",x,z);

        else

        {

          move(n-1,x,z,y);

          printf("%c-->%c\n",x,z);

          move(n-1,y,x,z);

        }

    }
    n==2时候，不满足条件，执行else：move(1,x,z,y)，即从x移动一个塔块经z到y
    然后将最下面的最大塔块从x移到z即printf("%c-->%c\n",x,z);
    接着将执行move(1,y,x,z)即将上面的塔块从y移到Z
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lishuo102
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 14:45:097楼 得分:0
    汉诺塔算法啊，典型的递归问题
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jinjin666
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-20 15:19:328楼 得分:0
    汉诺塔问题
    目的：将所有的盘从X移动到Z；
    规则：任何时刻都必须是大盘在下。
    这可是经典递归程序，表面上很复杂，但用递归法竟然会如此简单。

    步骤分析：
    1.将其他盘移动到Y塔；
    2.将最大盘从X移动到Z塔；
    3.将其他盘从Y移动到Z塔，完成；
    至于怎么把其他盘移动到某盘，我们不用写代码 直接递归就行了，应为他和上面的问题相似，只不过盘数少了一个、盘的名字变了；
    当递归到只剩下一个盘时，直接挪过去问题解决了。以下是程序代码：

    using System;
    using System.Drawing;
    using System.Collections;
    using System.ComponentModel;
    using System.Windows.Forms;
    using System.Data;

    namespace hannuota
    {
    /// <summary>
    /// Form1 的摘要说明。
    /// </summary>
    public class Form1 : System.Windows.Forms.Form
    {
      private System.Windows.Forms.ListBox listBox1;
      private System.Windows.Forms.Button button1;
      private System.Windows.Forms.Button button2;
      private System.Windows.Forms.TextBox num;
      private System.Windows.Forms.Label label1;
      private System.Windows.Forms.Label label2;
      private System.Windows.Forms.Label label3;
      private System.Windows.Forms.Label label4;
      /// <summary>
      /// 必需的设计器变量。
      /// </summary>
      private System.ComponentModel.Container components = null;

      public Form1()
      {
      //
      // Windows 窗体设计器支持所必需的
      //
      InitializeComponent();

      //
      // TODO: 在 InitializeComponent 调用后添加任何构造函数代码
      //
      }

      /// <summary>
      /// 清理所有正在使用的资源。
      /// </summary>
      protected override void Dispose( bool disposing )
      {
      if( disposing )
      {
        if (components != null)
        {
        components.Dispose();
        }
      }
      base.Dispose( disposing );
      }

      #region Windows 窗体设计器生成的代码
      /// <summary>
      /// 设计器支持所需的方法 - 不要使用代码编辑器修改
      /// 此方法的内容。
      /// </summary>
      private void InitializeComponent()
      {
      this.listBox1 = new System.Windows.Forms.ListBox();
      this.button1 = new System.Windows.Forms.Button();
      this.button2 = new System.Windows.Forms.Button();
      this.num = new System.Windows.Forms.TextBox();
      this.label1 = new System.Windows.Forms.Label();
      this.label2 = new System.Windows.Forms.Label();
      this.label3 = new System.Windows.Forms.Label();
      this.label4 = new System.Windows.Forms.Label();
      this.SuspendLayout();
      //
      // listBox1
      //
      this.listBox1.ItemHeight = 12;
      this.listBox1.Location = new System.Drawing.Point(8, 8);
      this.listBox1.Name = "listBox1";
      this.listBox1.Size = new System.Drawing.Size(88, 160);
      this.listBox1.TabIndex = 0;
      //
      // button1
      //
      this.button1.Location = new System.Drawing.Point(16, 216);
      this.button1.Name = "button1";
      this.button1.Size = new System.Drawing.Size(56, 24);
      this.button1.TabIndex = 1;
      this.button1.Text = "Bulid";
      this.button1.Click += new System.EventHandler(this.button1_Click);
      //
      // button2
      //
      this.button2.Location = new System.Drawing.Point(16, 256);
      this.button2.Name = "button2";
      this.button2.Size = new System.Drawing.Size(56, 24);
      this.button2.TabIndex = 2;
      this.button2.Text = "Next";
      this.button2.Click += new System.EventHandler(this.button2_Click);
      //
      // num
      //
      this.num.Location = new System.Drawing.Point(48, 184);
      this.num.Name = "num";
      this.num.Size = new System.Drawing.Size(40, 21);
      this.num.TabIndex = 3;
      this.num.Text = "3";
      //
      // label1
      //
      this.label1.Location = new System.Drawing.Point(16, 192);
      this.label1.Name = "label1";
      this.label1.Size = new System.Drawing.Size(32, 16);
      this.label1.TabIndex = 4;
      this.label1.Text = "盘数";
      //
      // label2
      //
      this.label2.Location = new System.Drawing.Point(144, 264);
      this.label2.Name = "label2";
      this.label2.Size = new System.Drawing.Size(32, 16);
      this.label2.TabIndex = 5;
      this.label2.Text = "X";
      //
      // label3
      //
      this.label3.Location = new System.Drawing.Point(288, 264);
      this.label3.Name = "label3";
      this.label3.Size = new System.Drawing.Size(16, 16);
      this.label3.TabIndex = 6;
      this.label3.Text = "Y";
      //
      // label4
      //
      this.label4.Location = new System.Drawing.Point(424, 264);
      this.label4.Name = "label4";
      this.label4.Size = new System.Drawing.Size(24, 16);
      this.label4.TabIndex = 7;
      this.label4.Text = "Z";
      //
      // Form1
      //
      this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
      this.ClientSize = new System.Drawing.Size(512, 293);
      this.Controls.Add(this.label4);
      this.Controls.Add(this.label3);
      this.Controls.Add(this.label2);
      this.Controls.Add(this.label1);
      this.Controls.Add(this.num);
      this.Controls.Add(this.button2);
      this.Controls.Add(this.button1);
      this.Controls.Add(this.listBox1);
      this.Name = "Form1";
      this.Text = "Form1";
      this.Load += new System.EventHandler(this.Form1_Load);
      this.ResumeLayout(false);

      }
      #endregion

      /// <summary>
      /// 应用程序的主入口点。
      /// </summary>
      [STAThread]
      static void Main()
      {
      Application.Run(new Form1());
      }

      int n;char X,Y,Z;
      private System.Windows .Forms.Label[]tL;
      int I;
      int a,b,c;

      private void Form1_Load(object sender, System.EventArgs e)
      {
      X='X';Y='Y';Z='Z';
     
      }
      public void Hanio(int m,char x,char y,char z)
      {
      if (m==1)Move(x,1,z);
      else
      {
        Hanio(m-1,x,z,y);
        Move(x,m,z);
        Hanio(m-1,y,x,z);
      }
      }
      public void Move(char x,int m,char z)
      {
      listBox1.Items .Add ((n-m).ToString ()+" from "+x+" to "+z);
     
      }

      private void button1_Click(object sender, System.EventArgs e)
      {
      n=int.Parse (num.Text) ;
      listBox1.Items .Clear ();
     
      Hanio(n,X,Y,Z);

      InDisk(n);
      I=0;
      a=n;
      b=0;
      c=0;
      }
      void InDisk(int m)
      {
      int i;
      if (tL!=null)
      {
        for(i=0;i <tL.Length  ;i++)
        Controls.Remove (tL[i]);
      }
      tL=new Label [m];
      tL.Initialize ();

     
      for( i=0;i <m;i++)
      {
       
        tL[i]=new Label ();
       
       
        tL[i].BackColor =System.Drawing .Color .Magenta;
        tL[i].Text =i.ToString ();
        tL[i].Location  =new System.Drawing.Point(112+7*i, 240-20*i);
        tL[i].Size  =new System.Drawing.Size(120-14*i, 18);
       
        //Controls.Add (tL[i]);
        tL[i].Enabled =true;
        tL[i].Visible =true;
        tL[i].Show ();
       
      } 
      Controls.AddRange (tL);
      }

      private void pictureBox1_Click(object sender, System.EventArgs e)
      {
     
      }

      private void button2_Click(object sender, System.EventArgs e)
      {
      string t1,t2,t0;string s;
     
     
      if (I <listBox1.Items .Count)
      {
        s=listBox1.Items [I].ToString() ;
        t0=s.Substring (0,1);
        t1=s.Substring (7,1) ;
        t2=s.Substring (12,1) ;
        //textBox1.Text =t0;
        Rmove(t0,t1,t2);
        I++;
       
      }
      }
      void Rmove(string s0,string s1,string s2)
      {
      int numb;//,from,to;
      numb=int.Parse (s0);
        if(s1=="X")a--;
        if(s1=="Y")b--;
        if(s1=="Z")c--;
      if(s2=="X"){tL[numb].Location =new System.Drawing .Point (112+7*numb,240-20*a);a++;}
      if(s2=="Y"){tL[numb].Location =new System.Drawing .Point (250+7*numb,240-20*b);b++;}
      if(s2=="Z"){tL[numb].Location =new System.Drawing .Point (388+7*numb,240-20*c);c++;}
     
      }

     
    }
    }

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • steedhorse
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      3

      4
    发表于：2008-08-20 15:36:559楼 得分:0
    递归就是要相信思维的跨度。
    照楼主这么细致地去考虑问题，递归就没有任何优势了。还不如不用递归，自己手工用栈和循环来实现呢。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • steedhorse
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      3

      4
    发表于：2008-08-20 15:54:4510楼 得分:0
    当然，关于参数的传递（特别是值传递），以及参数的调用和返回机制，还是有必要了解一点的。
    但这个不限于递归，因为学习编程就得了解这个东西，不管用不用递归。
    除此之外，递归也没啥特别的，只是它调用了自己而已。
    通常情况下，我们会让一个函数调用另一个函数，但这并没有实质性的区别，因为函数从表面看就是个名字，从底层看就是个地址，不管你调用的是其它函数还是同一个函数，都是一样的。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • steedhorse
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      3

      4
    发表于：2008-08-20 16:00:4511楼 得分:0
    函数的调用和返回，打错了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • thaij
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 00:21:3512楼 得分:0
    值得好好琢磨下，不是太明白啊 。。
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved