C++中你必須知道的23種算法

jopen 7年前發布 | 5K 次閱讀 Dropbox Apache Cayenne

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;

}

 本文由用戶 jopen 自行上傳分享,僅供網友學習交流。所有權歸原作者,若您的權利被侵害,請聯系管理員。
 轉載本站原創文章,請注明出處,并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺,歡迎各類分享!