大家谁能给我一个“汉诺塔”的递归程序

Question

我记得西电马玉祥写的Pascal书上有例子

Answer 1

/* 这个是 C 语言的 */
void move(char x, int n, char z) {
printf("move(%c, %d, %c);\n", x, n, z);
}void hanoi(int n, char x, char y, char z) {
printf("hanoi(%d, %c, %c, %c);\n", n, x, y, z);
if(n==1)
move(x, 1, z);
else {
hanoi(n-1, x, z, y);
move(x, n, z);
hanoi(n-1, y, x, z);
}
}main() {
hanoi(5, 'X', 'Y', 'Z');
}

Answer 2

/* 这个是C＃的 */
using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;namespace WindowsApplication1
{
/// <summary>
/// Summary description for Form1.
/// </summary>
public class Form1 : System.Windows.Forms.Form
{
private System.Windows.Forms.ListBox list;
private System.Windows.Forms.NumericUpDown numericUpDown_圆盘数量;
private System.Windows.Forms.Button button_开始计算;
private System.Windows.Forms.Label label1;
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.Container components = null; public Form1()
{
//
// Required for Windows Form Designer support
//
InitializeComponent(); //
// TODO: Add any constructor code after InitializeComponent call
// } /// <summary>
/// Clean up any resources being used.
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if (components != null) 
{
components.Dispose();
}
}
base.Dispose( disposing );
} #region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.list = new System.Windows.Forms.ListBox();
this.button_开始计算 = new System.Windows.Forms.Button();
this.label1 = new System.Windows.Forms.Label();
this.numericUpDown_圆盘数量 = new System.Windows.Forms.NumericUpDown();
((System.ComponentModel.ISupportInitialize)(this.numericUpDown_圆盘数量)).BeginInit();
this.SuspendLayout();
// 
// list
// 
this.list.Anchor = (((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
| System.Windows.Forms.AnchorStyles.Left) 
| System.Windows.Forms.AnchorStyles.Right);
this.list.HorizontalScrollbar = true;
this.list.IntegralHeight = false;
this.list.ItemHeight = 16;
this.list.Location = new System.Drawing.Point(0, 48);
this.list.Name = "list";
this.list.Size = new System.Drawing.Size(272, 168);
this.list.TabIndex = 0;
// 
// button_开始计算
// 
this.button_开始计算.Anchor = (System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right);
this.button_开始计算.Location = new System.Drawing.Point(176, 8);
this.button_开始计算.Name = "button_开始计算";
this.button_开始计算.Size = new System.Drawing.Size(88, 32);
this.button_开始计算.TabIndex = 1;
this.button_开始计算.Text = "开始计算";
this.button_开始计算.Click += new System.EventHandler(this.button_开始计算_Click);
// 
// label1
// 
this.label1.Location = new System.Drawing.Point(0, 16);
this.label1.Name = "label1";
this.label1.Size = new System.Drawing.Size(112, 24);
this.label1.TabIndex = 3;
this.label1.Text = "圆盘的数量：";
this.label1.TextAlign = System.Drawing.ContentAlignment.MiddleRight;
// 
// numericUpDown_圆盘数量
// 
this.numericUpDown_圆盘数量.Location = new System.Drawing.Point(112, 16);
this.numericUpDown_圆盘数量.Maximum = new System.Decimal(new int[] {
   99,
   0,
   0,
   0});
this.numericUpDown_圆盘数量.Minimum = new System.Decimal(new int[] {
   1,
   0,
   0,
   0});
this.numericUpDown_圆盘数量.Name = "numericUpDown_圆盘数量";
this.numericUpDown_圆盘数量.Size = new System.Drawing.Size(48, 26);
this.numericUpDown_圆盘数量.TabIndex = 2;
this.numericUpDown_圆盘数量.Value = new System.Decimal(new int[] {
 1,
 0,
 0,
 0});
// 
// Form1
// 
this.AcceptButton = this.button_开始计算;
this.AutoScaleBaseSize = new System.Drawing.Size(8, 19);
this.ClientSize = new System.Drawing.Size(272, 214);
this.Controls.AddRange(new System.Windows.Forms.Control[] {
  this.numericUpDown_圆盘数量,
  this.button_开始计算,
  this.list,
  this.label1});
this.Font = new System.Drawing.Font("宋体", 12F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(134)));
this.MinimumSize = new System.Drawing.Size(240, 240);
this.Name = "Form1";
this.Text = "汉诺塔问题求解";
((System.ComponentModel.ISupportInitialize)(this.numericUpDown_圆盘数量)).EndInit();
this.ResumeLayout(false); }
#endregion /// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main() 
{
Application.Run(new Form1());
} private void button_开始计算_Click(object sender, System.EventArgs e)
{
System.DateTime begin = System.DateTime.Now;
string [] str = 汉诺塔.计算汉诺塔移动过程(
System.Convert.ToInt32(this.numericUpDown_圆盘数量.Value),
"X",
"Y",
"Z"
);
System.DateTime end = System.DateTime.Now; this.list.Items.Clear();
this.list.Items.AddRange(str);
this.list.Items.Add("______________________________________________________________________");
this.list.Items.Add("总共移动 " + (str.Length - 1) + " 次");
this.list.Items.Add("花费时间：" + (end - begin));
this.list.Items.Add("");
} } public class 汉诺塔
{
private static 塔座 x = null;
private static 塔座 y = null;
private static 塔座 z = null;
private static System.Collections.ArrayList 结果 = null; public static string [] 计算汉诺塔移动过程(int 圆盘数量)
{
return 计算汉诺塔移动过程(圆盘数量, "X", "Y", "Z");
} public static string [] 计算汉诺塔移动过程(int 圆盘数量, string X塔名字, string Y塔名字, string Z塔名字)
{
//初始化数据并为三做塔命名
x = new 塔座(X塔名字);
y = new 塔座(Y塔名字);
z = new 塔座(Z塔名字);
结果 = new System.Collections.ArrayList();
结果.Add("在以下结果中：括号“（）”中的数字表示圆盘的大小．用“—>”表示移动到目标塔座。例如：“X(2)->Z”将X塔座上的大小为2的盘移动到Z塔座上"); //用整数(从"1"到"圆盘数量")分别表示大小不同的圆盘,放到X塔座上.(数字越大,所代表的圆盘越大)
for(int i = 1; i <= 圆盘数量; i ++)
{
x.Add(i);
}
汉诺塔处理(x.Count,x,y,z);
return (string [])(结果.ToArray(typeof(string)));
} //移动某塔座上的第一个圆盘
private static void 移动(塔座 原塔座, 塔座 目标塔座)
{
结果.Add(原塔座.名字 + "(" + 原塔座[0] + ")" + "—>" + 目标塔座.名字);
目标塔座.Insert(0, 原塔座[0]);
原塔座.RemoveAt(0);
} //该函数为递归函数，用来完成汉诺塔的移到。
private static void 汉诺塔处理(int n, 塔座 x塔, 塔座 y塔, 塔座 z塔)
{
if(n == 1)
{
移动(x塔, z塔);
}
else
{
汉诺塔处理(n-1, x塔, z塔, y塔);
移动(x塔, z塔);
汉诺塔处理(n-1, y塔, x塔, z塔);
}
}
} /// <summary>
/// 声明塔座类
/// </summary>
public class 塔座:System.Collections.ArrayList
{
/// <summary>
/// 用来定义塔座的名字
/// </summary>
public string 名字; public 塔座(string 塔座名字)
{
this.名字 = 塔座名字;
}
}
}