目錄

漢諾塔遞歸

漢諾塔子移動(dòng)次數(shù)的計(jì)算

牛牛的漢諾塔

選擇正常的遞歸模擬計(jì)算子移動(dòng)次數(shù)

根據(jù)具體數(shù)據(jù)得出數(shù)學(xué)規(guī)律

根據(jù)遞歸圖得出數(shù)學(xué)規(guī)律

將遞歸函數(shù)轉(zhuǎn)化為遞推式

結(jié)尾

---

漢諾塔遞歸

漢諾塔是一個(gè)經(jīng)典問題，相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置n個(gè)金盤。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

漢諾塔以及其衍生問題往往使用遞歸來求解，也是學(xué)習(xí)和理解遞歸很好的老師。

其偽代碼如下

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 

定義遞歸函數(shù)hanoi(n,a,b,c)表示將n個(gè)盤子從a柱移動(dòng)到c柱，以b柱為輔助柱。

維護(hù)定義的含義，內(nèi)部邏輯先將n-1個(gè)盤子從a柱移動(dòng)到b柱，以c柱為輔助柱。再將最大盤子從a柱移動(dòng)到c柱，以b柱為輔助柱。最后將n-1個(gè)盤子從b柱移動(dòng)到c柱，以a柱為輔助柱。

遞歸結(jié)束出口為n==1時(shí)，從a柱移動(dòng)到c柱，以b柱為輔助柱。

C++代碼

#include <iostream>
using namespace std;// 函數(shù)聲明
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);
}

漢諾塔子移動(dòng)次數(shù)的計(jì)算

牛牛的漢諾塔

鏈接：登錄—專業(yè)IT筆試面試備考平臺_?？途W(wǎng) 來源：?？途W(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 262144K，其他語言524288K

64bit IO Format: %lld

題目描述

漢諾塔是一個(gè)經(jīng)典問題，相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置n個(gè)金盤。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

漢諾塔以及其衍生問題往往使用遞歸來求解，也是學(xué)習(xí)和理解遞歸很好的老師。

其偽代碼如下

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

牛牛很快就理解了代碼的意思并且寫出了求解漢諾塔的程序，他現(xiàn)在想研究漢諾塔的規(guī)律。

請你統(tǒng)計(jì)以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次數(shù)，以及所有移動(dòng)的總步數(shù)。

輸入描述:

僅一行，輸入一個(gè)正整數(shù)n(1≤n≤60)(1 leq n leq 60)(1≤n≤60)表示漢諾塔的層數(shù)。

輸出描述:

首先輸出6行

A->B:XX

A->C:XX

B->A:XX

B->C:XX

C->A:XX

C->B:XX

分別表示每種移動(dòng)情況出現(xiàn)的次數(shù)

最后輸出一行

SUM:XX

表示所有移動(dòng)情況的總和。

示例1

輸入

復(fù)制3

3

輸出

復(fù)制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

說明

偽代碼所示算法的移動(dòng)序列如下：

A->C

A->B

C->B

A->C

B->A

B->C

A->C

統(tǒng)計(jì)：

A->B出現(xiàn)1次

A->C出現(xiàn)3次

B->C出現(xiàn)1次

B->A出現(xiàn)1次

C->B出現(xiàn)1次

總計(jì)7次

選擇正常的遞歸模擬計(jì)算子移動(dòng)次數(shù)

#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;
}

我們可以通過遞歸關(guān)系式來表達(dá)這個(gè)問題的解法次數(shù)。對于n個(gè)盤子，移動(dòng)它們所需的步驟T(n)可以表示為：

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

這里的思路是：移動(dòng)n-1個(gè)盤子到臨時(shí)柱子（這需要T(n-1)步），移動(dòng)最大的盤子到目標(biāo)柱子（這需要1步），最后再將n-1個(gè)盤子從臨時(shí)柱子移動(dòng)到目標(biāo)柱子上（再次需要T(n-1)步）。

我們可以進(jìn)一步解開這個(gè)遞歸式：

• 當(dāng)n = 1時(shí)，只需要移動(dòng)一次，所以T(1) = 1。

• 當(dāng)n = 2時(shí)，T(2) = 2T(1) + 1 = 3。

• 當(dāng)n = 3時(shí)，T(3) = 2T(2) + 1 = 7。

以此類推，我們發(fā)現(xiàn)這是一個(gè)等比數(shù)列的求和問題，其總和公式為：

T(n)=2^n?1

因此，漢諾塔問題的時(shí)間復(fù)雜度為O(2^n)。這個(gè)復(fù)雜度表明了隨著盤子數(shù)量的增加，需要的移動(dòng)次數(shù)呈指數(shù)級增長，這也解釋了為什么漢諾塔問題在盤子數(shù)量稍多時(shí)就變得難以直接通過手動(dòng)移動(dòng)來解決。

當(dāng)n==60時(shí)，時(shí)間復(fù)雜度是O(2^60)，2^10≈1000=10^3，2^60==2^10*2^10*2^10*2^10*2^10*2^10。也就是六個(gè)10^3相乘，等于10^18遠(yuǎn)遠(yuǎn)超過10^9，10^9對應(yīng)的時(shí)間大概是1s，這樣的遞歸是一定會超時(shí)的。

根據(jù)具體數(shù)據(jù)得出數(shù)學(xué)規(guī)律

我們將正常遞歸模擬計(jì)算子移動(dòng)次數(shù)的代碼進(jìn)行修改，用來計(jì)算前n項(xiàng)的子移動(dòng)次數(shù)數(shù)據(jù)。

#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。

我們希望找出前后項(xiàng)的規(guī)律，很容易發(fā)現(xiàn)，同一個(gè)n中，1號等于4號，3號等于6號。

因此我們將數(shù)據(jù)截取出1,2,3,5四列數(shù)據(jù)。做法很簡單，只需要簡單修改代碼即可。

#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

我們希望由上面的數(shù)據(jù)找出前后項(xiàng)的關(guān)系，我們對a->b,a->c,b->a,c->a重新進(jìn)行編號，分別記為1,2,3,4。

我們需要用的n-1項(xiàng)的1,2,3,4號數(shù)據(jù)推導(dǎo)出n項(xiàng)的1,2,3,4號數(shù)據(jù)。

找規(guī)律的思路是，我們可以先關(guān)注n項(xiàng)的1號數(shù)據(jù)，看n-1項(xiàng)的某一號數(shù)據(jù)是否可以單獨(dú)推導(dǎo)出n項(xiàng)的1號數(shù)據(jù)。1對1的關(guān)系。如果1對1的關(guān)系找不到，那就找n-1項(xiàng)的多號數(shù)據(jù)是否可以推導(dǎo)出1號數(shù)據(jù)，以此類推。

先關(guān)注n項(xiàng)1號與n-1項(xiàng)一對一的關(guān)系。

當(dāng)n==7時(shí)，1號等于n==6的（2號*2-3），等于（3號*2+3）。

當(dāng)n==8時(shí)，1號等于n==7的（2號*2-4），等于（3號*2+4）。

當(dāng)n==9時(shí)，1號等于n==8的（2號*2-4），等于（3號*2+4）。

當(dāng)n==10時(shí)，1號等于n==9的（2號*2-5），等于（3號*2+5）。

很容易發(fā)現(xiàn)遞推公式，n項(xiàng)的1號等于n-1項(xiàng)的（2號*2-n/2）或者等于（3號*2+n/2）。

找到1號的遞推式，我們接著找2號的遞推式。

先關(guān)注n項(xiàng)2號與n-1項(xiàng)一對一的關(guān)系。

當(dāng)n==7時(shí)，2號等于n==6的（1號*2+1）。

當(dāng)n==8時(shí)，2號等于n==7的（1號*2+1）。

當(dāng)n==9時(shí)，2號等于n==8的（1號*2+1）。

當(dāng)n==10時(shí)，2號等于n==9的（1號*2+1）。

很容易發(fā)現(xiàn)遞推公式，n項(xiàng)的2號等于n-1項(xiàng)的（2號*2+1）。

找到2號的遞推式，我們接著找3號的遞推式。

先關(guān)注n項(xiàng)3號與n-1項(xiàng)一對一的關(guān)系。

當(dāng)n==7時(shí)，3號等于n==6的（1號*2-3）。

當(dāng)n==8時(shí)，3號等于n==7的（1號*2-3）。

當(dāng)n==9時(shí)，3號等于n==8的（1號*2-4）。

當(dāng)n==10時(shí)，3號等于n==9的（1號*2-4）。

很容易發(fā)現(xiàn)遞推公式，n項(xiàng)的3號等于n-1項(xiàng)的（1號*2-（n-1）/2）。

找到3號的遞推式，我們接著找4號的遞推式。

先關(guān)注n項(xiàng)4號與n-1項(xiàng)一對一的關(guān)系。

當(dāng)n==7時(shí)，4號等于n==6的（3號*2）。

當(dāng)n==8時(shí)，4號等于n==7的（3號*2）。

當(dāng)n==9時(shí)，4號等于n==8的（3號*2）。

當(dāng)n==10時(shí)，4號等于n==9的（3號*2）。

很容易發(fā)現(xiàn)遞推公式，n項(xiàng)的4號等于n-1項(xiàng)的（3號*2）。

接著我們就可以利用遞推式直接求前后項(xiàng)的數(shù)據(jù)。

其實(shí)我們可以發(fā)現(xiàn)，上述的前后項(xiàng)關(guān)系不僅僅是上述的幾種，例如n項(xiàng)的1號等于n-1項(xiàng)的（1號+2號），n項(xiàng)的3號等于n-1項(xiàng)的（1號+4號）等等。我們知道的是這些推導(dǎo)公式都可以推導(dǎo)出前后項(xiàng)關(guān)系，得到遞推式。

#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;
}

根據(jù)遞歸圖得出數(shù)學(xué)規(guī)律

#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;
}

將遞歸函數(shù)轉(zhuǎn)化為遞推式

#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;
}

結(jié)尾

最后，感謝您閱讀我的文章，希望這些內(nèi)容能夠?qū)δ兴鶈l(fā)和幫助。如果您有任何問題或想要分享您的觀點(diǎn)，請隨時(shí)在評論區(qū)留言。

同時(shí)，不要忘記訂閱我的博客以獲取更多有趣的內(nèi)容。在未來的文章中，我將繼續(xù)探討這個(gè)話題的不同方面，為您呈現(xiàn)更多深度和見解。

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