1.河內之塔
說明
河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的，河內為越戰時
北越的首都，即現在的胡志明市；1883年法國數學家Edouard Lucas曾提及這個故事，據說創世
紀時Benares有一座波羅教塔，是由三支鑽石棒（Pag）所支撐，開始時神在第一根棒上放置64
個由上至下依由小至大排列的金盤（Disc），並命令僧侶將所有的金盤從第一根石棒移至第三根
石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬
運完畢之時，此塔將毀損，而也就是世界末日來臨之時。
解法如果柱子標為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當有兩個盤
子，就將B當作輔助柱。如果盤數超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處
理兩個盤子，也就是：A->B、A ->C、B->C這三個步驟，而被遮住的部份，其實就是進入程式
的遞回處理。事實上，若有n個盤子，則移動完畢所需之次數為2^n - 1，所以當盤數為64時，則
所需次數為：264- 1 = 18446744073709551615為5.05390248594782e+16年，也就是約5000世紀，
如果對這數字沒什幺概念，就假設每秒鐘搬一個盤子好了，也要約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("請輸入盤數：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
2.超長整數運算（大數運算）
說明基於記憶體的有效運用，程式語言中規定了各種不同的資料型態，也因此變數所可以表
達的最大整數受到限制，例如123456789123456789這樣的整數就不可能儲存在long變數中（例
如C/C++等），我們稱這為long數，這邊翻為超長整數（避免與資料型態的長整數翻譯混淆），或
俗稱大數運算。
解法一個變數無法表示超長整數，則就使用多個變數，當然這使用陣列最為方便，假設程式
語言的最大資料型態可以儲存至65535的數好了，為了計算方便及符合使用十進位制的習慣，讓
每一個陣列元素可以儲存四個位數，也就是0到9999的數，例如：
很多人問到如何計算像50!這樣的問題，解法就是使用程式中的乘法函式，至於要算到多大，就
看需求了。
由於使用陣列來儲存數值，關於數值在運算時的加減乘除等各種運算、位數的進位或借位就必
須自行定義，加、減、乘都是由低位數開始運算，而除法則是由高位數開始運算，這邊直接提
供加減乘除運算的函式供作參考，以下的N為陣列長度。
void add(int *a, int *b, int *c) {
int i, carry = 0;
for(i = N - 1; i >= 0; i--) {
c[i] = a[i] + b[i] + carry;
if(c[i] < 10000)
carry = 0;
else { // 進位
c[i] = c[i] - 10000;
carry = 1;
}
}
}
void sub(int *a, int *b, int *c) {
int i, borrow = 0;
for(i = N - 1; i >= 0; i--) {
c[i] = a[i] - b[i] - borrow;
if(c[i] >= 0)
borrow = 0;
else { // 借位
c[i] = c[i] + 10000;
borrow = 1;
}
}
}
void mul(int *a, int b, int *c) { // b 為乘數
int i, tmp, carry = 0;
for(i = N - 1; i >=0; i--) {
tmp = a[i] * b + carry;
c[i] = tmp % 10000;
carry = tmp / 10000;
}
}
void div(int *a, int b, int *c) { // b 為除數
int i, tmp, remain = 0;
for(i = 0; i < N; i++) {
tmp = a[i] + remain;
c[i] = tmp / b;
remain = (tmp % b) * 10000;
}
}
3.最大公因數、最小公倍數、因式分解
說明最大公因數使用輾轉相除法來求，最小公倍數則由這個公式來求：
GCD*LCM=兩數乘積
解法最大公因數可以使用遞回與非遞回求解，因式分解基本上就是使用小於輸入數的數值當
作除數，去除以輸入數值，如果可以整除就視為因數，要比較快的解法就是求出小於該數的所
有質數，並試試看是不是可以整除，求質數的問題是另一個課題，請參考Eratosthenes 篩選求
質數。
實作（最大公因數、最小公倍數）
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int m, n, r;
int s;
printf("輸入兩數：");
scanf("%d %d", &m, &n);
s = m * n;
while(n != 0) {
r = m % n;
m = n;
n = r;
}
printf("GCD：%d\n", m);
printf("LCM：%d\n", s/m);
return 0;
}
實作（因式分解）
C（不用質數表）
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int i, n;
printf("請輸入整數：");
scanf("%d", &n);
printf("%d = ", n);
for(i = 2; i * i <= n;) {
if(n % i == 0) {
printf("%d * ", i);
n /= i;
}
else
i++;
}
printf("%d\n", n);
return 0;
}
C（使用質數表）
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int prime(int*); // 求質數表
void factor(int*, int); // 求factor
int main(void) {
int ptable[N+1] = {0};
int count, i, temp;
count = prime(ptable);
printf("請輸入一數：");
scanf("%d", &temp);
factor(ptable, temp);
printf("\n");
return 0;
}
int prime(int* pNum) {
int i, j;
int prime[N+1];
for(i = 2; i <= N; i++)
prime[i] = 1;
for(i = 2; i*i <= N; i++) {
if(prime[i] == 1) {
for(j = 2*i; j <= N; j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
for(i = 2, j = 0; i < N; i++) {
if(prime[i] == 1)
pNum[j++] = i;
}
return j;
}
void factor(int* table, int num) {
int i;
for(i = 0; table[i] * table[i] <= num;) {
if(num % table[i] == 0) {
printf("%d * ", table[i]);
num /= table[i];
}
else
i++;
}
printf("%d\n", num);
}
4.完美數
說明如果有一數n，其真因數（Proper factor）的總和等於n，則稱之為完美數（Perfect Number），
例如以下幾個數都是完美數：
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
程式基本上不難，第一眼看到時會想到使用回圈求出所有真因數，再進一步求因數和，不過若n
值很大，則此法會花費許多時間在回圈測試上，十分沒有效率，例如求小於10000的所有完美數。
解法如何求小於10000的所有完美數？並將程式寫的有效率？基本上有三個步驟：
求出一定數目的質數表
利用質數表求指定數的因式分解
利用因式分解求所有真因數和，並檢查是否為完美數
步驟一與步驟二在之前討論過了，問題在步驟三，如何求真因數和？方法很簡單，要先知道
將所有真因數和加上該數本身，會等於該數的兩倍，例如：
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28
等式後面可以化為：
2 * 28 = (20 + 21 + 22) * (70 + 71)
所以只要求出因式分解，就可以利用回圈求得等式後面的值，將該值除以2就是真因數和了；等
式後面第一眼看時可能想到使用等比級數公式來解，不過會使用到次方運算，可以在回圈走訪
因式分解陣列時，同時計算出等式後面的值，這在下面的實作中可以看到。
#include <stdio.h>
#include <stdlib.h>
#define N 1000
#define P 10000
int prime(int*); // 求質數表
int factor(int*, int, int*); // 求factor
int fsum(int*, int); // sum ot proper factor
int main(void) {
int ptable[N+1] = {0}; // 儲存質數表
int fact[N+1] = {0}; // 儲存因式分解結果
int count1, count2, i;
count1 = prime(ptable);
for(i = 0; i <= P; i++) {
count2 = factor(ptable, i, fact);
if(i == fsum(fact, count2))
printf("Perfect Number: %d\n", i);
}
printf("\n");
return 0;
}
int prime(int* pNum) {
int i, j;
int prime[N+1];
for(i = 2; i <= N; i++)
prime[i] = 1;
for(i = 2; i*i <= N; i++) {
if(prime[i] == 1) {
for(j = 2*i; j <= N; j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
for(i = 2, j = 0; i < N; i++) {
if(prime[i] == 1)
pNum[j++] = i;
}
return j;
}
int factor(int* table, int num, int* frecord) {
int i, k;
for(i = 0, k = 0; table[i] * table[i] <= num;) {
if(num % table[i] == 0) {
frecord[k] = table[i];
k++;
num /= table[i];
}
else
i++;
}
frecord[k] = num;
return k+1;
}
int fsum(int* farr, int c) {
int i, r, s, q;
i = 0;
r = 1;
s = 1;
q = 1;
while(i < c) {
do {
r *= farr[i];
q += r;
i++;
} while(i < c-1 && farr[i-1] == farr[i]);
s *= q;
r = 1;
q = 1;
}
return s / 2;
}
5.阿姆斯壯數
說明
在三位的整數中，例如153可以滿足13 + 53 + 33 = 153，這樣的數稱之為Armstrong數，試寫出一
程式找出所有的三位數Armstrong數。
解法
Armstrong數的尋找，其實就是在問如何將一個數字分解為個位數、十位數、百位數......，這只
要使用除法與余數運算就可以了，例如輸入input為abc，則：
a = input / 100
b = (input%100) / 10
c = input % 10
#include <stdio.h>
#include <time.h>
#include <math.h>
int main(void) {
int a, b, c;
int input;
printf("尋找Armstrong數：\n");
for(input = 100; input <= 999; input++) {
a = input / 100;
b = (input % 100) / 10;
c = input % 10;
if(a*a*a + b*b*b + c*c*c == input)
printf("%d ", input);
}
printf("\n");
return 0;
}
6.最大訪客數
說明
現將舉行一個餐會，讓訪客事先填寫到達時間與離開時間，為了掌握座位的數目，必須先估計
不同時間的最大訪客數。
解法
這個題目看似有些復雜，其實相當簡單，單就計算訪客數這個目的，同時考慮同一訪客的來訪
時間與離開時間，反而會使程式變得復雜；只要將來訪時間與離開時間分開處理就可以了，假
設訪客i 的來訪時間為x[i]，而離開時間為y[i]。
在資料輸入完畢之後，將x[i]與y[i]分別進行排序（由小到大），道理很簡單，只要先計算某時之
前總共來訪了多少訪客，然後再減去某時之前的離開訪客，就可以輕易的解出這個問題。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int); // 快速排序法
int maxguest(int[], int[], int, int);
int main(void) {
int x[MAX] = {0};
int y[MAX] = {0};
int time = 0;
int count = 0;
printf("\n輸入來訪與離開125;時間(0~24)：");
printf("\n范例：10 15");
printf("\n輸入-1 -1結束");
while(count < MAX) {
printf("\n>>");
scanf("%d %d", &x[count], &y[count]);
if(x[count] < 0)
break;
count++;
}
if(count >= MAX) {
printf("\n超出最大訪客數(%d)", MAX);
count--;
}
// 預先排序
quicksort(x, 0, count);
quicksort(y, 0, count);
while(time < 25) {
printf("\n%d 時的最大訪客數：%d",
time, maxguest(x, y, count, time));
time++;
}
printf("\n");
return 0;
}
int maxguest(int x[], int y[], int count, int time) {
int i, num = 0;
for(i = 0; i <= count; i++) {
if(time > x[i])
num++;
if(time > y[i])
num--;
}
return num;
}
int partition(int number[], int left, int right) {
int i, j, s;
s = number[right];
i = left - 1;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}
void quicksort(int number[], int left, int right) {
int q;
if(left < right) {
q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
7.中序式轉後序式（前序式）
說明平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱
之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理解，但由於電腦執行指令時是
有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以
必須將中序表示式轉換為另一種表示方法。
可以將中序表示式轉換為後序（Postfix）表示式，後序表示式又稱之為逆向波蘭表示式（Reverse
polish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)這個式子，表示為後序
表示式時是ab+cd+*。
解法用手算的方式來計算後序式相當的簡單，將運算子兩旁的運算元依先後順序全括號起來，
然後將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號
就可以完成後序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+
如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用回
圈，取出中序式的字元，遇運算元直接輸出，堆疊運算子與左括號， ISP>ICP的話直接輸出堆
疊中的運算子，遇右括號輸出堆疊中的運算子至左括號。
如果要將中序式轉為前序式，則在讀取中序式時是由後往前讀取，而左右括號的處理方式相反，
其余不變，但輸出之前必須先置入堆疊，待轉換完成後再將堆疊中的值由上往下讀出，如此就
是前序表示式。
實作
C
#include <stdio.h>
#include <stdlib.h>
int postfix(char*); // 中序轉後序
int priority(char); // 決定運算子優先順序
int main(void) {
例如(a+b)*(c+d)
這個式子，依演算
法的輸出過程如
下： OP
STACK OUTPUT
( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*
char input[80];
printf("輸入中序運算式：");
scanf("%s", input);
postfix(input);
return 0;
}
int postfix(char* infix) {
int i = 0, top = 0;
char stack[80] = {'\0'};
char op;
while(1) {
op = infix[i];
switch(op) {
case '\0':
while(top > 0) {
printf("%c", stack[top]);
top--;
}
printf("\n");
return 0;
// 運算子堆疊
case '(':
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(op)) {
printf("%c", stack[top]);
top--;
}
// 存入堆疊
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
// 遇) 輸出至(
case ')':
while(stack[top] != '(') {
printf("%c", stack[top]);
top--;
}
top--; // 不輸出(
break;
// 運算元直接輸出
default:
printf("%c", op);
break;
}
i++;
}
}
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
default:
p = 0;
break;
}
return p;
}
8.中序式轉後序式（前序式）
說明平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱
之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理解，但由於電腦執行指令時是
有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以
必須將中序表示式轉換為另一種表示方法。
可以將中序表示式轉換為後序（Postfix）表示式，後序表示式又稱之為逆向波蘭表示式（Reverse
polish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)這個式子，表示為後序
表示式時是ab+cd+*。
解法用手算的方式來計算後序式相當的簡單，將運算子兩旁的運算元依先後順序全括號起來，
然後將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號
就可以完成後序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+
如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用回
圈，取出中序式的字元，遇運算元直接輸出，堆疊運算子與左括號， ISP>ICP的話直接輸出堆
疊中的運算子，遇右括號輸出堆疊中的運算子至左括號。
如果要將中序式轉為前序式，則在讀取中序式時是由後往前讀取，而左右括號的處理方式相反，
其余不變，但輸出之前必須先置入堆疊，待轉換完成後再將堆疊中的值由上往下讀出，如此就
是前序表示式。
實作
C
#include <stdio.h>
#include <stdlib.h>
int postfix(char*); // 中序轉後序
int priority(char); // 決定運算子優先順序
int main(void) {
例如(a+b)*(c+d)
這個式子，依演算
法的輸出過程如
下： OP
STACK OUTPUT
( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*
char input[80];
printf("輸入中序運算式：");
scanf("%s", input);
postfix(input);
return 0;
}
int postfix(char* infix) {
int i = 0, top = 0;
char stack[80] = {'\0'};
char op;
while(1) {
op = infix[i];
switch(op) {
case '\0':
while(top > 0) {
printf("%c", stack[top]);
top--;
}
printf("\n");
return 0;
// 運算子堆疊
case '(':
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(op)) {
printf("%c", stack[top]);
top--;
}
// 存入堆疊
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
// 遇) 輸出至(
case ')':
while(stack[top] != '(') {
printf("%c", stack[top]);
top--;
}
top--; // 不輸出(
break;
// 運算元直接輸出
default:
printf("%c", op);
break;
}
i++;
}
}
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
default:
p = 0;
break;
}
return p;
}
9.後序式的運算
說明將中序式轉換為後序式的好處是，不用處理運算子先後順序問題，只要依序由運算式由
前往後讀取即可。
解法
#include <stdio.h>
#include <stdlib.h>
void evalPf(char*);
double cal(double, char, double);
int main(void) {
char input[80];
運算時由後序式的前方開
始讀取，遇到運算元先存入
堆疊，如果遇到運算子，則
由堆疊中取出兩個運算元進
行對應的運算，然後將結果
存回堆疊，如果運算式讀取
完畢，那麼堆疊頂的值就是
答案了， 例如我們計算
12+34+*這個運算式（也就是
(1+2)*(3+4)）：讀取
堆疊
1 1
2 1 2
+ 3 // 1+2 後存回
3 3 3
4 3 3 4
+ 3 7 // 3+4 後存回
* 21 // 3 * 7 後存回
printf("輸入後序式：");
scanf("%s", input);
evalPf(input);
return 0;
}
void evalPf(char* postfix) {
double stack[80] = {0.0};
char temp[2];
char token;
int top = 0, i = 0;
temp[1] = '\0';
while(1) {
token = postfix[i];
switch(token) {
case '\0':
printf("ans = %f\n", stack[top]);
return;
case '+': case '-': case '*': case '/':
stack[top-1] =
cal(stack[top], token, stack[top-1]);
top--;
break;
default:
if(top < sizeof(stack) / sizeof(float)) {
temp[0] = postfix[i];
top++;
stack[top] = atof(temp);
}
break;
}
i++;
}
}
double cal(double p1, char op, double p2) {
switch(op) {
case '+':
return p1 + p2;
case '-':
return p1 - p2;
case '*':
return p1 * p2;
case '/':
return p1 / p2;
}
}
10.洗撲克牌（亂數排列）
說明
洗撲克牌的原理其實與亂數排列是相同的，都是將一組數字（例如1～N）打亂重新排列，只
不過洗撲克牌多了一個花色判斷的動作而已。
解法
初學者通常會直接想到，隨機產生1～N的亂數並將之存入陣列中，後來產生的亂數存入陣列
前必須先檢查陣列中是否已有重復的數字，如果有這個數就不存入，再重新產生下一個數，運
氣不好的話，重復的次數就會很多，程式的執行速度就很慢了，這不是一個好方法。
以1～52的亂數排列為例好了，可以將陣列先依序由1到52填入，然後使用一個回圈走訪陣列，
並隨機產生1～52的亂數，將產生的亂數當作索引取出陣列值，並與目前陣列走訪到的值相交換，
如此就不用擔心亂數重復的問題了，陣列走訪完畢後，所有的數字也就重新排列了。
至於如何判斷花色？這只是除法的問題而已，取商數判斷花色，取余數判斷數字，您可以直接
看程式比較清楚。
實作
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 52
int main(void) {
int poker[N + 1];
int i, j, tmp, remain;
// 初始化陣列
for(i = 1; i <= N; i++)
poker[i] = i;
srand(time(0));
// 洗牌
for(i = 1; i <= N; i++) {
j = rand() % 52 + 1;
tmp = poker[i];
poker[i] = poker[j];
poker[j] = tmp;
}
for(i = 1; i <= N; i++) {
// 判斷花色
switch((poker[i]-1) / 13) {
case 0:
printf("桃"); break;
case 1:
printf("心"); break;
case 2:
printf("磚"); break;
case 3:
printf("梅"); break;
}
// 撲克牌數字
remain = poker[i] % 13;
switch(remain) {
case 0:
printf("K "); break;
case 12:
printf("Q "); break;
case 11:
printf("J "); break;
default:
printf("%d ", remain); break;
}
if(i % 13 == 0)
printf("\n");
}
return 0;
}
11.賭博游戲
說明一個簡單的賭博游戲，游戲規則如下：玩家擲兩個骰子，點數為1到6，如果第一次點數
和為7或11，則玩家勝，如果點數和為2、3或12，則玩家輸，如果和為其它點數，則記錄第一
次的點數和，然後繼續擲骰，直至點數和等於第一次擲出的點數和，則玩家勝，如果在這之前
擲出了點數和為7，則玩家輸。
解法規則看來有些復雜，但是其實只要使用switch配合if條件判斷來撰寫即可，小心不要弄
錯勝負順序即可。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define WON 0
#define LOST 1
#define CONTINUE 2
int rollDice() {
return (rand() % 6) + (rand() % 6) + 2;
}
int main(void) {
int firstRoll = 1;
int gameStatus = CONTINUE;
int die1, die2, sumOfDice;
int firstPoint = 0;
char c;
srand(time(0));
printf("Craps賭博游戲，按Enter鍵開始游戲****");
while(1) {
getchar();
if(firstRoll) {
sumOfDice = rollDice();
printf("\n玩家擲出點數和：%d\n", sumOfDice);
switch(sumOfDice) {
case 7: case 11:
gameStatus = WON; break;
case 2: case 3: case 12:
gameStatus = LOST; break;
default:
firstRoll = 0;
gameStatus = CONTINUE;
firstPoint = sumOfDice;
break;
}
}
else {
sumOfDice = rollDice();
printf("\n玩家擲出點數和：%d\n", sumOfDice);
if(sumOfDice == firstPoint)
gameStatus = WON;
else if(sumOfDice == 7)
gameStatus = LOST;
}
if(gameStatus == CONTINUE)
puts("未分勝負，再擲一次****\n");
else {
if(gameStatus == WON)
puts("玩家勝");
else
puts("玩家輸");
printf("再玩一次？");
scanf("%c", &c);
if(c == 'n') {
puts("游戲結束");
break;
}
firstRoll = 1;
}
}
return 0;
}
12.約瑟夫問題（Josephus
Problem）
說明據說著名猶太歷史學家Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39 個猶
太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人到，於是決定了
一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，
然後再由下一個重新報數，直到所有人都自殺身亡為止。
然而Josephus 和他的朋友並不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排
在第16個與第31個位置，於是逃過了這場死亡游戲。
解法約瑟夫問題可用代數分析來求解，將這個問題擴大好了，假設現在您與m個朋友不幸參
與了這個游戲，您要如何保護您與您的朋友？只要畫兩個圓圈就可以讓自己與朋友免於死亡游
戲，這兩個圓圈內圈是排列順序，而外圈是自殺順序，如下圖所示：
使用程式來求解的話，只要將陣列當作環狀來處理就可以了，在陣列中由計數1開始，每找到三
個無資料區就填入一個計數，直而計數達41為止，然後將陣列由索引1開始列出，就可以得知每
個位置的自殺順序，這就是約瑟夫排列，41個人而報數3的約琴夫排列如下所示：
14 36 1 38 15 2 25 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個位置，而倒數第二個自殺的要排在第16個位置，之前的
人都死光了，所以他們也就不知道約琴夫與他的朋友並沒有遵守游戲規則了。
#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; // 環狀處理
if(man[pos] == 0)
i++;
if(i == M) { // 報數為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; }
13.選擇、插入、氣泡排序
說明選擇排序（Selection sort）、插入排序（Insertion sort）與氣泡排序（Bubble sort）這三個
排序方式是初學排序所必須知道的三個基本排序方式，它們由於速度不快而不實用（平均與最
快的時間復雜度都是O(n2)），然而它們排序的方式確是值得觀察與探討的。
解法
選擇排序
將要排序的對象分作兩部份，一個是已排序的，一個是未排序的，從後端未排序部份選擇一個
最小值，並放入前端已排序部份的最後一個，例如：
排序前：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 ......
插入排序
像是玩樸克一樣，我們將牌分作兩堆，每次從後面一堆的牌抽出最前端的牌，然後插入前面一
堆牌的適當位置，例如：
排序前：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] ......
氣泡排序法
顧名思義，就是排序時，最大的元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方法，
將大的元素交換至右端，所以大的元素會不斷的往右移動，直到適當的位置為止。
基本的氣泡排序法可以利用旗標的方式稍微減少一些比較的時間，當尋訪完陣列後都沒有發生
任何的交換動作，表示排序已經完成，而無需再進行之後的回圈比較與交換動作，例如：
排序前：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] 由於接下來不會再發生交換動作，排序提早結束
在上面的例子當中，還加入了一個觀念，就是當進行至i與i+1時沒有交換的動作，表示接下來的
i+2至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請選擇排序方式：\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("選項錯誤(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");
}
}
14.排序法-
改良的插入排序
說明
插入排序法由未排序的後半部前端取出一個值，插入已排序前半部的適當位置，概念簡單但速
度不快。
排序要加快的基本原則之一，是讓後一次的排序進行時，盡量利用前一次排序後的結果，以加
快排序的速度，Shell排序法即是基於此一概念來改良插入排序法。
解法
Shell排序法最初是D.L Shell於1959所提出，假設要排序的元素有n個，則每次進行插入排序時
並不是所有的元素同時進行時，而是取一段間隔。
Shell首先將間隔設定為n/2，然後跳躍進行插入排序，再來將間隔n/4，跳躍進行排序動作，再來
間隔設定為n/8、n/16，直到間隔為1之後的最後一次排序終止，由於上一次的排序動作都會將
固定間隔內的元素排序好，所以當間隔越來越小時，某些元素位於正確位置的機率越高，因此
最後幾次的排序動作將可以大幅減低。
舉個例子來說，假設有一未排序的數字如右：89 12 65 97 61 81 27 2 61 98
數字的總數共有10個，所以第一次我們將間隔設定為10 / 2 = 5，此時我們對間隔為5的數字進行
排序，如下所示：
畫線連結的部份表示要一起進行排序的部份，再來將間隔設定為5 / 2的商，也就是2，則第二
次的插入排序對象如下所示：
再來間隔設定為2 / 2 = 1，此時就是單純的插入排序了，由於大部份的元素都已大致排序過了，
所以最後一次的插入排序幾乎沒作什麼排序動作了：
將間隔設定為n / 2是D.L Shell最初所提出，在教科書中使用這個間隔比較好說明，然而Shell排
序法的關鍵在於間隔的選定，例如Sedgewick證明選用以下的間隔可以加快Shell排序法的速度：
其中4*(2j)2 + 3*(2j) + 1不可超過元素總數n值，使用上式找出j後代入4*(2j)2 + 3*(2j) + 1求得第一
個間隔，然後將2j除以2代入求得第二個間隔，再來依此類推。
後來還有人證明有其它的間隔選定法可以將Shell排序法的速度再加快；另外Shell排序法的概念
也可以用來改良氣泡排序法。
實作
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;
}
}
15.排序法-
改良的氣泡排序
說明
請看看之前介紹過的氣泡排序法：
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;
}
}
}
事實上這個氣泡排序法已經不是單純的氣泡排序了，它使用了旗標與右端左移兩個方法來改進
排序的效能，而Shaker排序法使用到後面這個觀念進一步改良氣泡排序法。
解法
在上面的氣泡排序法中，交換的動作並不會一直進行至陣列的最後一個，而是會進行至MAX-i-
1，所以排序的過程中，陣列右方排序好的元素會一直增加，使得左邊排序的次數逐漸減少，如
我們的例子所示：
排序前：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]
方括號括住的部份表示已排序完畢，Shaker排序使用了這個概念，如果讓左邊的元素也具有這
樣的性質，讓左右兩邊的元素都能先排序完成，如此未排序的元素會集中在中間，由於左右兩
邊同時排序，中間未排序的部份將會很快的減少。
方法就在於氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行，
如此完成一次排序的動作，而您必須使用left與right兩個旗標來記錄左右兩端已排序的元素位
置。
一個排序的例子如下所示：
排序前：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]
如上所示，括號中表示左右兩邊已排序完成的部份，當left > right時，則排序完成。
實作
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));
16.排序法-
改良的選擇排序
說明
選擇排序法的概念簡單，每次從未排序部份選一最小值，插入已排序部份的後端，其時間主要
花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加快，選擇排序法的速率也
就可以加快，Heap排序法讓搜尋的路徑由樹根至最後一個樹葉，而不是整個未排序部份，因而
稱之為改良的選擇排序法。
解法
Heap排序法使用Heap Tree（堆積樹），樹是一種資料結構，而堆積樹是一個二元樹，也就是每
一個父節點最多只有兩個子節點（關於樹的詳細定義還請見資料結構書籍），堆積樹的父節點
若小於子節點，則稱之為最小堆積（Min Heap），父節點若大於子節點，則稱之為最大堆積（Max
Heap），而同一層的子節點則無需理會其大小關系，例如下面就是一個堆積樹：
可以使用一維陣列來儲存堆積樹的所有元素與其順序，為了計算方便，使用的起始索引是1而不
是0，索引1是樹根位置，如果左子節點儲存在陣列中的索引為s，則其父節點的索引為s/2，而右
子節點為s+1，就如上圖所示，將上圖的堆積樹轉換為一維陣列之後如下所示：
首先必須知道如何建立堆積樹，加至堆積樹的元素會先放置在最後一個樹葉節點位置，然後檢
查父節點是否小於子節點（最小堆積），將小的元素不斷與父節點交換，直到滿足堆積樹的條件
為止，例如在上圖的堆積加入一個元素12，則堆積樹的調整方式如下所示：
建立好堆積樹之後，樹根一定是所有元素的最小值，您的目的就是：
將最小值取出
然後調整樹為堆積樹
不斷重復以上的步驟，就可以達到排序的效果，最小值的取出方式是將樹根與最後一個樹葉節
點交換，然後切下樹葉節點，重新調整樹為堆積樹，如下所示：
調整完畢後，樹根節點又是最小值了，於是我們可以重覆這個步驟，再取出最小值，並調整樹
為堆積樹，如下所示：
如此重覆步驟之後，由於使用一維陣列來儲存堆積樹，每一次將樹葉與樹根交換的動作就是將
最小值放至後端的陣列，所以最後陣列就是變為已排序的狀態。
其實堆積在調整的過程中，就是一個選擇的行為，每次將最小值選至樹根，而選擇的路徑並不
是所有的元素，而是由樹根至樹葉的路徑，因而可以加快選擇的過程， 所以Heap排序法才會被
稱之為改良的選擇排序法。
#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 createheap(int[]);
void heapsort(int[]);
int main(void) {
int number[MAX+1] = {-1};
int i, num;
srand(time(NULL));
printf("排序前：");
for(i = 1; i <= MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
printf("\n建立堆積樹：");
createheap(number);
for(i = 1; i <= MAX; i++)
printf("%d ", number[i]);
printf("\n");
heapsort(number);
printf("\n");
return 0;
}
void createheap(int number[]) {
int i, s, p;
int heap[MAX+1] = {-1};
for(i = 1; i <= MAX; i++) {
heap[i] = number[i];
s = i;
p = i / 2;
while(s >= 2 && heap[p] > heap[s]) {
SWAP(heap[p], heap[s]);
s = p;
p = s / 2;
}
}
for(i = 1; i <= MAX; i++)
number[i] = heap[i];
}
void heapsort(int number[]) {
int i, m, p, s;
m = MAX;
while(m > 1) {
SWAP(number[1], number[m]);
m--;
p = 1;
s = 2 * p;
while(s <= m) {
if(s < m && number[s+1] < number[s])
s++;
if(number[p] <= number[s])
break;
SWAP(number[p], number[s]);
p = s;
s = 2 * p;
}
printf("\n排序中：");
for(i = MAX; i > 0; i--)
printf("%d ", number[i]);
}
}
17.快速排序法（一）
說明快速排序法（quick sort）是目前所公認最快的排序方法之一（視解題的對象而定），雖然
快速排序法在最差狀況下可以達O(n2)，但是在多數的情況下，快速排序法的效率表現是相當不
錯的。
快速排序法的基本精神是在數列中找出適當的軸心，然後將數列一分為二，分別對左邊與右邊
數列進行排序，而影響快速排序法效率的正是軸心的選擇。
這邊所介紹的第一個快速排序法版本，是在多數的教科書上所提及的版本，因為它最容易理解，也最符合軸心分割與左右進行排序的概念，適合對初學者進行講解。
解法這邊所介紹的快速演算如下：將最左邊的數設定為軸，並記錄其值為s
廻圈處理：
令索引i 從數列左方往右方找，直到找到大於s 的數
令索引j 從數列左右方往左方找，直到找到小於s 的數
如果i >= j，則離開回圈
如果i < j，則交換索引i與j兩處的值
將左側的軸與j 進行交換
對軸左邊進行遞回
對軸右邊進行遞回
透過以下演算法，則軸左邊的值都會小於s，軸右邊的值都會大於s，如此再對軸左右兩邊進行
遞回，就可以對完成排序的目的，例如下面的實例，*表示要交換的數，[]表示軸：
[41] 24 76* 11 45 64 21 69 19 36*
[41] 24 36 11 45* 64 21 69 19* 76
[41] 24 36 11 19 64* 21* 69 45 76
[41] 24 36 11 19 21 64 69 45 76
21 24 36 11 19 [41] 64 69 45 76
在上面的例子中，41左邊的值都比它小，而右邊的值都比它大，如此左右再進行遞回至排序完
成。
#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 quicksort(int[], int, int);
int main(void) {
int number[MAX] = {0};
int i, num;
srand(time(NULL));
printf("排序前：");
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
quicksort(number, 0, MAX-1);
printf("\n排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
return 0;
}
void quicksort(int number[], int left, int right) {
int i, j, s;
if(left < right) {
s = number[left];
i = left;
j = right + 1;
while(1) {
// 向右找
while(i + 1 < number.length && number[++i] < s) ;
// 向左找
while(j -1 > -1 && number[--j] > s) ;
if(i >= j)
break;
SWAP(number[i], number[j]);
}
number[left] = number[j];
number[j] = s;
quicksort(number, left, j-1); // 對左邊進行遞回
quicksort(number, j+1, right); // 對右邊進行遞回
}
}
18.快速排序法（二）
說明在快速排序法（一）中，每次將最左邊的元素設為軸，而之前曾經說過，快速排序法的
加速在於軸的選擇，在這個例子中，只將軸設定為中間的元素，依這個元素作基准進行比較，
這可以增加快速排序法的效率。
解法在這個例子中，取中間的元素s作比較，同樣的先得右找比s大的索引i，然後找比s小的
索引j，只要兩邊的索引還沒有交會，就交換i 與j 的元素值，這次不用再進行軸的交換了，
因為在尋找交換的過程中，軸位置的元素也會參與交換的動作，例如：
41 24 76 11 45 64 21 69 19 36
首先left為0，right為9，(left+right)/2 = 4（取整數的商），所以軸為索引4的位置，比較的元素是
45，您往右找比45大的，往左找比45小的進行交換：
41 24 76* 11 [45] 64 21 69 19 *36
41 24 36 11 45* 64 21 69 19* 76
41 24 36 11 19 64* 21* 69 45 76
[41 24 36 11 19 21] [64 69 45 76]
完成以上之後，再初別對左邊括號與右邊括號的部份進行遞回，如此就可以完成排序的目的。
#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 quicksort(int[], int, int);
int main(void) {
int number[MAX] = {0};
int i, num;
srand(time(NULL));
printf("排序前：");
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
quicksort(number, 0, MAX-1);
printf("\n排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
return 0;
}
void quicksort(int number[], int left, int right) {
int i, j, s;
if(left < right) {
s = number[(left+right)/2];
i = left - 1;
j = right + 1;
while(1) {
while(number[++i] < s) ; // 向右找
while(number[--j] > s) ; // 向左找
if(i >= j)
break;
SWAP(number[i], number[j]);
}
quicksort(number, left, i-1); // 對左邊進行遞回
quicksort(number, j+1, right); // 對右邊進行遞回
}
}
19.快速排序法（三）
說明
之前說過軸的選擇是快速排序法的效率關鍵之一，在這邊的快速排序法的軸選擇方式更加快了
快速排序法的效率，它是來自演算法名書Introduction to Algorithms 之中。
解法
先說明這個快速排序法的概念，它以最右邊的值s作比較的標准，將整個數列分為三個部份，
一個是小於s的部份，一個是大於s的部份，一個是未處理的部份，如下所示：
在排序的過程中，i 與j 都會不斷的往右進行比較與交換，最後數列會變為以下的狀態：
然後將s的值置於中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示：
然後將s的值置於中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示：
整個演算的過程，直接摘錄書中的虛擬碼來作說明：
QUICKSORT(A, p, r)
if p < r
then q <- PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
end QUICKSORT
PARTITION(A, p, r)
x <- A[r]
i <- p-1
for j <- p to r-1
do if A[j] <= x
then i <- i+1
exchange A[i]<->A[j]
exchange A[i+1]<->A[r]
return i+1
end PARTITION
一個實際例子的演算如下所示：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int);
int main(void) {
int number[MAX] = {0};
int i, num;
srand(time(NULL));
printf("排序前：");
for(i = 0; i < MAX; i++) {
number[i] = rand() % 100;
printf("%d ", number[i]);
}
quicksort(number, 0, MAX-1);
printf("\n排序後：");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
return 0;
}
int partition(int number[], int left, int right) {
int i, j, s;
s = number[right];
i = left - 1;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}
void quicksort(int number[], int left, int right) {
int q;
if(left < right) {
q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
20.多維矩陣轉一維矩陣
說明
有的時候，為了運算方便或資料儲存的空間問題，使用一維陣列會比二維或多維陣列來得方便，
例如上三角矩陣、下三角矩陣或對角矩陣，使用一維陣列會比使用二維陣列來得節省空間。
解法
以二維陣列轉一維陣列為例，索引值由0開始，在由二維陣列轉一維陣列時，我們有兩種方式：
「以列（Row）為主」或「以行（Column）為主」。由於C/C++、Java等的記憶體配置方式都是
以列為主，所以您可能會比較熟悉前者（Fortran的記憶體配置方式是以行為主）。
以列為主的二維陣列要轉為一維陣列時，是將二維陣列由上往下一列一列讀入一維陣列，此時
索引的對應公式如下所示，其中row與column是二維陣列索引，loc表示對應的一維陣列索引：
loc = column + row*行數
以行為主的二維陣列要轉為一維陣列時，是將二維陣列由左往右一行一行讀入一維陣列，此時
索引的對應公式如下所示：
loc = row + column*列數
公式的推導您畫圖看看就知道了，如果是三維陣列，則公式如下所示，其中i（個數u1）、j（個
數u2）、k（個數u3）分別表示三維陣列的三個索引：
以列為主：loc = i*u2*u3 + j*u3 + k
以行為主：loc = k*u1*u2 + j*u1 + i
更高維度的可以自行依此類推，但通常更高維度的建議使用其它資料結構（例如物件包裝）會
比較具體，也不易搞錯。
在C/C++中若使用到指標時，會遇到指標運算與記憶體空間位址的處理問題，此時也是用到這
邊的公式，不過必須在每一個項上乘上資料型態的記憶體大小。
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int arr1[3][4] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}};
int arr2[12] = {0};
int row, column, i;
printf("原二維資料：\n");
for(row = 0; row < 3; row++) {
for(column = 0; column < 4; column++) {
printf("%4d", arr1[row][column]);
}
printf("\n");
}
printf("\n以列為主：");
for(row = 0; row < 3; row++) {
for(column = 0; column < 4; column++) {
i = column + row * 4;
arr2[i] = arr1[row][column];
}
}
for(i = 0; i < 12; i++)
printf("%d ", arr2[i]);
printf("\n以行為主：");
for(row = 0; row < 3; row++) {
for(column = 0; column < 4; column++) {
i = row + column * 3;
arr2[i] = arr1[row][column];
}
}
for(i = 0; i < 12; i++)
printf("%d ", arr2[i]);
printf("\n");
return 0;
}
21.上三角、下三角、對稱矩陣
說明
上三角矩陣是矩陣在對角線以下的元素均為0，即Aij = 0，i > j，例如：
1 2 3 4 5
0 6 7 8 9
0 0 10 11 12
0 0 0 13 14
0 0 0 0 15
下三角矩陣是矩陣在對角線以上的元素均為0，即Aij = 0，i < j，例如：
1 0 0 0 0
2 6 0 0 0
3 7 10 0 0
4 8 11 13 0
5 9 12 14 15
對稱矩陣是矩陣元素對稱於對角線，例如：
1 2 3 4 5
2 6 7 8 9
3 7 10 11 12
4 8 11 13 14
5 9 12 14 15
上三角或下三角矩陣也有大部份的元素不儲存值（為0），我們可以將它們使用一維陣列來儲存
以節省儲存空間，而對稱矩陣因為對稱於對角線，所以可以視為上三角或下三角矩陣來儲存。
解法
假設矩陣為nxn，為了計算方便，我們讓陣列索引由1開始，上三角矩陣化為一維陣列，若以
列為主，其公式為：loc = n*(i-1) - i*(i-1)/2 + j
化為以行為主，其公式為：loc = j*(j-1)/2 + i
下三角矩陣化為一維陣列，若以列為主，其公式為：loc = i*(i-1)/2 + j
若以行為主，其公式為：loc = n*(j-1) - j*(j-1)/2 + i
公式的導證其實是由等差級數公式得到，您可以自行繪圖並看看就可以導證出來，對於C/C++
或Java等索引由0開始的語言來說，只要將i與j各加1，求得loc之後減1即可套用以上的公式。
#include <stdio.h>
#include <stdlib.h>
#define N 5
int main(void) {
int arr1[N][N] = {
{1, 2, 3, 4, 5},
{0, 6, 7, 8, 9},
{0, 0, 10, 11, 12},
{0, 0, 0, 13, 14},
{0, 0, 0, 0, 15}};
int arr2[N*(1+N)/2] = {0};
int i, j, loc = 0;
printf("原二維資料：\n");
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
printf("%4d", arr1[i][j]);
}
printf("\n");
}
printf("\n以列為主：");
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
if(arr1[i][j] != 0)
arr2[loc++] = arr1[i][j];
}
}
for(i = 0; i < N*(1+N)/2; i++)
printf("%d ", arr2[i]);
printf("\n輸入索引(i, j)：");
scanf("%d, %d", &i, &j);
loc = N*i - i*(i+1)/2 + j;
printf("(%d, %d) = %d", i, j, arr2[loc]);
printf("\n");
return 0;
}
22.m元素集合的n個元素子集
說明
假設有個集合擁有m個元素，任意的從集合中取出n個元素，則這n個元素所形成的可能子集有
那些？
解法
假設有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}
這些子集已經使用字典順序排列，如此才可以觀察出一些規則：
如果最右一個元素小於m，則如同碼表一樣的不斷加1
如果右邊一位已至最大值，則加1的位置往左移
每次加1的位置往左移後，必須重新調整右邊的元素為遞減順序
所以關鍵點就在於哪一個位置必須進行加1的動作，到底是最右一個位置要加1？還是其它的位
置？
在實際撰寫程式時，可以使用一個變數positon來記錄加1的位置，position的初值設定為n-1，
因為我們要使用陣列，而最右邊的索引值為最大的n-1，在position位置的值若小於m就不斷加
1，如果大於m了，position就減1，也就是往左移一個位置；由於位置左移後，右邊的元素會經
過調整，所以我們必須檢查最右邊的元素是否小於m，如果是，則position調整回n-1，如果不
是，則positon維持不變。
實作
C
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int main(void) {
int set[MAX];
int m, n, position;
int i;
printf("輸入集合個數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]++;
// 調整右邊元素
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;
}
23.數字拆解
說明
這個題目來自於數字拆解，我將之改為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
共七種
依此類推，請問一個指定數字NUM的拆解方法個數有多少個？
解法
我們以上例中最後一個數字5的拆解為例，假設f( n )為數字n的可拆解方式個數，而f(x, y)為使
用y以下的數字來拆解x的方法個數，則觀察：
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的數字來拆解1沒有意義，所以f(1, 4) =f(1, 1)，而同樣的，f(0, 5)會等於f(0, 0)，所以：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)
依照以上的說明，使用動態程式規畫（Dynamic programming）來進行求解，其中f(4,1)其實就
是f(5-1, min(5-1,1))，f(x, y)就等於f(n-y, min(n-x, y))，其中n為要拆解的數字，而min()表示取兩
者中較小的數。
使用一個二維陣列表格table[x][y]來表示f(x, y)，剛開始時，將每列的索引0與索引1元素值設定
為1，因為任何數以0以下的數拆解必只有1種，而任何數以1以下的數拆解也必只有1種：
for(i = 0; i < NUM +1; i++){
table[i][0] = 1; // 任何數以0以下的數拆解必只有1種
table[i][1] = 1; // 任何數以1以下的數拆解必只有1種
}
接下來就開始一個一個進行拆解了，如果數字為NUM，則我們的陣列維度大小必須為NUM x
(NUM/2+1)，以數字10為例，其維度為10 x 6我們的表格將會如下所示：
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
實作
C
#include <stdio.h>
#include <stdlib.h>
#define NUM 10 // 要拆解的數字
#define DEBUG 0
int main(void) {
int table[NUM][NUM/2+1] = {0}; // 動態規畫表格
int count = 0;
int result = 0;
int i, j, k;
printf("數字拆解\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; // 任何數以0以下的數拆解必只有1種
table[i][1] = 1; // 任何數以1以下的數拆解必只有1種
}
// 動態規劃
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;
}
}
// 計算並顯示結果
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除錯資訊\n");
for(i = 0; i < NUM; i++) {
for(j = 0; j < NUM/2+1; j++)
printf("%2d", table[i][j]);
printf("\n");
}
}
return 0;
}
摘自 jia0511的專欄
