C++中你必须知道的23种算法

12年前

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的话直接输出堆

叠中的运算子，遇右括号输出堆叠中的运算子至左括号。

如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，

其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就

是前序表示式。

实作

#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的话直接输出堆

叠中的运算子，遇右括号输出堆叠中的运算子至左括号。

如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，

其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就

是前序表示式。

实作

#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的乱数，将产生的乱数当作索引取出阵列值，并与目前阵列走访到的值相交换，

如此就不用担心乱数重复的问题了，阵列走访完毕后，所有的数字也就重新排列了。

至于如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以直接

看程式比较清楚。

实作

#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排序法的概念

也可以用来改良气泡排序法。

实作

#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时，则排序完成。

实作

#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的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：

整个演算的过程，直接摘录书中的虚拟码来作说明：

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维持不变。

实作

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

实作

#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;

}

C++中你必须知道的23种算法

博客分类

目录

推荐阅读

C++中你必须知道的23种算法

程序员必须知道的编程格言

主题：Java的内部类——你知道多少？

你要知道的开源世界---读开源软件之道