軟件課講了這些問(wèn)題，這次順便總結(jié)下。
說(shuō)白了也就是：遞歸，回溯，深搜或者廣搜。
1.漢諾塔
////////////////////////////////////////////////
/*
漢諾塔
題目：
假設(shè)有A, B, C 3個(gè)軸，有n個(gè)直徑各不相同，
從小到大依次編號(hào)為1，2，3，…，n的圓盤(pán)
按照從小到大的順序疊放在A軸上。現(xiàn)在要求
將這n個(gè)圓盤(pán)移至C軸上并仍然按照同樣順序
疊放，但圓盤(pán)移動(dòng)時(shí)必須遵守下列規(guī)則：
1.每次只能移動(dòng)一個(gè)圓盤(pán)，它必須位于某個(gè)
軸的頂部。
2.圓盤(pán)可以插在A,B,C中任一軸上。
3.任何時(shí)刻都不能將一個(gè)較大的圓盤(pán)壓在較小
的圓盤(pán)之上。
*/
///////////////////////////////////////////////
經(jīng)典的問(wèn)題，屬于遞歸的入門(mén)級(jí)問(wèn)題，但是同樣不好分析，在n<=4以?xún)?nèi)還可以模擬下漢諾塔的實(shí)現(xiàn)，當(dāng)n>=5時(shí)就不太現(xiàn)實(shí)了，讓我們來(lái)看看漢諾塔當(dāng)圓盤(pán)個(gè)數(shù)n時(shí)有多少組解？ 按照傳說(shuō)來(lái)看：n=64,當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。
但是這畢竟是神話(huà)，不過(guò)當(dāng)把64個(gè)金片全部放到另外一根針時(shí)，確實(shí)要很長(zhǎng)很長(zhǎng)一段時(shí)間。
讓我們來(lái)看看需要多長(zhǎng)時(shí)間。
首先，我們找出遞推關(guān)系：
f(n + 1) = 2*f(n) + 1
至于這個(gè)怎么得到的可以畫(huà)圖看看。
把遞推關(guān)系算出來(lái)后，也就是:
f(n) = 2^n-1
那么當(dāng)n=64時(shí)，是多少？
f(64)= 2^64-1=18446744073709551615
假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一年大約有 31536926 秒，計(jì)算表明移完這些金片需要5800多億年，比地球壽命還要長(zhǎng)，事實(shí)上，世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅。
好吧，說(shuō)了那么多，還是步入正題。
漢諾塔的實(shí)現(xiàn)有遞歸和非遞歸兩種情況，遞歸的很常見(jiàn)，也很簡(jiǎn)單，非遞歸實(shí)際上就是二叉樹(shù)的中序遍歷。也可以認(rèn)為是棧的實(shí)現(xiàn)。
遞歸的版本：
/*遞歸實(shí)現(xiàn)*/
#include <iostream>
using namespace std;
//把n號(hào)圓盤(pán)從x移到y(tǒng)，并打印出。
void Move(int n, char x, char y)
{
cout<< "把" << n << "號(hào)圓盤(pán)從" << x << "移動(dòng)到" << y << endl;
}
//把前n個(gè)通過(guò)b從a移到c
void Hanoi(int n, char a, char b, char c)
{
if(n == 1)
Move(1, a, c);
else
{
Hanoi(n-1, a, c, b);
Move(n, a, c);
Hanoi(n-1, b, a, c);
}
}
int main()
{
int n;
cout << "輸入n的大小: ";
cin >> n;
Hanoi(n, 'a', 'b', 'c');
cout << "Ok!" << endl << "By Tanky Woo." << endl;
return 0;
}
非遞歸的版本有時(shí)間再補(bǔ)上。
2.n皇后
對(duì)于每一個(gè)ACMer,八皇后問(wèn)題都是必經(jīng)之路。
作為搜索類(lèi)題目還是老問(wèn)題：
1.邊界條件。
2.對(duì)每種情況都得遍歷到，可以用解答樹(shù)分析。
3.剪枝 http://www.wutianqi.com/?p=1341(搜索與剪枝)
4.輔助空間的變化。回溯前和回溯后的變化。
如果不用輔助空間的回溯當(dāng)然就不需要注意輔助空間的問(wèn)題了。
以下是n皇后的源碼：
/*
* n皇后問(wèn)題
* Tanky Woo
*/
#include <iostream>
using namespace std;
int queen[100];
int n; // n皇后
int tot = 0; //解法種數(shù)
// www.wutianqi.com
void search(int cur)
{
if(cur == n) //遞歸邊界。符合要求，輸出。
{
tot++;
for(int i=0; i<n; ++i)
cout << queen[i] << " ";
cout << endl;
}
else
{
for(int i=0; i<n; ++i)
{
bool flag = 1;
queen[cur] = i; // 嘗試把第cur行的皇后放在第i列
for(int j=0; j<cur; ++j) // 檢查是否和前面的皇后沖突
if(queen[cur] == queen[j] // 同一列
|| cur-queen[cur] == j-queen[j] // 正對(duì)角線(xiàn)
|| cur+queen[cur] == j+queen[j]) // 反對(duì)角線(xiàn)
{
flag = 0;
break;
}
if(flag)
search(cur+1); // 如果合法，繼續(xù)
}
}
}
int main()
{
cout << "輸入皇后個(gè)數(shù)n: ";
cin >> n;
search(0);
cout << "共有" << tot << "種解." << endl << "By Tanky Woo." << endl;
return 0;
}
對(duì)于這個(gè)問(wèn)題，還可以用輔助空間來(lái)提高算法的效率: 增加輔助空間vis[][]來(lái)判斷是否有其他皇后已經(jīng)在列和對(duì)角線(xiàn)上。
#include <iostream>
using namespace std;
int queen[100];
int n; // n皇后
int tot = 0; //解法種數(shù)
int vis[3][100]; // 輔助空間
void search(int cur)
{
if(cur == n) //遞歸邊界。符合要求，輸出。
{
tot++;
for(int i=0; i<n; ++i)
cout << queen[i] << " ";
cout << endl;
}
else
{
for(int i=0; i<n; ++i)
{
if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n])
{
queen[cur] = i;
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
search(cur+1);
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; //記住要變化來(lái)
}
}
}
}
int main()
{
memset(vis, 0, sizeof(vis));
cout << "輸入皇后個(gè)數(shù)n: ";
cin >> n;
search(0);
cout << "共有" << tot << "種解." << endl << "By Tanky Woo." << endl;
return 0;
}
3.跳馬問(wèn)題：
據(jù)說(shuō)此題證明可以用組合數(shù)學(xué)中的哈密頓環(huán)。
組合數(shù)學(xué)確實(shí)博大精深，看過(guò)一段時(shí)間的組合數(shù)學(xué)，感覺(jué)和實(shí)際聯(lián)系的很多，Orz.
此題有兩種版本：
①：給定一個(gè)N*N的棋盤(pán)，起始點(diǎn)在(0,0)處，要求求出有多少種方法，可以不重復(fù)的遍歷棋盤(pán)上所有的點(diǎn)。
規(guī)則：1.馬走日字
2.走過(guò)的點(diǎn)就不能再走了
此題和上面的n皇后類(lèi)似，是標(biāo)準(zhǔn)的DFS。
分析：從起始點(diǎn)開(kāi)始，每次遍歷八種方向，直到邊界條件，并輸出。
以下是跳馬問(wèn)題一的源碼：
/*馬跳棋盤(pán)問(wèn)題*/
#include <iostream>
using namespace std;
const int N = 10;
int a[N][N] = {0};
int cnt = 0;
void Horse(int a, int b, int t);
// www.wutianqi.com
int main()
{
int i = 0, j = 0, t = 1;
a[i][j] = t;
Horse(i, j, step+1);
cout << cnt << endl;
cout << "By Tanky Woo.\n";
return 0;
}
void Horse(int a, int b, int t)
{
int x[4] ={-2, -1, 1, 2}, y[4] = {-2, -1, 1, 2};
if(t == N*N+1)
cnt++;
for(int i=0; i<4; ++i)
for(int j=0; j<4; ++j)
{
if(x[i]==y[j] || x[i]==-y[j])
continue;
if(a+x[i]>=0 && a+x[i]<N && b+y[j]>=0 && b+y[j]<N && board[a+x[i]][b+y[j]]==0)
{
a[a+x[i]][b+y[j]] = t;
Horse(a+x[i], b+y[j], t+1);
a[a+x[i]][b+y[j]] = 0;
}
}
}
第二個(gè)版本： ②：設(shè)有右圖所示的一個(gè)棋盤(pán)，在棋盤(pán)上的A點(diǎn)，有一個(gè)中國(guó)象棋的馬，并約定馬走的規(guī)則：
規(guī)則：1. 馬走日字
2. 馬只能向右走。
試找出所有從A到B的途徑。
此題也是OI上很有名的騎士問(wèn)題。
此題似乎比較適合BFS.
還沒(méi)嘗試過(guò)。
讓我再想想，好像還有八數(shù)碼和素?cái)?shù)環(huán)問(wèn)題沒(méi)寫(xiě)。
不過(guò)在HDOJ上遇到過(guò)一個(gè)素?cái)?shù)環(huán)的題目：
http://www.wutianqi.com/?p=1329
有興趣可以做下。
對(duì)于DFS和BFS更多的題目，可以在我博客右上角搜索欄里輸入DFS或BFS，會(huì)出來(lái)相應(yīng)題目。