3柱河内塔问题的一种解释

直接进入正题.今有3个柱子A,B,C.A柱子上有n个大小不同的盘子,且从上到下盘子从小到大.要把所有的A柱子上的盘子移动到C柱子.

移动盘子可以借助B柱子,但是要求每次只能移动1个盘子,且整个移动过程中大盘子总是要在小盘子的下面.

图1.河内塔问题

如果只有1个盘子,结论是显然的.A移到C即可.

如果有n个盘子(n>=2),结论不显然,需要化简些.

先把n-1个盘子从A移动到B,借助C.(不必知道具体是怎么移动的,反正我做到了.)

再把最大的盘子从A移动到C.

然后把B柱子的n-1个盘子移动到C,借助A.(同样的,不必知道具体是怎么移动的,反正我做到了.)

于是我们把n个盘子的问题转化为了2个n-1个盘子的问题.

接着对每个(n-1个盘子的)问题操作下去,可以得到4个(n-2个的盘子的)问题.

最后可以化为若干(2的n-1次方)个显然的 1个盘子的问题.

由等比数列求和可以看出,一共需要2的n次方-1次操作.

全文的最后,发下(解决3个盘子的)代码吧:(C# .netcore 3.1)

 1 using System;
 2 namespace Hanoi {
 3     public static class Program {
 4 
 5         public static int Main(string[] args) {
 6             Hanoi(3, 'a', 'b', 'c');
 7             return 0;
 8         }
 9         public static void Hanoi(int k,char @from,char via,char to) {
10             if(k == 1) {
11                 Console.WriteLine($"{k}:{from}->{to}");
12             }
13             else {
14                 Hanoi(k - 1, @from, to, via);
15                 Console.WriteLine($"{k}:{from}->{to}");
16                 Hanoi(k - 1, via, @from, to);
17             }
18         }
19     }
20 }

p.s. 由于微软宣布不再给VB.NET提供新功能,后面就都用C#搞事情了(真香啊)