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