C++ 学习笔记： 汉诺塔问题的迭代解法

2022-12-06 22:07:19

目录

启发

既然是非递归解法，那么运用的函数中就不能出现之间或间接地对自身的引用。迭代就是利用一个完整的解决算法，对每一步都利用该步数作为参数带入算法得出具体结果。所以要迭代，就必须分析汉诺塔移动过程中每一步体现的规律。


思路&部分代码

分解过程

每一步都可以分解为：
1.决定移动的盘号（假如对n个盘子编号，从小到大为1~n）
2.决定将盘子从哪移动到哪。

由此可知，要解决的问题就是：
1.如何确定每一步对应那个盘子；
2.如何确定盘子当前的位置和要移动的位置。

移动盘号

假设移动4个盘子，默认将盘子从1号移动到3号柱，2号柱作为临时存放点。过程如下(括号内代表移动的盘号):

1–2(1)
1–3(2)
2–3(1)
1–2(3)
3–1(1)
3–2(2)
1–2(1)
1–3(4)
2–3(1)
2–1(2)
3–1(1)
2–3(3)
1–2(1)
1–3(2)
2–3(1)

观察上面式子，可以知道:
1.总步骤数为15（也就是24 -1)
2.移动1号盘的步骤为：[1,3,5,7,9,11,13,15] ,移动2号盘的步骤为[2,6,10,14]; 移动3号盘的步骤为[4,12]; 移动4号盘的步骤为[8]
3.第一次移动1号盘在步骤1；第一次移动2号盘在步骤2；第一次移动3号盘在步骤4，第一次移动4号盘在步骤8。

间隔数

由此可看到, 1号盘的步骤数间隔为2(3-1,5-3,7-5), 2号的间隔数为4(6-2,10-6,14-10), 3号的间隔数为8(12-4).因此猜测每个盘间隔数和它的盘号有关:

盘号 间隔数
1 2=21
2 4=22
3 8=23
4 24=16

以此类推。

证明：
递归地分析移动n个盘子的过程可得：
n=1时,移动一次;
n=2时,移动1+1+1=3次(首尾两个1分别代表移动1号的步骤);
n=3时,先移动2个盘到临时点上,再移动3号,最后把1,2号移动到终点,因此:3+1+3 = 7次.
为n时,设 a n a_{n} an​为总步数,则 a n a_{n} an​=2 a n − 1 + 1 a_{n-1} + 1 an−1​+1
得出 a n = 2 n − 1 a_{n} = 2^{n} -1 an​=2n−1
图解如下:
C++ 学习笔记： 汉诺塔问题的迭代解法
因此可以利用数学归纳法证明步骤间隔数和盘号的关系.
设移动总数为n的盘子们
其中1号:
因为移动了1号盘以后,下一步不可能再动1号,因此排除"存在任意连续的两步都移动1号"的假设.当移动了另外号码(假设a号)的盘子后(此时除1号呆的柱子,其他柱子上的盘子都比1号大),第三步一定会移动1号,因为移动之前a号下要么比a号大,要么没有盘子,又不可能再把a号移回去(无效操作),因此只能挪动1号.得出:一号的步骤间隔为2.
设k号盘的步骤间隔=2k 成立
k+1号:
总过程分解到(k+1)的层次,共有2(n-k-1) 个分叉.每个分叉都代表移动k个盘子的(2k-1 -1)步,因此间隔数：
a k + 1 = 2 k − 1 + 1 + 2 k − 1 + 1 = 2 k + 1 a_{k+1} = 2^{k}-1+1+2^{k}-1+1 = 2^{k+1} ak+1​=2k−1+1+2k−1+1=2k+1
中间的+1代表移动k+2号盘的那一步,最后的+1代表移动第二次移动k+1号盘的那一步.

第一次移动某盘对应的步骤数

依照上图，证明这个也就很简单了。第一次移动第n个盘子的步骤编号为2n-1 。递归下去，第一次移动第n+1个盘子的步骤编号为2n-2 。因此，第一次移动第k个盘子的步骤编号为：
2k-1.


确定某一步要移动的盘号

现在我们可以解决第一个大问题了，就是如何确定每一步要移动的盘号。根据以上两个性质可得，在第（m）步时，定有某个盘（k）移动第（i）次，即：
m = 2 k − 1 + ( i − 1 ) ∗ 2 k m = 2^{k-1}+(i-1)*2^{k} m=2k−1+(i−1)∗2k
其中“2”的出现频率之高让人不禁想到二进制（？）或许可以利用二进制的某些特征来通过（m）反向确定（k）。
当 i ≠ 0 i \neq 0 i​=0 时， ( i − 1 ) ∗ 2 k (i-1)*2^{k} (i−1)∗2k 一定大于 2 k − 1 2^{k-1} 2k−1。 也就是说式子的前半部分在二进制数中似乎一直作为最低位的部分。（i）的大小不影响这一事实。
于是有：在第（m）步时，（m）所对应的二进制表示中最低为1的位数代表着移动的盘号。

代码1

将这一部分的功能用一个独立的函数完成：

#include <iostream>
#include <sstream>  //用于将数字转换为字符串
#include <bitset>  //用于将数字转换为二进制形式
#include <string>
#include <cmath>


int lowestBit(int num)
{
    //初始化stringstream对象,
    //用于存储步骤数num的二进制形式的bitForm
    //和其字符串形式的bitString
    stringstream ss;
    bitset<32> bitForm = bitset<32>(num);  //得到数字的二进制形式
    string bitString;
    
    //初始化盘号.
    //考虑到汉诺塔可能很高,所以用范围较大的 unsigned int
    unsigned int position = 0;  
    
    //转换为字符串
    ss << bitForm;
    ss >> bitString;
    
	//for循环从右往左判定第一个1出现的位置
	for (unsigned int i = bitString.size(); i >= 0;i--)
    {
        if (bitString[i] == '1')
        {
        	//注意,bitString的最右边有一个隐式的“\0”
        	//因此若第一位为"1",此时 i = 31
            position = bitString.size() - i;
            break;
        }
    }
    return position;
}

移动的起始和终止

反观移动4个盘子的过程，还可以发现：

1–2(1)
1–3(2)
2–3(1)
1–2(3)
3–1(1)
3–2(2)
1–2(1)
1–3(4)
2–3(1)
2–1(2)
3–1(1)
2–3(3)
1–2(1)
1–3(2)
2–3(1)

（1）号盘的路线是：1–2--3–1--2–3--1–2--3
（2）号盘的路线是：1–3--2–1--3
（3）号盘的路线是：1–2--3
（4）号盘的路线是：1–3
这之中存在着一种“不走回头路”的规律：（1）号不会从1–2之后，再从2–1，23、31的组合同理，剩下（2、3、4）号盘的行动路线也同理。因为要避免无效回合，当一个盘子最初的移动定下来时，它的轨迹就已经决定了。
因此，产生了两种移动路线：
顺序：1–2--3–1
逆序：1–3--2–1

又:最后一个盘一定只有 1–3 这一步（默认初始都在1号，终点为3号）。由上递归分析图可得，（3）的移动轨迹和（4）相反，（2）和（3）相反，（1）和（2）相反，以此类推。

总结出：
当移动总数为n的盘子时，第k个盘子的行动轨迹：
1.与n相同【n-k为偶数】
2.与n相反【n-k为奇数】

那么我们只要根据盘号确定每一个盘子的轨迹，并根据其移动次数 i i i 来确定始终即可。

代码2

代码分成两个函数，一个用于收集用户提供的起点、终点和临时点模拟出轨迹，一个根据当前步骤数和盘号判断具体移动：

string movement(unsigned int plateNum,unsigned int stepNum,unsigned int position,int ini,int fin,int tem)
{
	//根据盘号和步骤数,利用上面提供的 [步骤,盘号,次数] 三者的关系式逆推次数 i
	//由 i 判断具体移动
	//plateNum -- 盘子总数
	//stepNum -- 步骤数
	//position -- 盘号
	//ini -- 起点
	//fin -- 终点
	//tem -- 临时点

	//初始化移动次数moveTimes 和 字符串move
    unsigned int moveTimes = 0;
    string move;
    
    //计算moveTimes
    moveTimes = stepNum - static_cast<unsigned int>(pow(2, static_cast<double>(position)-1));
    moveTimes /= static_cast<int>(pow(2, static_cast<double>(position)));
    moveTimes += 1;
    
	//用 moveTimes 判断具体行动
	if((plateNum - position)%2 == 0)
    {
        if ((moveTimes % 3) == 1)
            move = movementGenerator(ini,fin);
        else if ((moveTimes % 3) == 2)
            move = movementGenerator(fin,tem);
        else
            move = movementGenerator(tem,ini);
    }
    else
    {
        if ((moveTimes % 3) == 1)
            move = movementGenerator(ini,tem);
        else if ((moveTimes % 3) == 2)
            move = movementGenerator(tem,fin);
        else
            move = movementGenerator(fin,ini);
    }
    return move;
}


string movementGenerator(int start,int end)
{
	//返回对应的行动轨迹字符串
	//如:起点=1,终点=2
	//则返回字符串"1--2"
    stringstream ss;
    string moveString;
    ss << start;
    ss<<"--";
    ss << end;
    ss >> moveString;
    return moveString;
}

总过程及代码

利用一个总函数hanoi集合运行上面的几个函数,解决汉诺塔问题。 总代码如下：

//tower of hanoi
//iteration type
#include <iostream>
#include <bitset>
#include <sstream>
#include <string>
#include <cmath>
using namespace std;

void hanoi(unsigned int, int, int, int);
int lowestBit(int);
string movement(unsigned int, unsigned int, unsigned int,int,int,int);
string movementGenerator(int, int);

int main()
{
    unsigned int plateNum = 0;
    int ini = 0;
    int fin = 0;
    int tem = 0;
    cout << "Enter the plate number: ";
    cin >> plateNum;
    cout << "Enter the ini, fin, and tem: ";
    cin >> ini >> fin >> tem;
    hanoi(plateNum, ini, fin, tem);
    
    

}

//return the position of the first "1" from right to left, AKA the plate number
int lowestBit(int num)
{
    stringstream ss;
    bitset<32> bitForm = bitset<32>(num);
    string bitString;
    unsigned int position = 0;
    ss << bitForm;
    ss >> bitString;
    for (unsigned int i = bitString.size(); i >= 0;i--)
    {
        if (bitString[i] == '1')
        {
            position = bitString.size() - i;
            break;
        }
    }
    return position;
}

//return a string including the movement, such as "A--B"
string movement(unsigned int plateNum,unsigned int stepNum,unsigned int position,int ini,int fin,int tem)
{
    unsigned int moveTimes = 0;
    string move;
    moveTimes = stepNum - static_cast<unsigned int>(pow(2, static_cast<double>(position)-1));
    moveTimes /= static_cast<int>(pow(2, static_cast<double>(position)));
    moveTimes += 1;
    if((plateNum - position)%2 == 0)
    {
        if ((moveTimes % 3) == 1)
            move = movementGenerator(ini,fin);
        else if ((moveTimes % 3) == 2)
            move = movementGenerator(fin,tem);
        else
            move = movementGenerator(tem,ini);
    }
    else
    {
        if ((moveTimes % 3) == 1)
            move = movementGenerator(ini,tem);
        else if ((moveTimes % 3) == 2)
            move = movementGenerator(tem,fin);
        else
            move = movementGenerator(fin,ini);
    }
    return move;
}

string movementGenerator(int start,int end)
{
    stringstream ss;
    string moveString;
    ss << start;
    ss<<"--";
    ss << end;
    ss >> moveString;
    return moveString;
}

//总函数hanoi
void hanoi(unsigned int plateNum, int ini, int fin, int tem)
{
    unsigned int position;
    string move;
    for (unsigned int i = 1; i <= pow(2,static_cast<double>(plateNum))-1;i++)
    {
        position = lowestBit(i);
        move = movement(plateNum, i, position,ini,fin,tem);
        cout << move << endl;
    }
}

后记

该解法参考c++迭代递归实现汉诺塔（5种迭代方法满足你）。笔者初觉得只用迭代的方法实现汉诺塔问题很难，惊叹于此文章用到的思维方式。为学习如何具体地分析一个较复杂的问题，特记此思考过程。如有疑问，欢迎讨论。

上一篇：​深入理解［代理模式］原理与技术


下一篇：linux shell之不使用局部变量的递归