其他經(jīng)典例題跳轉(zhuǎn)鏈接

C語言經(jīng)典算法-1
1.漢若塔 2. 費(fèi)式數(shù)列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官（一）6. 老鼠走迷官（二）7. 騎士走棋盤8. 八皇后9. 八枚銀幣10. 生命游戲

C語言經(jīng)典算法-2
字串核對(duì)、雙色、三色河內(nèi)塔、背包問題（Knapsack Problem）、蒙地卡羅法求 PI、Eratosthenes篩選求質(zhì)數(shù)

C語言經(jīng)典算法-3
超長整數(shù)運(yùn)算（大數(shù)運(yùn)算）、長 PI、最大公因數(shù)、最小公倍數(shù)、因式分解、完美數(shù)、阿姆斯壯數(shù)

C語言經(jīng)典算法-4
最大訪客數(shù)、中序式轉(zhuǎn)后序式（前序式）、后序式的運(yùn)算、洗撲克牌（亂數(shù)排列）、Craps賭博游戲

C語言經(jīng)典算法-5
約瑟夫問題（Josephus Problem）、排列組合、格雷碼（Gray Code)、產(chǎn)生可能的集合、m元素集合的n個(gè)元素子集

C語言經(jīng)典算法-6
數(shù)字拆解、得分排行，選擇、插入、氣泡排序、Shell 排序法 - 改良的插入排序、Shaker 排序法 - 改良的氣泡排序

C語言經(jīng)典算法-7
排序法 - 改良的選擇排序、快速排序法（一）、快速排序法（二）、快速排序法（三）、合并排序法

C語言經(jīng)典算法-8
基數(shù)排序法、循序搜尋法（使用衛(wèi)兵）、二分搜尋法（搜尋原則的代表）、插補(bǔ)搜尋法、費(fèi)氏搜尋法

C語言經(jīng)典算法-9
稀疏矩陣、多維矩陣轉(zhuǎn)一維矩陣、上三角、下三角、對(duì)稱矩陣、奇數(shù)魔方陣、4N 魔方陣、2(2N+1) 魔方陣

31.數(shù)字拆解

說明
這個(gè)題目來自于 數(shù)字拆解，我將之改為C語言的版本，并加上說明。

題目是這樣的：
3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

共七種

依此類推，請(qǐng)問一個(gè)指定數(shù)字NUM的拆解方法個(gè)數(shù)有多少個(gè)？
解法
我們以上例中最后一個(gè)數(shù)字5的拆解為例，假設(shè)f( n )為數(shù)字n的可拆解方式個(gè)數(shù)，而f(x, y)為使用y以下的數(shù)字來拆解x的方法個(gè)數(shù)，則觀察：
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

使用函式來表示的話：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)

其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大于1的數(shù)字來拆解1沒有意義，所以f(1, 4) = f(1, 1)，而同樣的，f(0, 5)會(huì)等于f(0, 0)，所以：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)

依照以上的說明，使用動(dòng)態(tài)程式規(guī)畫（Dynamic programming）來進(jìn)行求解，其中f(4,1)其實(shí)就是f(5-1, min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n為要拆解的數(shù)字，而min()表示取兩者中較小的數(shù)。

使用一個(gè)二維陣列表格table[x][y]來表示f(x, y)，剛開始時(shí)，將每列的索引0與索引1元素值設(shè)定為1，因?yàn)槿魏螖?shù)以0以下的數(shù)拆解必只有1種，而任何數(shù)以1以下的數(shù)拆解也必只有1種：

for(i = 0; i < NUM +1; i++){ table[i][0] = 1; // 任何數(shù)以0以下的數(shù)拆解必只有1種 table[i][1] = 1; // 任何數(shù)以1以下的數(shù)拆解必只有1種 
}

接下來就開始一個(gè)一個(gè)進(jìn)行拆解了，如果數(shù)字為NUM，則我們的陣列維度大小必須為NUM x (NUM/2+1)，以數(shù)字10為例，其維度為10 x 6我們的表格將會(huì)如下所示：
1 1 0 0 0 0
1 1 0 0 0 0
1 1 2 0 0 0
1 1 2 3 0 0
1 1 3 4 5 0
1 1 3 5 6 7
1 1 4 7 9 0
1 1 4 8 0 0
1 1 5 0 0 0
1 1 0 0 0 0

實(shí)作

C 
#include <stdio.h> 
#include <stdlib.h> 
#define NUM 10    //  要拆解的數(shù)字 
#define DEBUG 0 int main(void) { int table[NUM][NUM/2+1] = {0}; // 動(dòng)態(tài)規(guī)畫表格 int count = 0; int result = 0; int i, j, k; printf("數(shù)字拆解\n"); printf("3 = 2+1 = 1+1+1 所以3有三種拆法\n"); printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");   printf("共五種\n"); printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");printf("共七種\n"); printf("依此類推，求 %d 有幾種拆法？", NUM); // 初始化 for(i = 0; i < NUM; i++){ table[i][0] = 1;  // 任何數(shù)以0以下的數(shù)拆解必只有1種 table[i][1] = 1;  // 任何數(shù)以1以下的數(shù)拆解必只有1種 }        // 動(dòng)態(tài)規(guī)劃 for(i = 2; i <= NUM; i++){ for(j = 2; j <= i; j++){ if(i + j > NUM) // 大于 NUM continue; count = 0;    for(k = 1 ; k <= j; k++){ count += table[i-k][(i-k >= k) ? k : i-k];                  } table[i][j] = count; }            } // 計(jì)算并顯示結(jié)果 for(k = 1 ; k <= NUM; k++) result += table[NUM-k][(NUM-k >= k) ? k : NUM-k];                    printf("\n\nresult: %d\n", result); if(DEBUG) { printf("\n除錯(cuò)資訊\n"); for(i = 0; i < NUM; i++) { for(j = 0; j < NUM/2+1; j++) printf("%2d", table[i][j]); printf("\n"); } } return 0; 
} 

32.得分排行

說明假設(shè)有一教師依學(xué)生座號(hào)輸入考試分?jǐn)?shù)，現(xiàn)希望在輸入完畢后自動(dòng)顯示學(xué)生分?jǐn)?shù)的排行，當(dāng)然學(xué)生的分?jǐn)?shù)可能相同。
解法這個(gè)問題基本上要解不難，只要使用額外的一個(gè)排行陣列走訪分?jǐn)?shù)陣列就可以了，直接使用下面的程式片段作說明：

for(i = 0; i < count; i++) { juni[i] = 1; for(j = 0; j < count; j++) { if(score[j] > score[i]) juni[i]++; } 
} 
printf("得分\t排行\(zhòng)n"); 
for(i = 0; i < count; i++) printf("%d\t%d\n", score[i], juni[i]); 

上面這個(gè)方法雖然簡單，但是反覆計(jì)算的次數(shù)是n^2，如果n值變大，那么運(yùn)算的時(shí)間就會(huì)拖長；改變juni陣列的長度為n+2，并將初始值設(shè)定為0，如下所示：

接下來走訪分?jǐn)?shù)陣列，并在分?jǐn)?shù)所對(duì)應(yīng)的排行陣列索引元素上加1，如下所示：

將排行陣列最右邊的元素設(shè)定為1，然后依序?qū)⒂疫叺脑刂导又磷筮呉粋€(gè)元素，最后排行陣列中的「分?jǐn)?shù)+1」」就是得該分?jǐn)?shù)的排行，如下所示：

這樣的方式看起來復(fù)雜，其實(shí)不過在計(jì)算某分?jǐn)?shù)之前排行的人數(shù)，假設(shè)89分之前的排行人數(shù)為x人，則89分自然就是x+1了，這也是為什么排行陣列最右邊要設(shè)定為1的原因；如果89分有y人，則88分自然就是x+y+1，整個(gè)陣列右邊元素向左加的原因正是如此。
如果分?jǐn)?shù)有負(fù)分的情況，由于C/C++或Java等程式語言無法處理負(fù)的索引，所以必須加上一個(gè)偏移值，將所有的分?jǐn)?shù)先往右偏移一個(gè)范圍即可，最后顯示的時(shí)候記得減回偏移值就可以了。

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 100 
#define MIN 0 int main(void) { int score[MAX+1] = {0}; int juni[MAX+2] = {0}; int count = 0, i; do { printf("輸入分?jǐn)?shù)，-1結(jié)束："); scanf("%d", &score[count++]); } while(score[count-1] != -1);count--; for(i = 0; i < count; i++) juni[score[i]]++; juni[MAX+1] = 1; for(i = MAX; i >= MIN; i--) juni[i] = juni[i] + juni[i+1]; printf("得分\t排行\(zhòng)n"); for(i = 0; i < count; i++) printf("%d\t%d\n", score[i], juni[score[i]+1]); return 0; 
} 

33.選擇、插入、氣泡排序

說明選擇排序（Selection sort）、插入排序（Insertion sort）與氣泡排序（Bubble sort）這三個(gè)排序方式是初學(xué)排序所必須知道的三個(gè)基本排序方式，它們由于速度不快而不實(shí)用（平均與最快的時(shí)間復(fù)雜度都是O(n2)），然而它們排序的方式確是值得觀察與探討的。
解法
選擇排序
將要排序的對(duì)象分作兩部份，一個(gè)是已排序的，一個(gè)是未排序的，從后端未排序部份選擇一個(gè)最小值，并放入前端已排序部份的最后一個(gè)，例如：

排序前：70 80 31 37 10 1 48 60 33 80

[1] 80 31 37 10 70 48 60 33 80 選出最小值1
[1 10] 31 37 80 70 48 60 33 80 選出最小值10
[1 10 31] 37 80 70 48 60 33 80 選出最小值31
[1 10 31 33] 80 70 48 60 37 80 …
[1 10 31 33 37] 70 48 60 80 80 …
[1 10 31 33 37 48] 70 60 80 80 …
[1 10 31 33 37 48 60] 70 80 80 …
[1 10 31 33 37 48 60 70] 80 80 …
[1 10 31 33 37 48 60 70 80] 80 …

插入排序
像是玩樸克一樣，我們將牌分作兩堆，每次從后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的適當(dāng)位置，例如：

排序前：92 77 67 8 6 84 55 85 43 67

[77 92] 67 8 6 84 55 85 43 67 將77插入92前
[67 77 92] 8 6 84 55 85 43 67 將67插入77前
[8 67 77 92] 6 84 55 85 43 67 將8插入67前
[6 8 67 77 92] 84 55 85 43 67 將6插入8前
[6 8 67 77 84 92] 55 85 43 67 將84插入92前
[6 8 55 67 77 84 92] 85 43 67 將55插入67前
[6 8 55 67 77 84 85 92] 43 67 …
[6 8 43 55 67 77 84 85 92] 67 …
[6 8 43 55 67 67 77 84 85 92] …

氣泡排序法
顧名思義，就是排序時(shí)，最大的元素會(huì)如同氣泡一樣移至右端，其利用比較相鄰元素的方法，將大的元素交換至右端，所以大的元素會(huì)不斷的往右移動(dòng)，直到適當(dāng)?shù)奈恢脼橹埂?/p>

基本的氣泡排序法可以利用旗標(biāo)的方式稍微減少一些比較的時(shí)間，當(dāng)尋訪完陣列后都沒有發(fā)生任何的交換動(dòng)作，表示排序已經(jīng)完成，而無需再進(jìn)行之后的回圈比較與交換動(dòng)作，例如：

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] …
27 6 9 18 49 [50 58 80 90 95] …
6 9 18 27 [49 50 58 80 90 95] …
6 9 18 [27 49 50 58 80 90 95] 由于接下來不會(huì)再發(fā)生交換動(dòng)作，排序提早結(jié)束

在上面的例子當(dāng)中，還加入了一個(gè)觀念，就是當(dāng)進(jìn)行至i與i+1時(shí)沒有交換的動(dòng)作，表示接下來的i+2至n已經(jīng)排序完畢，這也增進(jìn)了氣泡排序的效率。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void selsort(int[]);  // 選擇排序 
void insort(int[]);   // 插入排序 
void bubsort(int[]);  // 氣泡排序 int main(void) {  int number[MAX] = {0}; int i;  srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } printf("\n請(qǐng)選擇排序方式：\n"); printf("(1)選擇排序\n(2)插入排序\n(3)氣泡排序\n:"); scanf("%d", &i); switch(i) { case 1: selsort(number); break; case 2: insort(number); break; case 3: bubsort(number); break; default: printf("選項(xiàng)錯(cuò)誤(1..3)\n"); } return 0; 
} void selsort(int number[]) { int i, j, k, m; for(i = 0; i < MAX-1; i++) { m = i; for(j = i+1; j < MAX; j++) if(number[j] < number[m]) m = j; if( i != m) SWAP(number[i], number[m]) printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } } void insort(int number[]) { int i, j, k, tmp; for(j = 1; j < MAX; j++) { tmp = number[j]; i = j - 1; while(tmp < number[i]) { number[i+1] = number[i]; i--; if(i == -1) break; } number[i+1] = tmp; printf("第 %d 次排序：", j); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } 
} void bubsort(int number[]) { int i, j, k, flag = 1; for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } 
} 

34.Shell 排序法 - 改良的插入排序

說明
插入排序法由未排序的后半部前端取出一個(gè)值，插入已排序前半部的適當(dāng)位置，概念簡單但速度不快。

排序要加快的基本原則之一，是讓后一次的排序進(jìn)行時(shí)，盡量利用前一次排序后的結(jié)果，以加快排序的速度，Shell排序法即是基于此一概念來改良插入排序法。
解法
Shell排序法最初是D.L Shell于1959所提出，假設(shè)要排序的元素有n個(gè)，則每次進(jìn)行插入排序時(shí)并不是所有的元素同時(shí)進(jìn)行時(shí)，而是取一段間隔。

Shell首先將間隔設(shè)定為n/2，然后跳躍進(jìn)行插入排序，再來將間隔n/4，跳躍進(jìn)行排序動(dòng)作，再來間隔設(shè)定為n/8、n/16，直到間隔為1之后的最 后一次排序終止，由于上一次的排序動(dòng)作都會(huì)將固定間隔內(nèi)的元素排序好，所以當(dāng)間隔越來越小時(shí)，某些元素位于正確位置的機(jī)率越高，因此最后幾次的排序動(dòng)作將 可以大幅減低。

舉個(gè)例子來說，假設(shè)有一未排序的數(shù)字如右：89 12 65 97 61 81 27 2 61 98

數(shù)字的總數(shù)共有10個(gè)，所以第一次我們將間隔設(shè)定為10 / 2 = 5，此時(shí)我們對(duì)間隔為5的數(shù)字進(jìn)行排序，如下所示：

畫線連結(jié)的部份表示 要一起進(jìn)行排序的部份，再來將間隔設(shè)定為5 / 2的商，也就是2，則第二次的插入排序?qū)ο笕缦滤?#xff1a;

再來間隔設(shè)定為2 / 2 = 1，此時(shí)就是單純的插入排序了，由于大部份的元素都已大致排序過了，所以最后一次的插入排序幾乎沒作什么排序動(dòng)作了：

將間隔設(shè)定為n / 2是D.L Shell最初所提出，在教科書中使用這個(gè)間隔比較好說明，然而Shell排序法的關(guān)鍵在于間隔的選定，例如Sedgewick證明選用以下的間隔可以加 快Shell排序法的速度：

其中4*(2j)2 + 3*(2j) + 1不可超過元素總數(shù)n值，使用上式找出j后代入4*(2j)2 + 3*(2j) + 1求得第一個(gè)間隔，然后將2j除以2代入求得第二個(gè)間隔，再來依此類推。

后來還有人證明有其它的間隔選定法可以將Shell排序法的速度再加快；另外Shell排序法的概念也可以用來改良?xì)馀菖判蚍ā?br /> 實(shí)作

C 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shellsort(int[]); int main(void) { int number[MAX] = {0}; int i;  srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } shellsort(number); return 0; 
} void shellsort(int number[]) { int i, j, k, gap, t; gap = MAX / 2; while(gap > 0) { for(k = 0; k < gap; k++) { for(i = k+gap; i < MAX; i+=gap) { for(j = i - gap; j >= k; j-=gap) { if(number[j] > number[j+gap]) { SWAP(number[j], number[j+gap]); } else break; } } } printf("\ngap = %d：", gap); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n"); gap /= 2; } 
} 

35.Shaker 排序法 - 改良的氣泡排序

說明
請(qǐng)看看之前介紹過的氣泡排序法：

 for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } 
} 

事實(shí)上這個(gè)氣泡排序法已經(jīng)不是單純的氣泡排序了，它使用了旗標(biāo)與右端左移兩個(gè)方法來改進(jìn)排序的效能，而Shaker排序法使用到后面這個(gè)觀念進(jìn)一步改良?xì)馀菖判蚍ā?br /> 解法
在上面的氣泡排序法中，交換的動(dòng)作并不會(huì)一直進(jìn)行至陣列的最后一個(gè)，而是會(huì)進(jìn)行至MAX-i-1，所以排序的過程中，陣列右方排序好的元素會(huì)一直增加，使得左邊排序的次數(shù)逐漸減少，如我們的例子所示：

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] …
27 6 9 18 49 [50 58 80 90 95] …
6 9 18 27 [49 50 58 80 90 95] …
6 9 18 [27 49 50 58 80 90 95]

方括號(hào)括住的部份表示已排序完畢，Shaker排序使用了這個(gè)概念，如果讓左邊的元素也具有這樣的性質(zhì)，讓左右兩邊的元素都能先排序完成，如此未排序的元素會(huì)集中在中間，由于左右兩邊同時(shí)排序，中間未排序的部份將會(huì)很快的減少。

方法就在于氣泡排序的雙向進(jìn)行，先讓氣泡排序由左向右進(jìn)行，再來讓氣泡排序由右往左進(jìn)行，如此完成一次排序的動(dòng)作，而您必須使用left與right兩個(gè)旗標(biāo)來記錄左右兩端已排序的元素位置。

一個(gè)排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 [81]
向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]

如上所示，括號(hào)中表示左右兩邊已排序完成的部份，當(dāng)left > right時(shí)，則排序完成。

實(shí)作

C 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shakersort(int[]); int main(void) { int number[MAX] = {0}; int i;  srand(time(NULL)); 

系列好文，點(diǎn)擊鏈接即可跳轉(zhuǎn)

C語言經(jīng)典算法-5
約瑟夫問題（Josephus Problem）、排列組合、格雷碼（Gray Code)、產(chǎn)生可能的集合、m元素集合的n個(gè)元素子集

C語言經(jīng)典算法-7
排序法 - 改良的選擇排序、快速排序法（一）、快速排序法（二）、快速排序法（三）、合并排序法