C#汉诺塔递归算法实现与可视化演示

数据结构设计

为了实现可视化的汉诺塔游戏，首先需要定义盘子的属性。每个盘子由高度、宽度以及在画布上的起始坐标组成。这些参数将用于后续计算盘子的大小和在垂直方向上的堆叠位置。

namespace 汉诺塔
{
  //盘子类
  class HanioItem
  {
    public int HanoiItemHeight { get; set; } //盘子的高度
    public int HanoiItemWidth { get; set; }   //盘子的宽度
    public Point HanoiItemPoint { get; set; } //画盘子的起始点
  }
}

界面初始化与盘面绘制

第1步：初始化绘图资源

在窗体加载时，需创建画笔对象并为三个代表柱子的 PictureBox 控件获取 Graphics 实例。这是所有绘图画布的基础环境准备。

// 初始化3个PictureBox画布
public void InitialTools()
{
   p = new Pen(Color.Black);
   hanioPicA = HanoiPicA.CreateGraphics();
   hanioPicB = HanoiPicB.CreateGraphics();
   hanioPicC = HanoiPicC.CreateGraphics();
}

第2步：生成初始盘子队列

根据输入的盘子数量（tag），在起始柱子 A 上生成一系列递减宽度的盘子。计算逻辑确保盘子从大到小依次排列，并存储到对应的 List 容器中。

public void InitialGraphics()
{
  int HanioItemHeight = 15;               // 固定盘子高度
  int HanioStartItemWidth = 90;           // 最大盘子宽度
  Point HanioStartItemP = new Point(15, 135); // 起始坐标

  InitialTools();
  tag = Convert.ToInt16(this.Tag.ToString());

  // 清空各塔列表
  HanioItemsA.Clear();
  HanioItemsB.Clear();
  HanioItemsC.Clear();

  // 计算相邻盘子宽度差值
  int diffrence = (90 - 30) / tag;

  for (int i = 1; i <= tag; i++)
  {
    HanioItem item = new HanioItem();
    item.HanoiItemWidth = HanioStartItemWidth;
    item.HanoiItemHeight = HanioItemHeight;
    item.HanoiItemPoint = HanioStartItemP;
    HanioItemsA.Add(item);

    // 下一个盘子变窄，中心向左微调
    HanioStartItemWidth -= diffrence;
    HanioStartItemP.X += diffrence / 2;
  }

  ShowHanoiGraphics();
}

第3步：执行重绘操作

此函数负责在内存中清除旧图像，绘制三根柱子的基础线条（底座和立柱），并根据当前 Lists 中的内容重新渲染所有盘子的位置。在 UI 线程调用此方法前，需插入短暂延迟以形成动画效果。

private void ShowHanoiGraphics()
{
  // 清屏
  hanioPicA.Clear(this.BackColor);
  hanioPicB.Clear(this.BackColor);
  hanioPicC.Clear(this.BackColor);

  // 绘制三个塔的基础框架线
  string[] pics = { "hanioPicA", "hanioPicB", "hanioPicC" };
  foreach (var pic in pics)
  {
     var g = /* 对应引用 */;
     g.DrawLine(p, 0, 150, 120, 150);
     g.DrawLine(p, 60, 0, 60, 150);
  }

  // 辅助函数：绘制特定塔的盘子
  DrawTower(hanioPicA, HanioItemsA);
  DrawTower(hanioPicB, HanioItemsB);
  DrawTower(hanioPicC, HanioItemsC);
}

// 简化版的绘制循环
void DrawTower(Graphics g, List<HanioItem> items)
{
  for (int i = 0; i < items.Count; i++) 
  {
    g.DrawRectangle(p, 
      items[i].HanoiItemPoint.X, 
      items[i].HanoiItemPoint.Y - i * 15, // 垂直堆叠
      items[i].HanoiItemWidth, 
      items[i].HanoiItemHeight);
  }
}

递归核心算法实现

第4步：编写递归移动函数

汉诺塔的经典解法是将规模为 n 的问题分解为 n-1 的子问题。函数 Hanio 接收盘子数量和源塔、辅助塔、目标塔的引用：

1. 若只有一个盘子，直接从源塔移动到目标塔。
2. 若有多个盘子：
   • 将上面 n-1 个盘子从源塔借助目标塔移到辅助塔。
   • 将剩下的最大的一个盘子从源塔直接移到目标塔。
   • 最后将辅助塔上的 n-1 个盘子借助源塔移到目标塔。

/// <summary>
/// 汉诺塔核心递归函数
/// </summary>
private void Hanio(int n, List<HanioItem> A, List<HanioItem> B, List<HanioItem> C)
{
  if (n == 1)
  {
    HanioMove(A, C); // 直接移向目标塔
  }
  else
  {
    Hanio(n - 1, A, C, B); // 借C中转，将n-1个从A移到B
    HanioMove(A, C);       // 最大的盘子A -> C
    Hanio(n - 1, B, A, C); // 借A中转，将n-1个从B移到C
  }
}

第5步：处理单步移动逻辑

HanioMove 负责在数据结构层面移除源塔顶部的盘子并加入目标塔，然后触发重绘，并暂停 1000 毫秒以让用户看清移动过程。

private void HanioMove(List<HanioItem> X, List<HanioItem> Y)
{
  // 获取顶部盘子
  HanioItem item = X[X.Count - 1];
  X.Remove(item);
  Y.Add(item);
  
  // 更新画面并延时
  ShowHanoiGraphics();
  System.Threading.Thread.Sleep(1000); 
}

启动运行

当用户点击确定按钮时，读取预设的盘子总数标签，开始递归求解：

private void btnOK_Click(object sender, EventArgs e)
{
  Hanio(tag, HanioItemsA, HanioItemsB, HanioItemsC);
}

以上就是用C#解决汉诺塔问题的详细内容，更多关于C#图形化算法实现及WinForms开发的资料请关注本站其它相关文章！