汉诺塔基本介绍

  1. 有三根相邻的柱子A,B,C
  2. A柱子从上往下按照下大上小的顺序放着一些圆盘
  3. 把所有的圆盘移动到C柱子上，一次只能移动一个，B可以临时存放，每次移动时要保证下大上小的规则

image.png

分治法实现汉诺塔思路分析

最小规模

如果只有一个盘，A——>C

小的问题

假如我们有n>=2情况，我们总是可以看作是两个盘 ①最下面的盘，②上面的盘

  1. 先把上面的盘A——>B
  2. 把最下面的盘A——>C
  3. 把B塔的所有盘从B——>C

小问题是个递归的过程，很容易解决，我们要把大问题拆分成这样的小问题，再合并解

代码

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Globalization;
  4. using System.IO;
  5. using System.Runtime.Serialization.Formatters.Binary;
  6. using System.Text;
  8. namespace ConsoleApp1
  9. {
  10.     class Program
  11.     {
  12.         public static int count = 0;
  13.         static void Main(string[] args)
  14.         {
  15.             hanoiTower(30, 'A', 'B', 'C');
  16.             Console.WriteLine("次数："+count);
  17.         }
  19.         //汉诺塔移动的方法，使用分治算法
  20.         public static void hanoiTower(int num,char a,char b,char c)
  21.         {
  22.             //如果只有一个盘
  23.             if (num == 1)
  24.             {
  25.                 //Console.WriteLine($"第1个盘从{a}——>{c}");
  26.                 count++;
  27.             }
  28.             else
  29.             {
  30.                 //假如我们有n >= 2情况，我们总是可以看作是两个盘 ①最下面的盘，②上面的盘
  31.                 //1.先把上面的所有盘A——>B,移动过程中间使用C
  32.                 hanoiTower(num - 1, a, c, b);
  33.                 //2.把最下面的盘A——>C
  34.                 //Console.WriteLine($"第{num}个盘从{a}——>{c}");
  35.                 count++;
  36.                 //把B塔的所有盘从B——>C，移动过程中间借用A
  37.                 hanoiTower(num - 1, b, a, c);
  38.             }
  39.         }
  40.     }
  41. }