【二十三】【算法分析与设计】三柱汉诺塔详解，计算子移动次数，正常递归计算，观察数据得出数学规律，递归图得出数学规律，将递归函数转化为递推式

目录

汉诺塔递归

汉诺塔子移动次数的计算

牛牛的汉诺塔

选择正常的递归模拟计算子移动次数

根据具体数据得出数学规律

根据递归图得出数学规律

将递归函数转化为递推式

结尾

---

汉诺塔递归

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。

其伪代码如下

Function Hanoi(n,a,b,c)if n==1 thenprint(a+'->'+c)elseHanoi(n-1,a,c,b)print(a+'->'+c)Hanoi(n-1,b,a,c)end if
end Function 

定义递归函数hanoi(n,a,b,c)表示将n个盘子从a柱移动到c柱，以b柱为辅助柱。

维护定义的含义，内部逻辑先将n-1个盘子从a柱移动到b柱，以c柱为辅助柱。再将最大盘子从a柱移动到c柱，以b柱为辅助柱。最后将n-1个盘子从b柱移动到c柱，以a柱为辅助柱。

递归结束出口为n==1时，从a柱移动到c柱，以b柱为辅助柱。

C++代码

#include <iostream>
using namespace std;// 函数声明
void hanoi(int n, char a, char b, char c) {if (n == 1) {cout << a << "->" << c<< endl;return;}hanoi(n-1, a, c, b);cout << a << " -> " << c<< endl;hanoi(n-1, b, a, c);
}

汉诺塔子移动次数的计算

牛牛的汉诺塔

链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。

其伪代码如下

Function Hanoi(n,a,b,c)

if n==1 then

print(a+'->'+c)

else

Hanoi(n-1,a,c,b)

print(a+'->'+c)

Hanoi(n-1,b,a,c)

end if

end Function

牛牛很快就理解了代码的意思并且写出了求解汉诺塔的程序，他现在想研究汉诺塔的规律。

请你统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。

输入描述:

仅一行，输入一个正整数n(1≤n≤60)(1 leq n leq 60)(1≤n≤60)表示汉诺塔的层数。

输出描述:

首先输出6行

A->B:XX

A->C:XX

B->A:XX

B->C:XX

C->A:XX

C->B:XX

分别表示每种移动情况出现的次数

最后输出一行

SUM:XX

表示所有移动情况的总和。

示例1

输入

复制3

3

输出

复制A->B:1 A->C:3 B->A:1 B->C:1 C->A:0 C->B:1 SUM:7

A->B:1

A->C:3

B->A:1

B->C:1

C->A:0

C->B:1

SUM:7

说明

伪代码所示算法的移动序列如下：

A->C

A->B

C->B

A->C

B->A

B->C

A->C

统计：

A->B出现1次

A->C出现3次

B->C出现1次

B->A出现1次

C->B出现1次

总计7次

选择正常的递归模拟计算子移动次数

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}
}
int main() {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;char a = 'A', b = 'B', c = 'C';int n;cin>>n;Hanoi(n, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count=count_ab+count_ac+count_ba+count_bc+count_ca+count_cb;cout<<"A->B:"<<count_ab<<endl;cout<<"A->C:"<<count_ac<<endl;cout<<"B->A:"<<count_ba<<endl;cout<<"B->C:"<<count_bc<<endl;cout<<"C->A:"<<count_ca<<endl;cout<<"C->B:"<<count_cb<<endl;cout<<"SUM:"<<count;
}

我们可以通过递归关系式来表达这个问题的解法次数。对于n个盘子，移动它们所需的步骤T(n)可以表示为：

T(n)=2T(n−1)+1

这里的思路是：移动n-1个盘子到临时柱子（这需要T(n-1)步），移动最大的盘子到目标柱子（这需要1步），最后再将n-1个盘子从临时柱子移动到目标柱子上（再次需要T(n-1)步）。

我们可以进一步解开这个递归式：

• 当n = 1时，只需要移动一次，所以T(1) = 1。

• 当n = 2时，T(2) = 2T(1) + 1 = 3。

• 当n = 3时，T(3) = 2T(2) + 1 = 7。

以此类推，我们发现这是一个等比数列的求和问题，其总和公式为：

T(n)=2^n−1

因此，汉诺塔问题的时间复杂度为O(2^n)。这个复杂度表明了随着盘子数量的增加，需要的移动次数呈指数级增长，这也解释了为什么汉诺塔问题在盘子数量稍多时就变得难以直接通过手动移动来解决。

当n==60时，时间复杂度是O(2^60)，2^10≈1000=10^3，2^60==2^10*2^10*2^10*2^10*2^10*2^10。也就是六个10^3相乘，等于10^18远远超过10^9，10^9对应的时间大概是1s，这样的递归是一定会超时的。

根据具体数据得出数学规律

我们将正常递归模拟计算子移动次数的代码进行修改，用来计算前n项的子移动次数数据。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a = 'A', b = 'B', c = 'C';cout<<"     ";cout << setw(8) << "a->b " << setw(8) << "a->c " << setw(8) << "b->a " << setw(8) << "b->c " << setw(8) << "c->a " << setw(8) << "c->b " << setw(8) << "SUM " << endl;for (int i = 1; i <= 20; i++) {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count = count_ab + count_ac + count_ba + count_bc + count_ca + count_cb;cout << "n="<<setw(2) << i<<":";cout << setw(7) << count_ab << " ";cout << setw(7) << count_ac << " ";cout << setw(7) << count_ba << " ";cout << setw(7) << count_bc << " ";cout << setw(7) << count_ca << " ";cout << setw(7) << count_cb << " ";cout << setw(7) << count << endl;}}

//输出a->b    a->c    b->a    b->c    c->a    c->b     SUM
n= 1:      0       1       0       0       0       0       1
n= 2:      1       1       0       1       0       0       3
n= 3:      1       3       1       1       0       1       7
n= 4:      4       3       1       4       2       1      15
n= 5:      4       9       6       4       2       6      31
n= 6:     15       9       6      15      12       6      63
n= 7:     15      31      27      15      12      27     127
n= 8:     58      31      27      58      54      27     255
n= 9:     58     117     112      58      54     112     511
n=10:    229     117     112     229     224     112    1023
n=11:    229     459     453     229     224     453    2047
n=12:    912     459     453     912     906     453    4095
n=13:    912    1825    1818     912     906    1818    8191
n=14:   3643    1825    1818    3643    3636    1818   16383
n=15:   3643    7287    7279    3643    3636    7279   32767
n=16:  14566    7287    7279   14566   14558    7279   65535
n=17:  14566   29133   29124   14566   14558   29124  131071
n=18:  58257   29133   29124   58257   58248   29124  262143
n=19:  58257  116515  116505   58257   58248  116505  524287
n=20: 233020  116515  116505  233020  233010  116505 1048575

我们将a->b,a->c,b->a,b->c,c->a,c->b分别记为1,2,3,4,5,6。

我们希望找出前后项的规律，很容易发现，同一个n中，1号等于4号，3号等于6号。

因此我们将数据截取出1,2,3,5四列数据。做法很简单，只需要简单修改代码即可。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL N = 1000005;
LL MOD = 1e4 + 7;
LL N1 = 10005;void Hanoi(int n, char a, char b, char c, int& count_ab, int& count_ac, int& count_ba, int& count_bc, int& count_ca, int& count_cb) {if (a == 'A' && c == 'B') count_ab++;if (a == 'A' && c == 'C') count_ac++;if (a == 'B' && c == 'A') count_ba++;if (a == 'B' && c == 'C') count_bc++;if (a == 'C' && c == 'A') count_ca++;if (a == 'C' && c == 'B') count_cb++;if (n == 1) {return;} else {Hanoi(n - 1, a, c, b, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);Hanoi(n - 1, b, a, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);}}
int main() {char a = 'A', b = 'B', c = 'C';cout << "     ";cout << setw(8) << "a->b ";cout << setw(8) << "a->c ";cout << setw(8) << "b->a ";
//    cout << setw(8) << "b->c ";cout << setw(8) << "c->a ";
//    cout << setw(8) << "c->b ";cout << setw(8) << "SUM " << endl;for (int i = 1; i <= 20; i++) {int count_ab = 0;int count_ac = 0;int count_ba = 0;int count_bc = 0;int count_ca = 0;int count_cb = 0;Hanoi(i, a, b, c, count_ab, count_ac, count_ba, count_bc, count_ca, count_cb);int count = count_ab + count_ac + count_ba + count_bc + count_ca + count_cb;cout << "n=" << setw(2) << i << ":";cout << setw(7) << count_ab << " ";cout << setw(7) << count_ac << " ";cout << setw(7) << count_ba << " ";
//        cout << setw(7) << count_bc << " ";cout << setw(7) << count_ca << " ";
//        cout << setw(7) << count_cb << " ";cout << setw(7) << count << endl;}}

//输出a->b    a->c    b->a    c->a     SUM
n= 1:      0       1       0       0       1
n= 2:      1       1       0       0       3
n= 3:      1       3       1       0       7
n= 4:      4       3       1       2      15
n= 5:      4       9       6       2      31
n= 6:     15       9       6      12      63
n= 7:     15      31      27      12     127
n= 8:     58      31      27      54     255
n= 9:     58     117     112      54     511
n=10:    229     117     112     224    1023
n=11:    229     459     453     224    2047
n=12:    912     459     453     906    4095
n=13:    912    1825    1818     906    8191
n=14:   3643    1825    1818    3636   16383
n=15:   3643    7287    7279    3636   32767
n=16:  14566    7287    7279   14558   65535
n=17:  14566   29133   29124   14558  131071
n=18:  58257   29133   29124   58248  262143
n=19:  58257  116515  116505   58248  524287
n=20: 233020  116515  116505  233010 1048575

我们希望由上面的数据找出前后项的关系，我们对a->b,a->c,b->a,c->a重新进行编号，分别记为1,2,3,4。

我们需要用的n-1项的1,2,3,4号数据推导出n项的1,2,3,4号数据。

找规律的思路是，我们可以先关注n项的1号数据，看n-1项的某一号数据是否可以单独推导出n项的1号数据。1对1的关系。如果1对1的关系找不到，那就找n-1项的多号数据是否可以推导出1号数据，以此类推。

先关注n项1号与n-1项一对一的关系。

当n==7时，1号等于n==6的（2号*2-3），等于（3号*2+3）。

当n==8时，1号等于n==7的（2号*2-4），等于（3号*2+4）。

当n==9时，1号等于n==8的（2号*2-4），等于（3号*2+4）。

当n==10时，1号等于n==9的（2号*2-5），等于（3号*2+5）。

很容易发现递推公式，n项的1号等于n-1项的（2号*2-n/2）或者等于（3号*2+n/2）。

找到1号的递推式，我们接着找2号的递推式。

先关注n项2号与n-1项一对一的关系。

当n==7时，2号等于n==6的（1号*2+1）。

当n==8时，2号等于n==7的（1号*2+1）。

当n==9时，2号等于n==8的（1号*2+1）。

当n==10时，2号等于n==9的（1号*2+1）。

很容易发现递推公式，n项的2号等于n-1项的（2号*2+1）。

找到2号的递推式，我们接着找3号的递推式。

先关注n项3号与n-1项一对一的关系。

当n==7时，3号等于n==6的（1号*2-3）。

当n==8时，3号等于n==7的（1号*2-3）。

当n==9时，3号等于n==8的（1号*2-4）。

当n==10时，3号等于n==9的（1号*2-4）。

很容易发现递推公式，n项的3号等于n-1项的（1号*2-（n-1）/2）。

找到3号的递推式，我们接着找4号的递推式。

先关注n项4号与n-1项一对一的关系。

当n==7时，4号等于n==6的（3号*2）。

当n==8时，4号等于n==7的（3号*2）。

当n==9时，4号等于n==8的（3号*2）。

当n==10时，4号等于n==9的（3号*2）。

很容易发现递推公式，n项的4号等于n-1项的（3号*2）。

接着我们就可以利用递推式直接求前后项的数据。

其实我们可以发现，上述的前后项关系不仅仅是上述的几种，例如n项的1号等于n-1项的（1号+2号），n项的3号等于n-1项的（1号+4号）等等。我们知道的是这些推导公式都可以推导出前后项关系，得到递推式。

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int main(){int n;cin>>n;vector<vector<LL>> a(n+1,vector<LL>(4));a[1][1]=1;for(int i=2;i<=n;i++){a[i][0]=a[i-1][1]+a[i-1][2];a[i][1]=a[i-1][0]*2+1;a[i][2]=a[i-1][3]*2+(i-1)/2;a[i][3]=a[i-1][2]*2;}cout<<"A->B:"<<a[n][0]<<endl;cout<<"A->C:"<<a[n][1]<<endl;cout<<"B->A:"<<a[n][2]<<endl;cout<<"B->C:"<<a[n][0]<<endl;cout<<"C->A:"<<a[n][3]<<endl;cout<<"C->B:"<<a[n][2]<<endl;cout<<"SUM:"<<a[n][0]*2+a[n][1]+a[n][2]*2+a[n][3]<<endl;
}

根据递归图得出数学规律

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int n;cin >> n;LL count_ab = 0, count_ac = 0, count_ba = 0, count_bc = 0, count_ca = 0, count_cb = 0;LL length = 1;for (int i = 1; i <= n; i++) {if (i != 1)length *= 2;if (i % 2 == 1) {LL tempcount = length / 3;count_ac += tempcount;count_cb += tempcount;count_ba += tempcount;LL tempcount1 = length % 3;if (tempcount1 == 1) {count_ac++;} else {count_ac++;count_cb++;}} else {LL tempcount = length / 3;count_ab += tempcount;count_bc += tempcount;count_ca += tempcount;LL tempcount1 = length % 3;if (tempcount1 == 1) {count_ab++;} else {count_ab++;count_bc++;}}}cout << "A->B:" << count_ab << endl;cout << "A->C:" << count_ac << endl;cout << "B->A:" << count_ba << endl;cout << "B->C:" << count_bc << endl;cout << "C->A:" << count_ca << endl;cout << "C->B:" << count_cb << endl;cout << "SUM:" << count_ab + count_ac + count_ba + count_bc + count_ca + count_cb << endl;
}

将递归函数转化为递推式

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int n;cin >> n;vector<vector<LL>> dp(3,vector<LL>(7));dp[1][2] = 1;for (int i = 2; i <= n; i++) {dp[2][1] = dp[1][2] + dp[1][3];dp[2][2] = dp[1][1] + dp[1][4] + 1;dp[2][3] = dp[1][1] + dp[1][5];dp[2][4] = dp[1][2] + dp[1][6];dp[2][5] = dp[1][6] + dp[1][3];dp[2][6] = dp[1][5] + dp[1][4];dp[1][1] = dp[2][1];dp[1][2] = dp[2][2];dp[1][3] = dp[2][3];dp[1][4] = dp[2][4];dp[1][5] = dp[2][5];dp[1][6] = dp[2][6];}cout << "A->B:" << dp[1][1] << endl;cout << "A->C:" << dp[1][2] << endl;cout << "B->A:" << dp[1][3] << endl;cout << "B->C:" << dp[1][4] << endl;cout << "C->A:" << dp[1][5] << endl;cout << "C->B:" << dp[1][6] << endl;cout << "SUM:" << dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5] + dp[1][6] << endl;
}

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！