日志
C語言經(jīng)典算法大全
Ø 老掉牙
河內(nèi)塔
費式數(shù)列
巴斯卡三角形
三色棋
老鼠走迷官（一）
老鼠走迷官（二）
騎士走棋盤
八個皇后
八枚銀幣
生命游戲
字串核對
雙色、三色河內(nèi)塔
背包問題（Knapsack Problem）
Ø 數(shù)、運算
蒙地卡羅法求 PI
Eratosthenes篩選求質(zhì)數(shù)
超長整數(shù)運算（大數(shù)運算）
長 PI
最大公因數(shù)、最小公倍數(shù)、因式分解
完美數(shù)
阿姆斯壯數(shù)
最大訪客數(shù)
中序式轉(zhuǎn)后序式（前序式）
后序式的運算
Ø 關(guān)于賭博
洗撲克牌（亂數(shù)排列）
Craps賭博游戲
約瑟夫問題（Josephus Problem）
Ø 集合問題
排列組合
格雷碼（Gray Code）
產(chǎn)生可能的集合
m元素集合的n個元素子集
數(shù)字拆解
Ø 排序
得分排行
選擇、插入、氣泡排序
Shell 排序法 - 改良的插入排序
Shaker 排序法 - 改良的氣泡排序
Heap 排序法 - 改良的選擇排序
快速排序法（一）
快速排序法（二）
快速排序法（三）
合并排序法
基數(shù)排序法
Ø 搜尋
循序搜尋法（使用衛(wèi)兵）
二分搜尋法（搜尋原則的代表）
插補搜尋法
費氏搜尋法
Ø 矩陣
稀疏矩陣
多維矩陣轉(zhuǎn)一維矩陣
上三角、下三角、對稱矩陣
奇數(shù)魔方陣
4N 魔方陣
2(2N+1) 魔方陣
1.河內(nèi)之塔
說明河內(nèi)之塔(Towers of Hanoi)是法國人M.Claus(Lucas)于1883年從泰國帶至法國的，河內(nèi)為越戰(zhàn)時北越的首都，即現(xiàn)在的胡志明市；1883年法國數(shù)學(xué)家 Edouard Lucas曾提及這個故事，據(jù)說創(chuàng)世紀時Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc），并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數(shù)搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。
解法如果柱子標為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤子，就將B當作輔助柱。如果盤數(shù)超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B、A ->C、B->C這三個步驟，而被遮住的部份，其實就是進入程式的遞回處理。事實上，若有n個盤子，則移動完畢所需之次數(shù)為2^n - 1，所以當盤數(shù)為64時，則所需次數(shù)為：264- 1 = 18446744073709551615為5.05390248594782e+16年，也就是約5000世紀，如果對這數(shù)字沒什幺概念，就假設(shè)每秒鐘搬一個盤子好了，也要約5850億年左右。
#include <stdio.h>
void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
}
else {
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}
}
int main() {
int n;
printf("請輸入盤數(shù)：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
2.Algorithm Gossip: 費式數(shù)列
說明
Fibonacci為1200年代的歐洲數(shù)學(xué)家，在他的著作中曾經(jīng)提到：「若有一只免子每個月生一只小免子，一個月后小免子也開始生產(chǎn)。起初只有一只免子，一個月后就有兩只免子，二個月后有三只免子，三個月后有五只免子（小免子投入生產(chǎn)）......。
如果不太理解這個例子的話，舉個圖就知道了，注意新生的小免子需一個月成長期才會投入生產(chǎn)，類似的道理也可以用于植物的生長，這就是Fibonacci數(shù)列，一般習(xí)慣稱之為費氏數(shù)列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89......
解法
依說明，我們可以將費氏數(shù)列定義為以下：
fn = fn-1 + fn-2 if n > 1
fn = n if n = 0, 1
#include <stdio.h>
#include <stdlib.h>
#define N 20
int main(void) {
int Fib[N] = {0};
int i;
Fib[0] = 0;
Fib[1] = 1;
for(i = 2; i < N; i++)
Fib[i] = Fib[i-1] + Fib[i-2];
for(i = 0; i < N; i++)
printf("%d ", Fib[i]);
printf("\n");
return 0;
}
3. 巴斯卡三角形
#include <stdio.h>
#define N 12
long combi(int n, int r){
int i;
long p = 1;
for(i = 1; i <= r; i++)
p = p * (n-i+1) / i;
return p;
}
void paint() {
int n, r, t;
for(n = 0; n <= N; n++) {
for(r = 0; r <= n; r++) {
int i;/* 排版設(shè)定開始 */
if(r == 0) {
for(i = 0; i <= (N-n); i++)
printf(" ");
}else {
printf(" ");
} /* 排版設(shè)定結(jié)束 */
printf("%3d", combi(n, r));
}
printf("\n");
}
}
4.Algorithm Gossip: 三色棋
說明
三色旗的問題最早由E.W.Dijkstra所提出，他所使用的用語為Dutch Nation Flag(Dijkstra為荷蘭人)，而多數(shù)的作者則使用Three-Color Flag來稱之。
假設(shè)有一條繩子，上面有紅、白、藍三種顏色的旗子，起初繩子上的旗子顏色并沒有順序，您希望將之分類，并排列為藍、白、紅的順序，要如何移動次數(shù)才會最少，注意您只能在繩子上進行這個動作，而且一次只能調(diào)換兩個旗子。
解法
在一條繩子上移動，在程式中也就意味只能使用一個陣列，而不使用其它的陣列來作輔助，問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進行，遇到藍色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：
只是要讓移動次數(shù)最少的話，就要有些技巧：
如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。
如果W部份為藍色，則B與W的元素對調(diào)，而B與W必須各+1，表示兩個群組都多了一個元素。
如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。
注意B、W、R并不是三色旗的個數(shù)，它們只是一個移動的指標；什幺時候移動結(jié)束呢？一開始時未處理的R指標會是等于旗子的總數(shù)，當R的索引數(shù)減至少于W的索引數(shù)時，表示接下來的旗子就都是紅色了，此時就可以結(jié)束移動，如下所示：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED 'r'
#define SWAP(x, y) { char temp; \
temp = color[x]; \
color[x] = color[y]; \
color[y] = temp; }
int main() {
char color[] = {'r', 'w', 'b', 'w', 'w',
'b', 'r', 'b', 'w', 'r', '\0'};
int wFlag = 0;
int bFlag = 0;
int rFlag = strlen(color) - 1;
int i;
for(i = 0; i < strlen(color); i++)
printf("%c ", color[i]);
printf("\n");
while(wFlag <= rFlag) {
if(color[wFlag] == WHITE)
wFlag++;
else if(color[wFlag] == BLUE) {
SWAP(bFlag, wFlag);
bFlag++; wFlag++;
}
else {
while(wFlag < rFlag && color[rFlag] == RED)
rFlag--;
SWAP(rFlag, wFlag);
rFlag--;
}
}
for(i = 0; i < strlen(color); i++)
printf("%c ", color[i]);
printf("\n");
return 0;
}
5.Algorithm Gossip: 老鼠走迷官（一）
說明老鼠走迷宮是遞回求解的基本題型，我們在二維陣列中使用2表示迷宮墻壁，使用1來表示老鼠的行走路徑，試以程式求出由入口至出口的路徑。
解法老鼠的走法有上、左、下、右四個方向，在每前進一格之后就選一個方向前進，無法前進時退回選擇下一個可前進方向，如此在陣列中依序測試四個方向，直到走到出口為止，這是遞回的基本題，請直接看程式應(yīng)就可以理解。
#include <stdio.h>
#include <stdlib.h>
int visit(int, int);
int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1; // 入口
int endI = 5, endJ = 5; // 出口
int success = 0;
int main(void) {
int i, j;
printf("顯示迷宮：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf(" ");
printf("\n");
}
if(visit(startI, startJ) == 0)
printf("\n沒有找到出口！\n");
else {
printf("\n顯示路徑：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++) {
if(maze[i][j] == 2)
printf("█");
else if(maze[i][j] == 1)
printf("◇");
else
printf(" ");
}
printf("\n");
}
}
return 0;
}
int visit(int i, int j) {
maze[i][j] = 1;
if(i == endI && j == endJ)
success = 1;
if(success != 1 && maze[i][j+1] == 0) visit(i, j+1);
if(success != 1 && maze[i+1][j] == 0) visit(i+1, j);
if(success != 1 && maze[i][j-1] == 0) visit(i, j-1);
if(success != 1 && maze[i-1][j] == 0) visit(i-1, j);
if(success != 1)
maze[i][j] = 0;
return success;
}
6.Algorithm Gossip: 老鼠走迷官（二）
說明由于迷宮的設(shè)計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？
解法求所有路徑看起來復(fù)雜但其實更簡單，只要在老鼠走至出口時顯示經(jīng)過的路徑，然后退回上一格重新選擇下一個位置繼續(xù)遞回就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。
#include <stdio.h>
#include <stdlib.h>
void visit(int, int);
int maze[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1; // 入口
int endI = 7, endJ = 7; // 出口
int main(void) {
int i, j;
printf("顯示迷宮：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf(" ");
printf("\n");
}
visit(startI, startJ);
return 0;
}
void visit(int i, int j) {
int m, n;
maze[i][j] = 1;
if(i == endI && j == endJ) {
printf("\n顯示路徑：\n");
for(m = 0; m < 9; m++) {
for(n = 0; n < 9; n++)
if(maze[m][n] == 2)
printf("█");
else if(maze[m][n] == 1)
printf("◇");
else
printf(" ");
printf("\n");
}
}
if(maze[i][j+1] == 0) visit(i, j+1);
if(maze[i+1][j] == 0) visit(i+1, j);
if(maze[i][j-1] == 0) visit(i, j-1);
if(maze[i-1][j] == 0) visit(i-1, j);
maze[i][j] = 0;
}
7.Algorithm Gossip: 騎士走棋盤
說明騎士旅游（Knight tour）在十八世紀初倍受數(shù)學(xué)家與拼圖迷的注意，它什么時候被提出已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個位置出發(fā)，它要如何走完[所有的位置？
解法騎士的走法，基本上可以使用遞回來解決，但是純綷的遞回在維度大時相當沒有效率，一個聰明的解法由J.C. Warnsdorff在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時，所能走的步數(shù)最少的一步。」，使用這個方法，在不使用遞回的情況下，可以有較高的機率找出走法（找不到走法的機會也是有的）。
#include <stdio.h>
int board[8][8] = {0};
int main(void) {
int startx, starty;
int i, j;
printf("輸入起始點：");
scanf("%d %d", &startx, &starty);
if(travel(startx, starty)) {
printf("游歷完成！\n");
}
else {
printf("游歷失敗！\n");
}
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
printf("%2d ", board[i][j]);
}
putchar('\n');
}
return 0;
}
int travel(int x, int y) {
// 對應(yīng)騎士可走的八個方向
int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};
// 測試下一步的出路
int nexti[8] = {0};
int nextj[8] = {0};
// 記錄出路的個數(shù)
int exists[8] = {0};
int i, j, k, m, l;
int tmpi, tmpj;
int count, min, tmp;
i = x;
j = y;
board[i][j] = 1;
for(m = 2; m <= 64; m++) {
for(l = 0; l < 8; l++)
exists[l] = 0;
l = 0;
// 試探八個方向
for(k = 0; k < 8; k++) {
tmpi = i + ktmove1[k];
tmpj = j + ktmove2[k];
// 如果是邊界了，不可走
if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)
continue;
// 如果這個方向可走，記錄下來
if(board[tmpi][tmpj] == 0) {
nexti[l] = tmpi;
nextj[l] = tmpj;
// 可走的方向加一個
l++;
}
}
count = l;
// 如果可走的方向為0個，返回
if(count == 0) {
return 0;
}
else if(count == 1) {
// 只有一個可走的方向
// 所以直接是最少出路的方向
min = 0;
}
else {
// 找出下一個位置的出路數(shù)
for(l = 0; l < count; l++) {
for(k = 0; k < 8; k++) {
tmpi = nexti[l] + ktmove1[k];
tmpj = nextj[l] + ktmove2[k];
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
if(board[tmpi][tmpj] == 0)
exists[l]++;
}
}
tmp = exists[0];
min = 0;
// 從可走的方向中尋找最少出路的方向
for(l = 1; l < count; l++) {
if(exists[l] < tmp) {
tmp = exists[l];
min = l;
}
}
}
// 走最少出路的方向
i = nexti[min];
j = nextj[min];
board[i][j] = m;
}
return 1;
}
8.Algorithm Gossip: 八皇后
說明西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在棋盤上，1970年與1971年， E.W.Dijkstra與N.Wirth曾經(jīng)用這個問題來講解程式設(shè)計之技巧。
解法關(guān)于棋盤的問題，都可以用遞回求解，然而如何減少遞回的次數(shù)？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就不用再檢查了，這個方法稱為分支修剪。
#include <stdio.h>
#include <stdlib.h>
#define N 8
int column[N+1]; // 同欄是否有皇后，1表示有
int rup[2*N+1]; // 右上至左下是否有皇后
int lup[2*N+1]; // 左上至右下是否有皇后
int queen[N+1] = {0};
int num; // 解答編號
void backtrack(int); // 遞回求解
int main(void) {
int i;
num = 0;
for(i = 1; i <= N; i++)
column[i] = 1;
for(i = 1; i <= 2*N; i++)
rup[i] = lup[i] = 1;
backtrack(1);
return 0;
}
void showAnswer() {
int x, y;
printf("\n解答 %d\n", ++num);
for(y = 1; y <= N; y++) {
for(x = 1; x <= N; x++) {
if(queen[y] == x) {
printf(" Q");
}
else {
printf(" .");
}
}
printf("\n");
}
}
void backtrack(int i) {
int j;
if(i > N) {
showAnswer();
}
else {
for(j = 1; j <= N; j++) {
if(column[j] == 1 &&
rup[i+j] == 1 && lup[i-j+N] == 1) {
queen[i] = j;
// 設(shè)定為占用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;
}
}
}
}
9.Algorithm Gossip: 八枚銀幣
說明現(xiàn)有八枚銀幣a b c d e f g h，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。
解法單就求假幣的問題是不難，但問題限制使用最少的比較次數(shù)，所以我們不能以單純的回圈比較來求解，我們可以使用決策樹（decision tree），使用分析與樹狀圖來協(xié)助求解。一個簡單的狀況是這樣的，我們比較a+b+c與d+e+f ，如果相等，則假幣必是g或h，我們先比較g或h哪個較重，如果g較重，再與a比較（a是真幣），如果g等于a，則g為真幣，則h為假幣，由于h比g輕而 g是真幣，則h假幣的重量比真幣輕。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void compare(int[], int, int, int);
void eightcoins(int[]);
int main(void) {
int coins[8] = {0};
int i;
srand(time(NULL));
for(i = 0; i < 8; i++)
coins[i] = 10;
printf("\n輸入假幣重量(比10大或小)：");
scanf("%d", &i);
coins[rand() % 8] = i;
eightcoins(coins);
printf("\n\n列出所有錢幣重量：");
for(i = 0; i < 8; i++)
printf("%d ", coins[i]);
printf("\n");
return 0;
}
void compare(int coins[], int i, int j, int k) {
if(coins[i] > coins[k])
printf("\n假幣 %d 較重", i+1);
else
printf("\n假幣 %d 較輕", j+1);
}
void eightcoins(int coins[]) {
if(coins[0]+coins[1]+coins[2] ==
coins[3]+coins[4]+coins[5]) {
if(coins[6] > coins[7])
compare(coins, 6, 7, 0);
else
compare(coins, 7, 6, 0);
}
else if(coins[0]+coins[1]+coins[2] >
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(coins, 2, 5, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(coins, 0, 4, 1);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(coins, 1, 3, 0);
}
else if(coins[0]+coins[1]+coins[2] <
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(coins, 5, 2, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(coins, 3, 1, 0);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(coins, 4, 0, 1);
}
}
10.Algorithm Gossip: 生命游戲
說明生命游戲（game of life）為1970年由英國數(shù)學(xué)家J. H. Conway所提出，某一細胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細胞，游戲規(guī)則如下：
孤單死亡：如果細胞的鄰居小于一個，則該細胞在下一次狀態(tài)將死亡。
擁擠死亡：如果細胞的鄰居在四個以上，則該細胞在下一次狀態(tài)將死亡。
穩(wěn)定：如果細胞的鄰居為二個或三個，則下一次狀態(tài)為穩(wěn)定存活。
復(fù)活：如果某位置原無細胞存活，而該位置的鄰居為三個，則該位置將復(fù)活一細胞。
解法生命游戲的規(guī)則可簡化為以下，并使用CASE比對即可使用程式實作：
鄰居個數(shù)為0、1、4、5、6、7、8時，則該細胞下次狀態(tài)為死亡。
鄰居個數(shù)為2時，則該細胞下次狀態(tài)為復(fù)活。
鄰居個數(shù)為3時，則該細胞下次狀態(tài)為穩(wěn)定。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXROW 10
#define MAXCOL 25
#define DEAD 0
#define ALIVE 1
int map[MAXROW][MAXCOL], newmap[MAXROW][MAXCOL];
void init();
int neighbors(int, int);
void outputMap();
void copyMap();
int main() {
int row, col;
char ans;
init();
while(1) {
outputMap();
for(row = 0; row < MAXROW; row++) {
for(col = 0; col < MAXCOL; col++) {
switch (neighbors(row, col)) {
case 0:
case 1:
case 4:
case 5:
case 6:
case 7:
case 8:
newmap[row][col] = DEAD;
break;
case 2:
newmap[row][col] = map[row][col];
break;
case 3:
newmap[row][col] = ALIVE;
break;
}
}
}
copyMap();
printf("\nContinue next Generation ? ");
getchar();
ans = toupper(getchar());
if(ans != 'Y') break;
}
return 0;
}
void init() {
int row, col;
for(row = 0; row < MAXROW; row++)
for(col = 0; col < MAXCOL; col++)
map[row][col] = DEAD;
puts("Game of life Program");
puts("Enter x, y where x, y is living cell");
printf("0 <= x <= %d, 0 <= y <= %d\n",
MAXROW-1, MAXCOL-1);
puts("Terminate with x, y = -1, -1");
while(1) {
scanf("%d %d", &row, &col);
if(0 <= row && row < MAXROW &&
0 <= col && col < MAXCOL)
map[row][col] = ALIVE;
else if(row == -1 || col == -1)
break;
else
printf("(x, y) exceeds map ranage!");
}
}
int neighbors(int row, int col) {
int count = 0, c, r;
for(r = row-1; r <= row+1; r++)
for(c = col-1; c <= col+1; c++) {
if(r < 0 || r >= MAXROW || c < 0 || c >= MAXCOL)
continue;
if(map[r][c] == ALIVE)
count++;
}
if(map[row][col] == ALIVE)
count--;
return count;
}
void outputMap() {
int row, col;
printf("\n\n%20cGame of life cell status\n");
for(row = 0; row < MAXROW; row++) {
printf("\n%20c", ' ');
for(col = 0; col < MAXCOL; col++)
if(map[row][col] == ALIVE) putchar('#');
else putchar('-');
}
}
void copyMap() {
int row, col;
for(row = 0; row < MAXROW; row++)
for(col = 0; col < MAXCOL; col++)
map[row][col] = newmap[row][col];
}
11.Algorithm Gossip: 字串核對
說明今日的一些高階程式語言對于字串的處理支援越來越強大（例如Java、Perl等），不過字串搜尋本身仍是個值得探討的課題，在這邊以Boyer- Moore法來說明如何進行字串說明，這個方法快且原理簡潔易懂。
解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統(tǒng)的字串搜尋是從關(guān)鍵字與字串的開頭開始比對，例如 Knuth-Morris-Pratt 演算法 字串搜尋，這個方法也不錯，不過要花時間在公式計算上；Boyer-Moore字串核對改由關(guān)鍵字的后面開始核對字串，并制作前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設(shè)是p好了，然后比對字串中p-n+1至p的值是否與關(guān)鍵字相同。
如果關(guān)鍵字中有重復(fù)出現(xiàn)的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關(guān)鍵字，t的前進值應(yīng)該取后面的3而不是取前面的7。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void table(char*); // 建立前進表
int search(int, char*, char*); // 搜尋關(guān)鍵字
void substring(char*, char*, int, int); // 取出子字串
int skip[256];
int main(void) {
char str_input[80];
char str_key[80];
char tmp[80] = {'\0'};
int m, n, p;
printf("請輸入字串：");
gets(str_input);
printf("請輸入搜尋關(guān)鍵字：");
gets(str_key);
m = strlen(str_input); // 計算字串長度
n = strlen(str_key);
table(str_key);
p = search(n-1, str_input, str_key);
while(p != -1) {
substring(str_input, tmp, p, m);
printf("%s\n", tmp);
p = search(p+n+1, str_input, str_key);
}
printf("\n");
return 0;
}
void table(char *key) {
int k, n;
n = strlen(key);
for(k = 0; k <= 255; k++)
skip[k] = n;
for(k = 0; k < n - 1; k++)
skip[key[k]] = n - k - 1;
}
int search(int p, char* input, char* key) {
int i, m, n;
char tmp[80] = {'\0'};
m = strlen(input);
n = strlen(key);
while(p < m) {
substring(input, tmp, p-n+1, p);
if(!strcmp(tmp, key)) // 比較兩字串是否相同
return p-n+1;
p += skip[input[p]];
}
return -1;
}
void substring(char *text, char* tmp, int s, int e) {
int i, j;
for(i = s, j = 0; i <= e; i++, j++)
mp[j] = text[i];
tmp[j] = '\0';
}
12.Algorithm Gossip: 雙色、三色河內(nèi)塔
說明雙色河內(nèi)塔與三色河內(nèi)塔是由之前所介紹過的河內(nèi)塔規(guī)則衍生而來，雙色河內(nèi)塔的目的是將下圖左上的圓環(huán)位置經(jīng)移動成為右下的圓環(huán)位置：
而三色河內(nèi)塔則是將下圖左上的圓環(huán)經(jīng)移動成為右上的圓環(huán)：
解法無論是雙色河內(nèi)塔或是三色河內(nèi)塔，其解法觀念與之前介紹過的河內(nèi)塔是類似的，同樣也是使用遞回來解，不過這次遞回解法的目的不同，我們先來看只有兩個盤的情況，這很簡單，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍色移動至第三柱。
再來是四個盤的情況，首先必須用遞回完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第一柱的上面兩個盤子就可以了。那么六個盤的情況呢？一樣！首先必須用遞回完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何進行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。
那么三色河內(nèi)塔呢？一樣，直接來看九個盤的情況，首先必須完成下圖的移動結(jié)果：
接下來最底兩層的就不用管它們了，因為它們已經(jīng)就定位，只要再處理第一柱上面的三個盤子就可以了。
雙色河內(nèi)塔 C 實作
#include <stdio.h>
void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}
void hanoi2colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
for(i = disks / 2; i > 1; i--) {
hanoi(i-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(i-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
}
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
}
int main() {
int n;
printf("請輸入盤數(shù)：");
scanf("%d", &n);
hanoi2colors(n);
return 0;
}
三色河內(nèi)塔 C 實作
#include <stdio.h>
void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}
void hanoi3colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
if(disks == 3) {
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, source);
printf("move disk from %c to %c\n", target, temp);;
}
else {
hanoi(disks/3-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(disks/3-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
hanoi(disks/3-1, source, target, temp);
printf("move disk from %c to %c\n", target, source);
printf("move disk from %c to %c\n", target, source);
hanoi(disks/3-1, temp, source, target);
printf("move disk from %c to %c\n", source, temp);
for (i = disks / 3 - 1; i > 0; i--) {
if (i>1) {
hanoi(i-1, target, source, temp);
}
printf("move disk from %c to %c\n",target, source);
printf("move disk from %c to %c\n",target, source);
if (i>1) {
hanoi(i-1, temp, source, target);
}
printf("move disk from %c to %c\n", source, temp);
}
}
}
int main() {
int n;
printf("請輸入盤數(shù)：");
scanf("%d", &n);
hanoi3colors(n);
return 0;
}
