1.河內(nèi)之塔

說(shuō)明：河內(nèi)之塔(Towers of Hanoi)是法國(guó)人M.Claus(Lucas)于1883年從泰國(guó)帶至法國(guó)的，河內(nèi)為越戰(zhàn)時(shí)北越的首都，即現(xiàn)在的胡志明市；1883年法國(guó)數(shù)學(xué)家 EdouardLucas曾提及這個(gè)故事，據(jù)說(shuō)創(chuàng)世紀(jì)時(shí)Benares有一座波羅教塔，是由三支鉆石棒（Pag）所支撐，開(kāi)始時(shí)神在第一根棒上放置64個(gè)由上至下依由小至大排列的金盤(pán)（Disc），并命令僧侶將所有的金盤(pán)從第一根石棒移至第三根石棒，且搬運(yùn)過(guò)程中遵守大盤(pán)子在小盤(pán)子之下的原則，若每日僅搬一個(gè)盤(pán)子，則當(dāng)盤(pán)子全數(shù)搬運(yùn)完畢之時(shí)，此塔將毀損，而也就是世界末日來(lái)臨之時(shí)。

解法：如果柱子標(biāo)為ABC，要由A搬至C，在只有一個(gè)盤(pán)子時(shí)，就將它直接搬至C，當(dāng)有兩個(gè)盤(pán)子，就將B當(dāng)作輔助柱。如果盤(pán)數(shù)超過(guò)2個(gè)，將第三個(gè)以下的盤(pán)子遮起來(lái)，就很簡(jiǎn)單了，每次處理兩個(gè)盤(pán)子，也就是：A->B、A ->C、B->C這三個(gè)步驟，而被遮住的部份，其實(shí)就是進(jìn)入程式的遞回處理。事實(shí)上，若有n個(gè)盤(pán)子，則移動(dòng)完畢所需之次數(shù)為2^n- 1，所以當(dāng)盤(pán)數(shù)為64時(shí)，則所需次數(shù)為：264- 1 = 18446744073709551615為5.05390248594782e+16年，也就是約5000世紀(jì)，如果對(duì)這數(shù)字沒(méi)什幺概念，就假設(shè)每秒鐘搬一個(gè)盤(pán)子好了，也要約5850億年左右。

#include

void hanoi(intn, char A, char B, char C) {

if(n == 1) {

printf("Move sheet %d from %c to%cn", n, A, C);

}

else {

hanoi(n-1, A, C, B);

printf("Move sheet %d from %c to%cn", n, A, C);

hanoi(n-1, B, A, C);

}

}

int main() {

int n;

printf("請(qǐng)輸入盤(pán)數(shù)：");

scanf("%d", &n);

hanoi(n, 'A', 'B', 'C');

return 0;

}

2.AlgorithmGossip: 費(fèi)式數(shù)列

說(shuō)明：Fibonacci為1200年代的歐洲數(shù)學(xué)家，在他的著作中曾經(jīng)提到：「若有一只免子每個(gè)月生一只小免子，一個(gè)月后小免子也開(kāi)始生產(chǎn)。起初只有一只免子，一個(gè)月后就有兩只免子，二個(gè)月后有三只免子，三個(gè)月后有五只免子（小免子投入生產(chǎn)）......。

如果不太理解這個(gè)例子的話，舉個(gè)圖就知道了，注意新生的小免子需一個(gè)月成長(zhǎng)期才會(huì)投入生產(chǎn)，類似的道理也可以用于植物的生長(zhǎng)，這就是Fibonacci數(shù)列，一般習(xí)慣稱之為費(fèi)氏數(shù)列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89......

解法：依說(shuō)明，我們可以將費(fèi)氏數(shù)列定義為以下：

fn = fn-1 + fn-2　　 if n> 1

fn = n　　　　　　 if n = 0, 1

#include

#include

#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

#define N 12

long combi(intn, 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è)定開(kāi)始 */

if(r == 0) {

for(i = 0; i <= (N-n); i++)

printf(" ");

}else {

printf(" ");

} /* 排版設(shè)定結(jié)束 */

printf("%3d", combi(n,r));

}

printf("n");

}

}

4.AlgorithmGossip: 三色棋

說(shuō)明：三色旗的問(wèn)題最早由E.W.Dijkstra所提出，他所使用的用語(yǔ)為Dutch Nation Flag(Dijkstra為荷蘭人)，而多數(shù)的作者則使用Three-ColorFlag來(lái)稱之。

假設(shè)有一條繩子，上面有紅、白、藍(lán)三種顏色的旗子，起初繩子上的旗子顏色并沒(méi)有順序，您希望將之分類，并排列為藍(lán)、白、紅的順序，要如何移動(dòng)次數(shù)才會(huì)最少，注意您只能在繩子上進(jìn)行這個(gè)動(dòng)作，而且一次只能調(diào)換兩個(gè)旗子。

解法：在一條繩子上移動(dòng)，在程式中也就意味只能使用一個(gè)陣列，而不使用其它的陣列來(lái)作輔助，問(wèn)題的解法很簡(jiǎn)單，您可以自己想像一下在移動(dòng)旗子，從繩子開(kāi)頭進(jìn)行，遇到藍(lán)色往前移，遇到白色留在中間，遇到紅色往后移，如下所示：

只是要讓移動(dòng)次數(shù)最少的話，就要有些技巧：

如果圖中W所在的位置為白色，則W+1，表示未處理的部份移至至白色群組。

如果W部份為藍(lán)色，則B與W的元素對(duì)調(diào)，而B(niǎo)與W必須各+1，表示兩個(gè)群組都多了一個(gè)元素。

如果W所在的位置是紅色，則將W與R交換，但R要減1，表示未處理的部份減1。

注意：B、W、R并不是三色旗的個(gè)數(shù)，它們只是一個(gè)移動(dòng)的指標(biāo)；什幺時(shí)候移動(dòng)結(jié)束呢？一開(kāi)始時(shí)未處理的R指標(biāo)會(huì)是等于旗子的總數(shù)，當(dāng)R的索引數(shù)減至少于W的索引數(shù)時(shí)，表示接下來(lái)的旗子就都是紅色了，此時(shí)就可以結(jié)束移動(dòng)，如下所示：

#include

#include

#include

#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','