2025年汉诺塔游戏玩法介绍（攻略和编程实现）

大家好，我是讯享网，很高兴认识大家。

汉诺塔游戏玩法介绍（攻略和编程实现）

汉诺塔游戏介绍

汉诺塔是根据一个传说形成的数学问题。描述如下：有三根杆子 A、B、C 。 A 杆上 N 个穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

每次只能移动一个圆盘
大盘不能叠在小盘上面

可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？

最早发明这个问题的人是法国数学家爱德华·卢卡斯。传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子。预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

若传说属实，僧侣们需要 $2^{64}-1$ 步才能完成这个任务，若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。

这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

在这里插入图片描述
讯享网

递归解法

这个游戏，只要手机上下个 APP ，N 从小到大玩一会，也就知道其中的套路了。如果有一个盘，那么直接将这个盘从 A 挪到 C即可。如果有两个盘，需要先将小盘挪到 B，大盘挪到 C，再将小盘挪到 C，以此类推……

可以看到，解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有 N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 N-1 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N-1 块盘移到 C。要先把 N-1 块盘挪到B，就需要先把 N-2 块盘挪到 C……如此递归地使用下去, 就可以求解。从这也可以看到需要总的步数为 $2^N-1$ 。

一个简单的 MATLAB 代码如下：

function hanoi2(n) %a上原有盘数为n的汉诺塔。 han(n,'a','b','c') function han(n,a,b,c) if n==1 ex(a,c) else han(n-1,a,c,b) ex(a,c) han(n-1,b,a,c) end function ex(a,b) disp ([a '-->' b])

讯享网

非递归算法

事实情况是，在现实生活中，给你这个游戏，你总不能老想着递归的事情，来完成这个游戏吧，对于脑子不灵光的同学，容易搞迷糊。所以，我们当遇到这个游戏的时候，需要一条“黄金准则”，来指导我们完成这个游戏。

我玩了两个小时这个游戏，琢磨出来一个准则，能够在现实生活中指导我们完成这个游戏，本质上还是递归，只不过有一些更好的理解方式。

方法如下，为了描述的方便，我将盘从小到大从 1 开始依次编号。
[
在这里插入图片描述

第一步：初始化。先判断 N 是奇数还是偶数，如果是奇数，先挪一个盘到 C，如果是偶数，先挪一个盘到B。
第二步：找 1 所在杆子，数出和 1 的连号数目（例：，前 4 个和 1 依次相连，那么连号为 4），假设连号数目为 k。
第三步：找到 k+1 号盘所在的杆，把它挪到除 1 所在的杆之外的另外一个杠（不妨称为其他杆）。
第四步，若 k+1 为奇数，那么将 1 挪到原 k+1 号盘所在的杆，否则，挪到现 k+1 号盘所在的杆（其它杆）。
判断是否结束，没结束，回到第二步。

看起来比较麻烦，顺几遍就知道其中的奥妙了。根据我琢磨出来的这个算法，我也写了个 MATLAB 程序如下：

讯享网%% 汉诺塔游戏编程 function Hanoi() clc clear close all %% 参数设定和初始化 N = 3; A = N:-1:1; B = []; C = []; State = {A,B,C}; State_desc = {'A','B','C'}; %% 执行第一步 steps = 1; if mod(N,2)==0 State{2} = State{1}(end); disp(['Step' num2str(steps) ':' State_desc{1} '->' State_desc{2}]); else State{3} = State{1}(end); disp(['Step' num2str(steps) ':' State_desc{1} '->' State_desc{3}]); end State{1}(end) = []; show_state(); %% while length(State{3})~=N %这是结束的标志 steps = steps + 1; set_ind_contain_one = find_element(1,State{1},State{2},State{3}); num_adj = num_adjacent(State{set_ind_contain_one}); ele_move = num_adj+1; set_ind_contain_ele_move = find_element(ele_move,State{1},State{2},State{3}); left_set_ind = setdiff(1:3, [set_ind_contain_one set_ind_contain_ele_move]) ; State{left_set_ind}(end+1) = State{set_ind_contain_ele_move}(end); State{set_ind_contain_ele_move}(end) = []; disp(['Step' num2str(steps) ':' State_desc{set_ind_contain_ele_move} '->' State_desc{left_set_ind}]); show_state(); steps = steps + 1; if mod(ele_move,2)==1 State{set_ind_contain_ele_move}(end+1) = State{set_ind_contain_one}(end); State{set_ind_contain_one}(end) = []; disp(['Step' num2str(steps) ':' State_desc{set_ind_contain_one} '->' State_desc{set_ind_contain_ele_move}]); show_state(); else State{left_set_ind}(end+1) = State{set_ind_contain_one}(end); State{set_ind_contain_one}(end) = []; disp(['Step' num2str(steps) ':' State_desc{set_ind_contain_one} '->' State_desc{left_set_ind}]); show_state(); end end function show_state() disp([' A=[' num2str(State{1}) ']']); disp([' B=[' num2str(State{2}) ']']); disp([' C=[' num2str(State{3}) ']']); end end function num = num_adjacent(S) len = length(S); diffS = S - (len:-1:1); num = length(find(diffS==0)); end function Set_ind = find_element(ele,A,B,C) if ismember(ele,A) Set_ind = 1; elseif ismember(ele,B) Set_ind = 2; else Set_ind = 3; end end

在这里插入图片描述

仿真和可视化界面

别人还做了这个游戏的仿真和可视化界面，可以用来学习 MATLAB 的GUI。