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

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

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

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

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

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

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

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

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

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

26.約瑟夫問題（Josephus Problem）

說明據(jù)說著名猶太歷史學(xué)家 Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人 開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。

然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
解法約瑟夫問題可用代數(shù)分析來求解，將這個問題擴大好了，假設(shè)現(xiàn)在您與m個朋友不幸參與了這個游戲，您要如何保護您與您的朋友？只要畫兩個圓圈就可以讓自己與朋友免于死亡游戲，這兩個圓圈內(nèi)圈是排列順序，而外圈是自殺順序，如下圖所示：

使用程式來求解的話，只要將陣列當(dāng)作環(huán)狀來處理就可以了，在陣列中由計數(shù)1開始，每找到三個無資料區(qū)就填入一個計數(shù)，直而計數(shù)達41為止，然后將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列，41個人而報數(shù)3的約琴夫排列如下所示：

14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23

由上可知，最后一個自殺的是在第31個位置，而倒數(shù)第二個自殺的要排在第16個位置，之前的人都死光了，所以他們也就不知道約琴夫與他的朋友并沒有遵守游戲規(guī)則了。

#include <stdio.h> 
#include <stdlib.h> 
#define N 41 
#define M 3 int main(void) { int man[N] = {0}; int count = 1; int i = 0, pos = -1; int alive = 0; while(count <= N) { do { pos = (pos+1) % N;  // 環(huán)狀處理 if(man[pos] == 0) i++; if(i == M) {  // 報數(shù)為3了 i = 0; break; } } while(1); man[pos] = count; count++; } printf("\n約琴夫排列："); for(i = 0; i < N; i++) printf("%d ", man[i]); printf("\n\n您想要救多少人？"); scanf("%d", &alive); printf("\nL表示這%d人要放的位置：\n", alive); for(i = 0; i < N; i++) { if(man[i] > alive) 	printf("D"); else 	printf("L"); if((i+1) % 5 == 0) 	printf("  "); } printf("\n"); return 0; } 

27.排列組合

說明將一組數(shù)字、字母或符號進行排列，以得到不同的組合順序，例如1 2 3這三個數(shù)的排列組合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。
解法可以使用遞回將問題切割為較小的單元進行排列組合，例如1 2 3 4的排列可以分為1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]進行排列，這邊利用旋轉(zhuǎn)法，先將旋轉(zhuǎn)間隔設(shè)為0，將最右邊的數(shù)字旋轉(zhuǎn)至最左邊，并逐步增加旋轉(zhuǎn)的間隔，例如：

1 2 3 4 -> 旋轉(zhuǎn)1 -> 繼續(xù)將右邊2 3 4進行遞回處理
2 1 3 4 -> 旋轉(zhuǎn)1 2 變?yōu)?2 1-> 繼續(xù)將右邊1 3 4進行遞回處理
3 1 2 4 -> 旋轉(zhuǎn)1 2 3變?yōu)?3 1 2 -> 繼續(xù)將右邊1 2 4進行遞回處理
4 1 2 3 -> 旋轉(zhuǎn)1 2 3 4變?yōu)? 1 2 3 -> 繼續(xù)將右邊1 2 3進行遞回處理

#include <stdio.h> 
#include <stdlib.h> 
#define N 4 void perm(int*, int); int main(void) { int num[N+1], i; for(i = 1; i <= N; i++) num[i] = i; perm(num, 1); return 0; 
} void perm(int* num, int i) { int j, k, tmp; if(i < N) { for(j = i; j <= N; j++) { tmp = num[j]; // 旋轉(zhuǎn)該區(qū)段最右邊數(shù)字至最左邊 for(k = j; k > i; k--) num[k] = num[k-1]; num[i] = tmp; perm(num, i+1); // 還原 for(k = i; k < j; k++) num[k] = num[k+1]; num[j] = tmp; } } else {  // 顯示此次排列 for(j = 1; j <= N; j++) printf("%d ", num[j]); printf("\n"); } 
}  

28.格雷碼（Gray Code）

說明
Gray Code是一個數(shù)列集合，每個數(shù)使用二進位來表示，假設(shè)使用n位元來表示每個數(shù)好了，任兩個數(shù)之間只有一個位元值不同，例如以下為3位元的Gray Code：

000 001 011 010 110 111 101 100

由定義可以知道，Gray Code的順序并不是唯一的，例如將上面的數(shù)列反過來寫，也是一組Gray Code：

100 101 111 110 010 011 001 000

Gray Code是由貝爾實驗室的Frank Gray在1940年代提出的，用來在使用PCM（Pusle Code Modulation）方法傳送訊號時避免出錯，并于1953年三月十七日取得美國專利。
解法
由于Gray Code相鄰兩數(shù)之間只改變一個位元，所以可觀 察Gray Code從1變0或從0變1時的位置，假設(shè)有4位元的Gray Code如下：

0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

觀察奇數(shù)項的變化時，我們發(fā)現(xiàn)無論它是第幾個Gray Code，永遠只改變最右邊的位元，如果是1就改為0，如果是0就改為1。

觀察偶數(shù)項的變化時，我們發(fā)現(xiàn)所改變的位元，是由右邊算來第一個1的左邊位元。

以上兩個變化規(guī)則是固定的，無論位元數(shù)為何；所以只要判斷位元的位置是奇數(shù)還是偶數(shù)，就可以決定要改變哪一個位元的值，為了程式撰寫方便，將陣列索引 0當(dāng)作最右邊的值，而在列印結(jié)果時，是由索引數(shù)字大的開始反向列印。

將2位元的Gray Code當(dāng)作平面座標(biāo)來看，可以構(gòu)成一個四邊形，您可以發(fā)現(xiàn)從任一頂點出發(fā)，繞四邊形周長繞一圈，所經(jīng)過的頂點座標(biāo)就是一組Gray Code，所以您可以得到四組Gray Code。

同樣的將3位元的Gray Code當(dāng)作平面座標(biāo)來看的話，可以構(gòu)成一個正立方體，如果您可以從任一頂點出發(fā)，將所有的邊長走過，并不重復(fù)經(jīng)過頂點的話，所經(jīng)過的頂點座標(biāo)順序之組合也就是一組Gray Code。

#include <stdio.h> 
#include <stdlib.h> #define MAXBIT 20 
#define TRUE 1 
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0') 
#define NEXT(x) x = (1 - (x)) int main(void) { char digit[MAXBIT]; int i, bits, odd; printf("輸入位元數(shù)："); scanf("%d", &bits); for(i = 0; i < bits; i++) { digit[i] = '0'; printf("0"); } printf("\n"); odd = TRUE; while(1) { if(odd) CHANGE_BIT(digit[0]); else { // 計算第一個1的位置 for(i = 0; i < bits && digit[i] == '0'; i++) ; if(i == bits - 1) // 最后一個Gray Code break; CHANGE_BIT(digit[i+1]); } for(i = bits - 1; i >= 0; i--) printf("%c", digit[i]); printf("\n"); NEXT(odd); } return 0; 
} 

29.產(chǎn)生可能的集合

說明
給定一組數(shù)字或符號，產(chǎn)生所有可能的集合（包括空集合），例如給定1 2 3，則可能的集合為：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
解法
如果不考慮字典順序，則有個簡單的方法可以產(chǎn)生所有的集合，思考二進位數(shù)字加法，并注意1出現(xiàn)的位置，如果每個位置都對應(yīng)一個數(shù)字，則由1所對應(yīng)的數(shù)字所產(chǎn)生的就是一個集合，例如：

Input	Set
000	{}
001	{3}
010	{2}
011	{2,3}
100	{1}
101	{1,3}
110	{1,2}
111	{1,2,3}

了解這個方法之后，剩下的就是如何產(chǎn)生二進位數(shù)？有許多方法可以使用，您可以使用unsigned型別加上&位元運算來產(chǎn)生，這邊則是使用陣列搜 尋，首先陣列內(nèi)容全為0，找第一個1，在還沒找到之前將走訪過的內(nèi)容變?yōu)?，而第一個找到的0則變?yōu)?1，如此重復(fù)直到所有的陣列元素都變?yōu)?為止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111

如果要產(chǎn)生字典順序，例如若有4個元素，則：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =>
{1,2,4} =>
{1,3} => {1,3,4} =>
{1,4} =>
{2} => {2,3} => {2,3,4} =>
{2,4} =>
{3} => {3,4} =>
{4}

簡單的說，如果有n個元素要產(chǎn)生可能的集合，當(dāng)依序產(chǎn)生集合時，如果最后一個元素是n，而倒數(shù)第二個元素是m的話，例如：
{a b c d e n}

則下一個集合就是{a b c d e+1}，再依序加入后續(xù)的元素。

例如有四個元素，而當(dāng)產(chǎn)生{1 2 3 4}集合時，則下一個集合就是{1 2 3+1}，也就是{1 2 4}，由于最后一個元素還是4，所以下一個集合就是{1 2+1}，也就是{1 3}，接下來再加入后續(xù)元素4，也就是{1 3 4}，由于又遇到元素4，所以下一個集合是{1 3+1}，也就是{1 4}。
實作

C（無字典順序） 
#include <stdio.h> 
#include <stdlib.h> #define MAXSIZE 20 int main(void) { char digit[MAXSIZE]; int i, j; int n; printf("輸入集合個數(shù)："); scanf("%d", &n); for(i = 0; i < n; i++) digit[i] = '0'; printf("\n{}"); // 空集合 while(1) { // 找第一個0，并將找到前所經(jīng)過的元素變?yōu)? for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++); if(i == n)  // 找不到0 break; else          // 將第一個找到的0變?yōu)? digit[i] = '1'; // 找第一個1，并記錄對應(yīng)位置 for(i = 0; i < n && digit[i] == '0'; i++); printf("\n{%d", i+1); for(j = i + 1; j < n; j++) if(digit[j] == '1') printf(",%d", j + 1); printf("}"); } printf("\n"); return 0; 
} 

C（字典順序） 
#include <stdio.h> 
#include <stdlib.h> #define MAXSIZE 20 int main(void) { int set[MAXSIZE]; int i, n, position = 0; printf("輸入集合個數(shù)："); scanf("%d", &n); printf("\n{}"); set[position] = 1; while(1) { printf("\n{%d", set[0]);  // 印第一個數(shù) for(i = 1; i <= position; i++) printf(",%d", set[i]); printf("}"); if(set[position] < n) {  // 遞增集合個數(shù) set[position+1] = set[position] + 1; position++; } else if(position != 0) {  // 如果不是第一個位置 position--;       // 倒退 set[position]++;  // 下一個集合尾數(shù) } else  // 已倒退至第一個位置 break; } printf("\n"); return 0; 
} 

30.m元素集合的n個元素子集

說明
假設(shè)有個集合擁有m個元素，任意的從集合中取出n個元素，則這n個元素所形成的可能子集有那些？
解法
假設(shè)有5個元素的集點，取出3個元素的可能子集如下：
{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5}

這些子集已經(jīng)使用字典順序排列，如此才可以觀察出一些規(guī)則：
如果最右一個元素小于m，則如同碼表一樣的不斷加1
如果右邊一位已至最大值，則加1的位置往左移
每次加1的位置往左移后，必須重新調(diào)整右邊的元素為遞減順序

所以關(guān)鍵點就在于哪一個位置必須進行加1的動作，到底是最右一個位置要加1？還是其它的位置？

在實際撰寫程式時，可以使用一個變數(shù)positon來記錄加1的位置，position的初值設(shè)定為n-1，因為我們要使用陣列，而最右邊的索引值為最大 的n-1，在position位置的值若小于m就不斷加1，如果大于m了，position就減1，也就是往左移一個位置；由于位置左移后，右邊的元素會 經(jīng)過調(diào)整，所以我們必須檢查最右邊的元素是否小于m，如果是，則position調(diào)整回n-1，如果不是，則positon維持不變。
實作

#include <stdio.h> 
#include <stdlib.h> #define MAX 20 int main(void) { int set[MAX]; int m, n, position; int i; printf("輸入集合個數(shù) m："); scanf("%d", &m); printf("輸入取出元素 n："); scanf("%d", &n); for(i = 0; i < n; i++) set[i] = i + 1; // 顯示第一個集合 for(i = 0; i < n; i++) printf("%d ", set[i]); putchar('\n'); position = n - 1; while(1) { if(set[n-1] == m) position--; else position = n - 1; set[position]++; // 調(diào)整右邊元素 for(i = position + 1; i < n; i++) set[i] = set[i-1] + 1; for(i = 0; i < n; i++) printf("%d ", set[i]); putchar('\n'); if(set[0] >= m - n + 1) break; } return 0; 
} 

系列好文，點擊鏈接即可跳轉(zhuǎn)
上一篇：
C語言經(jīng)典算法-4
最大訪客數(shù)、中序式轉(zhuǎn)后序式（前序式）、后序式的運算、洗撲克牌（亂數(shù)排列）、Craps賭博游戲
下一篇：
C語言經(jīng)典算法-6
數(shù)字拆解、得分排行，選擇、插入、氣泡排序、Shell 排序法 - 改良的插入排序、Shaker 排序法 - 改良的氣泡排序