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

第二种解法（使用质数表）

#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的所有完美数？并将程式写的有效率？基本上有三个步骤：

1. 求出一定数目的质数表
2. 利用质数表求指定数的因式分解
3. 利用因式分解求所有真因数和，并检查是否为完美数

步骤一与步骤二在之前讨论过了，问题在步骤三，如何求真因数和？方法很简单，要先知道将所有真因数和加上该数本身，会等于该数的两倍，例如：
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）表示式，后序表示式又称之为逆向波兰表示式（Reversepolish notation），它是由波兰的数学家卢卡谢维奇提出，例如(a+b)(c+d)这个式子，表示为后序表示式时是ab+cd+。

==解法==
用手算的方式来计算后序式相当的简单，将运算子两旁的运算元依先后顺序全括号起来，然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始），最后去掉所有的左括号就可以完成后序表示式，例如：
a+bd+c/d => ((a+(bd))+(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）表示式，后序表示式又称之为逆向波兰表示式（Reversepolish notation），它是由波兰的数学家卢卡谢维奇提出，例如(a+b)(c+d)这个式子，表示为后序表示式时是ab+cd+。

==解法==
用手算的方式来计算后序式相当的简单，将运算子两旁的运算元依先后顺序全括号起来，然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始），最后去掉所有的左括号就可以完成后序表示式，例如：
a+bd+c/d => ((a+(bd))+(c/d)) -> bd*+cd/+a如果要用程式来进行中序转后序，则必须使用堆叠，演算法很简单，直接叙述的话就是使用回
圈，取出中序式的字元，遇运算元直接输出，堆叠运算子与左括号， ISP>ICP的话直接输出堆叠中的运算子，遇右括号输出堆叠中的运算子至左括号。如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就是前序表示式。
例如(a+b)*(c+d)这个式子，依演算法的输出过程如下：
OPSTACK OUTPUT
( ( -a ( a+ (+ ab (+ ab) - ab+ab+( ( ab+c ( ab+c+ *(+ ab+cd *(+ ab+cd)ab+cd+ ab+cd

#include <stdio.h>
#include <stdlib.h>
int postfix(char*); // 中序转后序
int priority(char); // 决定运算子优先顺序
int main(void) {

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.后序式的运算

说明

将中序式转换为后序式的好处是，不用处理运算子先后顺序问题，只要依序由运算式由前往后读取即可。

==解法==
运算时由后序式的前方开始读取，遇到运算元先存入堆叠，如果遇到运算子，则由堆叠中取出两个运算元进行对应的运算，然后将结果存回堆叠，如果运算式读取完毕，那么堆叠顶的值就是答案了， 例如我们计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 后存回

#include <stdio.h>
#include <stdlib.h>
void evalPf(char*);
double cal(double, char, double);
int main(void) {
char input[80];
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.约瑟夫问题（JosephusProblem）

说明

据说着名犹太历史学家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
廻圈处理：

1. 令索引i 从数列左方往右方找，直到找到大于s 的数
2. 令索引j 从数列左右方往左方找，直到找到小于s 的数
3. 如果i >= j，则离开回圈
4. 如果i < j，则交换索引i与j两处的值
5. 将左侧的轴与j 进行交换
6. 对轴左边进行递回
7. 对轴右边进行递回

透过以下演算法，则轴左边的值都会小于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); // 对右边进行递回
}
}