1.河内之塔
2.Algorithm Gossip: 费式数列.
3.巴斯卡三角形
4.Algorithm Gossip: 三色棋
5.Algorithm Gossip: 老鼠走迷官（一）
6.Algorithm Gossip: 老鼠走迷官（二）
7.Algorithm Gossip: 骑士走棋盘
8.Algorithm Gossip: 八皇后
9.Algorithm Gossip: 八枚银币.
10.Algorithm Gossip: 生命游戏.
11.Algorithm Gossip: 字串核对
12.Algorithm Gossip: 双色、三色河内塔
13.Algorithm Gossip: 背包问题（Knapsack Problem
14.Algorithm Gossip: 蒙地卡罗法求 PI
15.Algorithm Gossip: Eratosthenes 筛选求质数
16.Algorithm Gossip: 超长整数运算（大数运算）.
17.Algorithm Gossip: 长 PI.
18.Algorithm Gossip: 最大公因数、最小公倍数、因式分解
19.Algorithm Gossip: 完美数...
20.Algorithm Gossip: 阿姆斯壮数.
21.Algorithm Gossip: 最大访客数....
22.Algorithm Gossip: 中序式转后序式（前序式）...
23.Algorithm Gossip: 后序式的运算.
24.Algorithm Gossip: 洗扑克牌（乱数排列）
25.Algorithm Gossip: Craps 赌博游戏.
26.Algorithm Gossip: 约瑟夫问题（Josephus Problem）
27.Algorithm Gossip: 排列组合.
28.Algorithm Gossip: 格雷码（Gray Code
29.Algorithm Gossip: 产生可能的集合
30.Algorithm Gossip: m 元素集合的 n 个元素子集
31.Algorithm Gossip: 数字拆解
32.Algorithm Gossip: 得分排行
33.Algorithm Gossip: 选择、插入、气泡排序
34.Algorithm Gossip: Shell 排序法 - 改良的插入排序
35.Algorithm Gossip: Shaker 排序法 - 改良的气泡排序
36.排序法 - 改良的选择
37.Algorithm Gossip:速排序法（一）
38.Algorithm Gossip: 快速排序法（二）
39.Algorithm Gossip: 快速排序法（三）
40.Algorithm Gossip: 合并排序法
41.Algorithm Gossip: 基数排序法.
42.Algorithm Gossip: 循序搜寻法（使用卫兵）
43.Algorithm Gossip: 二分搜寻法（搜寻原则的代表）
44.Algorithm Gossip: 插补搜寻法.
45.Algorithm Gossip: 费氏搜寻法.
46.Algorithm Gossip: 稀疏矩阵
47.Algorithm Gossip: 多维矩阵转一维矩阵
48.Algorithm Gossip: 上三角、下三角、对称矩阵
49.Algorithm Gossip: 奇数魔方阵
50.Algorithm Gossip: 4N 魔方阵.
51.Algorithm Gossip: 2(2N+1)
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时，则
64
如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约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-1=18446744073709551615为5.05390248594782e+16年，也就是约5000世纪
2.Algorithm Gossip: 费式数列
说明
Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免
子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三
只免子，三个月后有五只免子（小免子投入生产）......。
如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生
产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例
如以下： 1、1 、2、3、5、8、13、21、34、55、89......
解法
依说明，我们可以将费氏数列定义为以下：
fn = fn-1 + fn-2
fn = n
if n > 1
if n = 0, 1
#include <stdio.h>
#include <stdlib.h>
#define N 20
int main(void) {
int Fib[N] = {0};
int i;
Fib[0] = 0;
Fib[1] = 1;
for(i = 2; i < N; i++)
Fib[i] = Fib[i-1] + Fib[i-2];
for(i = 0; i < N; i++)
printf("%d ", Fib[i]);
printf("\n");
return 0;
}
3. 巴斯卡三角形
#include <stdio.h>
#define N 12
long combi(int n, int r){
int i;
long p = 1;
for(i = 1; i <= r; i++)
p = p * (n-i+1) / i;
return p;
}
void paint() {
int n, r, t;
for(n = 0; n <= N; n++) {
for(r = 0; r <= n; r++) {
int i;/* 排版设定开始 */
if(r == 0) {
for(i = 0; i <= (N-n); i++)
}else {
printf("
");
printf("
");
} /* 排版设定结束 */
printf("%3d", combi(n, r));
}
printf("\n");
}
}
4.Algorithm Gossip: 三色棋
说明
三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰
人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子。
解法
在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问
题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到
白色留在中间，遇到红色往后移，如下所示：
只是要让移动次数最少的话，就要有些技巧：
如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。
如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。
如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。
注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始
时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗
子就都是红色了，此时就可以结束移动，如下所示：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BLUE 'b'
#define WHITE 'w'
#define RED 'r'
#define SWAP(x, y) { char temp; \
temp = color[x]; \
color[x] = color[y]; \
color[y] = temp; }
int main() {
char color[] = {'r', 'w', 'b', 'w', 'w',
'b', 'r', 'b', 'w', 'r', '\0'};
int wFlag = 0;
int bFlag = 0;
int rFlag = strlen(color) - 1;
int i;
for(i = 0; i < strlen(color); i++)
printf("%c ", color[i]);
printf("\n");
while(wFlag <= rFlag) {
if(color[wFlag] == WHITE)
wFlag++;
else if(color[wFlag] == BLUE) {
SWAP(bFlag, wFlag);
bFlag++; wFlag++;
}
else {
while(wFlag < rFlag && color[rFlag] == RED)
rFlag--;
SWAP(rFlag, wFlag);
rFlag--;
}
}
for(i = 0; i < strlen(color); i++)
printf("%c ", color[i]);
printf("\n");
return 0;
}
5.Algorithm Gossip: 老鼠走迷官（一）
说明老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表
示老鼠的行走路径，试以程式求出由入口至出口的路径。
解法老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前
进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是
递回的基本题，请直接看程式应就可以理解。
#include <stdio.h>
#include <stdlib.h>
int visit(int, int);
int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1; // 入口
int endI = 5, endJ = 5; // 出口
int success = 0;
int main(void) {
int i, j;
printf("显示迷宫：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf("
");
printf("\n");
}
if(visit(startI, startJ) == 0)
printf("\n没有找到出口！\n");
else {
printf("\n显示路径：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++) {
if(maze[i][j] == 2)
printf("█");
else if(maze[i][j] == 1)
printf("◇");
else
printf("
");
}
printf("\n");
}
}
return 0;
}
int visit(int i, int j) {
maze[i][j] = 1;
if(i == endI && j == endJ)
success = 1;
if(success != 1 && maze[i][j+1] == 0) visit(i, j+1);
if(success != 1 && maze[i+1][j] == 0) visit(i+1, j);
if(success != 1 && maze[i][j-1] == 0) visit(i, j-1);
if(success != 1 && maze[i-1][j] == 0) visit(i-1, j);
if(success != 1)
maze[i][j] = 0;
return success;
}
6.Algorithm Gossip: 老鼠走迷官（二）
说明由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路径呢？
解法求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退
回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作
一点修改就可以了。
#include <stdio.h>
#include <stdlib.h>
void visit(int, int);
int maze[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 2, 2}};
int startI = 1, startJ = 1; // 入口
int endI = 7, endJ = 7; // 出口
int main(void) {
int i, j;
printf("显示迷宫：\n");
for(i = 0; i < 7; i++) {
for(j = 0; j < 7; j++)
if(maze[i][j] == 2)
printf("█");
else
printf("
");
printf("\n");
}
visit(startI, startJ);
return 0;
}
void visit(int i, int j) {
int m, n;
maze[i][j] = 1;
if(i == endI && j == endJ) {
printf("\n显示路径：\n");
for(m = 0; m < 9; m++) {
for(n = 0; n < 9; n++)
if(maze[m][n] == 2)
printf("█");
else if(maze[m][n] == 1)
printf("◇");
else
printf("
");
printf("\n");
}
}
if(maze[i][j+1] == 0) visit(i, j+1);
if(maze[i+1][j] == 0) visit(i+1, j);
if(maze[i][j-1] == 0) visit(i, j-1);
if(maze[i-1][j] == 0) visit(i-1, j);
maze[i][j] = 0;
}
7.Algorithm Gossip: 骑士走棋盘
说明骑士旅游（Knight tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出
已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位
置？
解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，
一个聪明的解法由J.C. Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路
就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步。」，使用这个
方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。
#include <stdio.h>
int board[8][8] = {0};
int main(void) {
int startx, starty;
int i, j;
printf("输入起始点：");
scanf("%d %d", &startx, &starty);
if(travel(startx, starty)) {
printf("游历完成！\n");
}
else {
printf("游历失败！\n");
}
for(i = 0; i < 8; i++) {
for(j = 0; j < 8; j++) {
printf("%2d ", board[i][j]);
}
putchar('\n');
}
return 0;
}
int travel(int x, int y) {
// 对应骑士可走的八个方向
int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1};
// 测试下一步的出路
int nexti[8] = {0};
int nextj[8] = {0};
// 记录出路的个数
int exists[8] = {0};
int i, j, k, m, l;
int tmpi, tmpj;
int count, min, tmp;
i = x;
j = y;
board[i][j] = 1;
for(m = 2; m <= 64; m++) {
for(l = 0; l < 8; l++)
exists[l] = 0;
l = 0;
// 试探八个方向
for(k = 0; k < 8; k++) {
tmpi = i + ktmove1[k];
tmpj = j + ktmove2[k];
// 如果是边界了，不可走
if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)
continue;
// 如果这个方向可走，记录下来
if(board[tmpi][tmpj] == 0) {
nexti[l] = tmpi;
nextj[l] = tmpj;
// 可走的方向加一个
l++;
}
}
count = l;
// 如果可走的方向为0个，返回
if(count == 0) {
return 0;
}
else if(count == 1) {
// 只有一个可走的方向
// 所以直接是最少出路的方向
min = 0;
}
else {
// 找出下一个位置的出路数
for(l = 0; l < count; l++) {
for(k = 0; k < 8; k++) {
tmpi = nexti[l] + ktmove1[k];
tmpj = nextj[l] + ktmove2[k];
if(tmpi < 0 || tmpj < 0 ||
tmpi > 7 || tmpj > 7) {
continue;
}
if(board[tmpi][tmpj] == 0)
exists[l]++;
}
}
tmp = exists[0];
min = 0;
// 从可走的方向中寻找最少出路的方向
for(l = 1; l < count; l++) {
if(exists[l] < tmp) {
tmp = exists[l];
min = l;
}
}
}
// 走最少出路的方向
i = nexti[min];
j = nextj[min];
board[i][j] = m;
}
return 1;
}
8.Algorithm Gossip: 八皇后
说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八
个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用这个问
题来讲解程式设计之技巧。
解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，
不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方
法称为分支修剪。
#include <stdio.h>
#include <stdlib.h>
#define N 8
int column[N+1]; // 同栏是否有皇后，1表示有
int rup[2*N+1]; // 右上至左下是否有皇后
int lup[2*N+1]; // 左上至右下是否有皇后
int queen[N+1] = {0};
int num; // 解答编号
void backtrack(int); // 递回求解
int main(void) {
int i;
num = 0;
for(i = 1; i <= N; i++)
column[i] = 1;
for(i = 1; i <= 2*N; i++)
rup[i] = lup[i] = 1;
backtrack(1);
return 0;
}
void showAnswer() {
int x, y;
printf("\n解答 %d\n", ++num);
for(y = 1; y <= N; y++) {
for(x = 1; x <= N; x++) {
if(queen[y] == x) {
printf(" Q");
}
else {
printf(" .");
}
}
printf("\n");
}
}
void backtrack(int i) {
int j;
if(i > N) {
showAnswer();
}
else {
for(j = 1; j <= N; j++) {
if(column[j] == 1 &&
rup[i+j] == 1 && lup[i-j+N] == 1) {
queen[i] = j;
// 设定为占用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;
}
}
}
}
9.Algorithm Gossip: 八枚银币
说明现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或
较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。
解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回
圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。一个简单
的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个
较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻
而 g是真币，则h假币的重量比真币轻。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void compare(int[], int, int, int);
void eightcoins(int[]);
int main(void) {
int coins[8] = {0};
int i;
srand(time(NULL));
for(i = 0; i < 8; i++)
coins[i] = 10;
printf("\n输入假币重量(比10大或小)：");
scanf("%d", &i);
coins[rand() % 8] = i;
eightcoins(coins);
printf("\n\n列出所有钱币重量：");
for(i = 0; i < 8; i++)
printf("%d ", coins[i]);
printf("\n");
return 0;
}
void compare(int coins[], int i, int j, int k) {
if(coins[i] > coins[k])
printf("\n假币 %d 较重", i+1);
else
printf("\n假币 %d 较轻", j+1);
}
void eightcoins(int coins[]) {
if(coins[0]+coins[1]+coins[2] ==
coins[3]+coins[4]+coins[5]) {
if(coins[6] > coins[7])
compare(coins, 6, 7, 0);
else
compare(coins, 7, 6, 0);
}
else if(coins[0]+coins[1]+coins[2] >
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(coins, 2, 5, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(coins, 0, 4, 1);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(coins, 1, 3, 0);
}
else if(coins[0]+coins[1]+coins[2] <
coins[3]+coins[4]+coins[5]) {
if(coins[0]+coins[3] == coins[1]+coins[4])
compare(coins, 5, 2, 0);
else if(coins[0]+coins[3] > coins[1]+coins[4])
compare(coins, 3, 1, 0);
if(coins[0]+coins[3] < coins[1]+coins[4])
compare(coins, 4, 0, 1);
}
}
10.Algorithm Gossip: 生命游戏
说明生命游戏（game of life）为1970年由英国数学家J. H. Conway所提出，某一细胞的邻居包
括上、下、左、右、左上、左下、右上与右下相邻之细胞，游戏规则如下：
孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状态将死亡。
拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡。
稳定：如果细胞的邻居为二个或三个，则下一次状态为稳定存活。
复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一细胞。
解法生命游戏的规则可简化为以下，并使用CASE比对即可使用程式实作：
邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡。
邻居个数为2时，则该细胞下次状态为复活。
邻居个数为3时，则该细胞下次状态为稳定。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXROW 10
#define MAXCOL 25
#define DEAD 0
#define ALIVE 1
int map[MAXROW][MAXCOL], newmap[MAXROW][MAXCOL];
void init();
int neighbors(int, int);
void outputMap();
void copyMap();
int main() {
int row, col;
char ans;
init();
while(1) {
outputMap();
for(row = 0; row < MAXROW; row++) {
for(col = 0; col < MAXCOL; col++) {
switch (neighbors(row, col)) {
case 0:
case 1:
case 4:
case 5:
case 6:
case 7:
case 8:
newmap[row][col] = DEAD;
break;
case 2:
newmap[row][col] = map[row][col];
break;
case 3:
newmap[row][col] = ALIVE;
break;
}
}
}
copyMap();
printf("\nContinue next Generation ? ");
getchar();
ans = toupper(getchar());
}
if(ans != 'Y')
break;
return 0;
}
void init() {
int row, col;
for(row = 0; row < MAXROW; row++)
for(col = 0; col < MAXCOL; col++)
map[row][col] = DEAD;
puts("Game of life Program");
puts("Enter x, y where x, y is living cell");
printf("0 <= x <= %d, 0 <= y <= %d\n",
MAXROW-1, MAXCOL-1);
puts("Terminate with x, y = -1, -1");
while(1) {
scanf("%d %d", &row, &col);
if(0 <= row && row < MAXROW &&
0 <= col && col < MAXCOL)
map[row][col] = ALIVE;
else if(row == -1 || col == -1)
break;
else
printf("(x, y) exceeds map ranage!");
}
}
int neighbors(int row, int col) {
int count = 0, c, r;
for(r = row-1; r <= row+1; r++)
for(c = col-1; c <= col+1; c++) {
if(r < 0 || r >= MAXROW || c < 0 || c >= MAXCOL)
continue;
if(map[r][c] == ALIVE)
count++;
}
if(map[row][col] == ALIVE)
count--;
return count;
}
void outputMap() {
int row, col;
printf("\n\n%20cGame of life cell status\n");
for(row = 0; row < MAXROW; row++) {
printf("\n%20c", ' ');
for(col = 0; col < MAXCOL; col++)
if(map[row][col] == ALIVE)
putchar('#');
else
putchar('-');
}
}
void copyMap() {
int row, col;
for(row = 0; row < MAXROW; row++)
for(col = 0; col < MAXCOL; col++)
map[row][col] = newmap[row][col];
}
11.Algorithm Gossip: 字串核对
说明今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字
串搜寻本身仍是个值得探讨的课题，在这边以 Boyer- Moore法来说明如何进行字串说明，这个
方法快且原理简洁易懂。
解法字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的
字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个
方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字
串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然
后比对字串中p-n+1至p的值是否与关键字相同。
如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，
如此就不会跳过可能的位置，例如texture这个关键字，t的前进值应该取后面的3而不是取前面的
7。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void table(char*); // 建立前进表
int search(int, char*, char*); // 搜寻关键字
void substring(char*, char*, int, int); // 取出子字串
int skip[256];
int main(void) {
char str_input[80];
char str_key[80];
char tmp[80] = {'\0'};
int m, n, p;
printf("请输入字串：");
gets(str_input);
printf("请输入搜寻关键字：");
gets(str_key);
m = strlen(str_input); // 计算字串长度
n = strlen(str_key);
table(str_key);
p = search(n-1, str_input, str_key);
while(p != -1) {
substring(str_input, tmp, p, m);
printf("%s\n", tmp);
p = search(p+n+1, str_input, str_key);
}
printf("\n");
return 0;
}
void table(char *key) {
int k, n;
n = strlen(key);
for(k = 0; k <= 255; k++)
skip[k] = n;
for(k = 0; k < n - 1; k++)
skip[key[k]] = n - k - 1;
}
int search(int p, char* input, char* key) {
int i, m, n;
char tmp[80] = {'\0'};
m = strlen(input);
n = strlen(key);
while(p < m) {
substring(input, tmp, p-n+1, p);
if(!strcmp(tmp, key)) // 比较两字串是否相同
return p-n+1;
p += skip[input[p]];
}
return -1;
}
void substring(char *text, char* tmp, int s, int e) {
int i, j;
for(i = s, j = 0; i <= e; i++, j++)
mp[j] = text[i];
tmp[j] = '\0';
}
12.Algorithm Gossip: 双色、三色河内塔
说明双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来，双色河内塔的目的
是将下图左上的圆环位置经移动成为右下的圆环位置：
而三色河内塔则是将下图左上的圆环经移动成为右上的圆环：
解法无论是双色河内塔或是三色河内塔，其解法观念与之前介绍过的河内塔是类似的，同样
也是使用递回来解，不过这次递回解法的目的不同，我们先来看只有两个盘的情况，这很简单，
只要将第一柱的黄色移动至第二柱，而接下来第一柱的蓝色移动至第三柱。
再来是四个盘的情况，首先必须用递回完成下图左上至右下的移动：
接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱的上面两个盘子就
可以了。那么六个盘的情况呢？一样！首先必须用递回完成下图左上至右下的移动：
接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的四个盘子就
可以了，这又与之前只有四盘的情况相同，接下来您就知道该如何进行解题了，无论是八个盘、
十个盘以上等，都是用这个观念来解题。
那么三色河内塔呢？一样，直接来看九个盘的情况，首先必须完成下图的移动结果：
接下来最底两层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的三个盘子
就可以了。
双色河内塔 C 实作
#include <stdio.h>
void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}
void hanoi2colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
for(i = disks / 2; i > 1; i--) {
hanoi(i-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(i-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
}
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
}
int main() {
int n;
printf("请输入盘数：");
scanf("%d", &n);
hanoi2colors(n);
return 0;
}
三色河内塔 C 实作
#include <stdio.h>
void hanoi(int disks, char source, char temp, char target) {
if (disks == 1) {
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", source, target);
} else {
hanoi(disks-1, source, target, temp);
hanoi(1, source, temp, target);
hanoi(disks-1, temp, source, target);
}
}
void hanoi3colors(int disks) {
char source = 'A';
char temp = 'B';
char target = 'C';
int i;
if(disks == 3) {
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, source);
printf("move disk from %c to %c\n", target, temp);;
}
else {
hanoi(disks/3-1, source, temp, target);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
printf("move disk from %c to %c\n", source, temp);
hanoi(disks/3-1, target, temp, source);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
printf("move disk from %c to %c\n", temp, target);
hanoi(disks/3-1, source, target, temp);
printf("move disk from %c to %c\n", target, source);
printf("move disk from %c to %c\n", target, source);
hanoi(disks/3-1, temp, source, target);
printf("move disk from %c to %c\n", source, temp);
for (i = disks / 3 - 1; i > 0; i--) {
if (i>1) {
hanoi(i-1, target, source, temp);
}
printf("move disk from %c to %c\n",target, source);
printf("move disk from %c to %c\n",target, source);
if (i>1) {
hanoi(i-1, temp, source, target);
}
printf("move disk from %c to %c\n", source, temp);
}
}
}
int main() {
int n;
printf("请输入盘数：");
scanf("%d", &n);
hanoi3colors(n);
return 0;
}
13.Algorithm Gossip: 背包问题（Knapsack Problem）
说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物
品，假设是水果好了，水果的编号、单价与重量如下所示：
0 李子 4KG NT$4500
1 苹果 5KG NT$5700
2 橘子 2KG NT$2250
3 草莓 1KG NT$1100
4 甜瓜 6KG NT$6700
解法 背包问题是关于最佳化的问题，要解最佳化问题可以使用「动态规划」（Dynamic
programming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加
入至集合中，最后得到的就是最佳解。
由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入
的 水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看
背包负重7公斤时的最佳解，最后一个放入的是2号，也就 是橘子，现在背包剩下负重量5公斤
（7-2），所以看负重 5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公
斤（5-5）， 无 法 再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。
实作
C
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 8
#define N 5
#define MIN 1
struct body {
char name[20];
int size;
int price;
};
// 重量限制
// 物品种类
// 最小重量
typedef struct body object;
int main(void) {
int item[LIMIT+1] = {0};
int value[LIMIT+1] = {0};
int newvalue, i, s, p;
object a[] = {{"李子", 4, 4500},
{"苹果", 5, 5700},
{"橘子", 2, 2250},
{"草莓", 1, 1100},
{"甜瓜", 6, 6700}};
for(i = 0; i < N; i++) {
for(s = a[i].size; s <= LIMIT; s++) {
p = s - a[i].size;
newvalue = value[p] + a[i].price;
if(newvalue > value[s]) {// 找到阶段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
printf("物品\t价格\n");
for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) {
printf("%s\t%d\n",
a[item[i]].name, a[item[i]].price);
}
printf("合计\t%d\n", value[LIMIT]);
return 0;
}
Java
class Fruit {
private String name;
private int size;
private int price;
public Fruit(String name, int size, int price) {
this.name = name;
this.size = size;
this.price = price;
}
public String getName() {
return name;
}
public int getPrice() {
return price;
}
public int getSize() {
return size;
}
}
public class Knapsack {
public static void main(String[] args) {
final int MAX = 8;
final int MIN = 1;
int[] item = new int[MAX+1];
int[] value = new int[MAX+1];
Fruit fruits[] = {
new Fruit("李子", 4, 4500),
new Fruit("苹果", 5, 5700),
new Fruit("橘子", 2, 2250),
new Fruit("草莓", 1, 1100),
new Fruit("甜瓜", 6, 6700)};
for(int i = 0; i < fruits.length; i++) {
for(int s = fruits[i].getSize(); s <= MAX; s++) {
int p = s - fruits[i].getSize();
int newvalue = value[p] +
fruits[i].getPrice();
if(newvalue > value[s]) {// 找到阶段最佳解
value[s] = newvalue;
item[s] = i;
}
}
}
System.out.println("物品\t价格");
for(int i = MAX;
i >= MIN;
i = i - fruits[item[i]].getSize()) {
System.out.println(fruits[item[i]].getName()+
"\t" + fruits[item[i]].getPrice());
}
System.out.println("合计\t" + value[MAX]);
}
}
14.Algorithm Gossip: 蒙地卡罗法求 PI
说明蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境，以赌博闻名。蒙地卡罗的
基本原理为以乱数配合面积公式来进行解题，这种以机率来解题的方式带有赌博的意味，虽然
在精确度上有所疑虑，但其解题的思考方向却是个值得学习的方式。
解法蒙地卡罗的解法适用于与面积有关的题目，例如求PI值或椭圆面积，这边介绍如何求PI
值；假设有一个圆半径为1，所以四分之一圆面积就为PI，而包括此四分之一圆的正方形面积就
为1，如下图所示：
如果随意的在正方形中投射飞标（点）好了，则这些飞标（点）有些会落于四分之一圆内，假
设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最
后的公式。
至于如何判断所产生的点落于圆内，很简单，令乱数产生X与Y两个数值，如果X^2+Y^2等于1
就是落在圆内。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 50000
int main(void) {
int i, sum = 0;
double x, y;
srand(time(NULL));
for(i = 1; i < N; i++) {
x = (double) rand() / RAND_MAX;
y = (double) rand() / RAND_MAX;
if((x * x + y * y) < 1)
sum++;
}
printf("PI = %f\n", (double) 4 * sum / N);
return 0;
}
15.Algorithm Gossip: Eratosthenes 筛选求质数
说明除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的
求出质数则一直是程式设计人员与数学家努力的课题，在这边介绍一个着名的 Eratosthenes求质
数方法。
解法首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以
整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？
首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设
A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整
除N。不过在程式中使用开根号会精确度的问题，所以可以使用 i*i <= N进行检查，且执行更快 。
再来假设有一个筛子存放1～N，例如：
2
3 4 5
6 7
8
9 10
11 12
13 14 15
16 17
18 19
20 21 ........ N
先将2的倍数筛去：
2
3 5 7
9 11 13 15
17 19 21 ........ N
再将3的倍数筛去：
2
3 5 7
11 13
17 19 ........ N
再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的
数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）。
检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍
数，使得程式中的if的检查动作可以减少。
实作
C
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int main(void) {
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; i < N; i++) {
if(prime[i] == 1) {
printf("%4d ", i);
if(i % 16 == 0)
printf("\n");
}
}
printf("\n");
return 0;
}
16.Algorithm Gossip: 超长整数运算（大数运算）
说明基于记忆体的有效运用，程式语言中规定了各种不同的资料型态，也因此变数所可以表
达的最大整数受到限制，例如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;
}
}
17.Algorithm Gossip: 长 PI
说明圆周率后的小数位数是无止境的，如何使用电脑来计算这无止境的小数是一些数学家与
程式设计师所感兴趣的，在这边介绍一个公式配合 大数运算，可以计算指定位数的圆周率。
解法首先介绍J.Marchin的圆周率公式：
3 5 7
3 5 7
可以将这个公式整理为：
3 3 5 5
也就是说第n项，若为奇数则为正数，为偶数则为负数，而项数表示方式为：
[16/5
2*n-1
2*n-1
2*n-1
2*n-1 2*n-1
2*n-1
来的
大，具有决定性，所以表示至少必须计算至第n项：
[16/5
2*n-1
] / (2*n-1) = 10
-L
将上面的等式取log并经过化简，我们可以求得：
n = L / (2log5) = L / 1.39794
所以若要求精确度至小数后L位数，则只要求至公式的第n项，其中n等于：
n = [L/1.39794] + 1
在上式中[]为高斯符号，也就是取至整数（不大于L/1.39794的整数）；为了计简方便，可以在程
式中使用下面这个公式来计简第n项：
2 2
这个公式的演算法配合大数运算函式的演算法为： div(w, 25, w);
div(v, 239, v);
div(v, 239, v);
sub(w, v, q);
div(q, 2*k-1, q)
至于大数运算的演算法，请参考之前的文章，必须注意的是在输出时，由于是输出阵列中的整
数值，如果阵列中整数位数不满四位，则必须补上0，在C语言中只要 使用格式指定字%04d，
使得不足位数部份自动补上0再输出，至于Java的部份，使用 NumberFormat来作格式化。
#include <stdio.h>
#define L 1000
#define N L/4+1
// L 为位数，N是array长度
void add(int*, int*, int*);
void sub(int*, int*, int*);
void div(int*, int, int*);
int main(void) {
int s[N+3] = {0};
int w[N+3] = {0};
int v[N+3] = {0};
int q[N+3] = {0};
int n = (int)(L/1.39793 + 1);
int k;
w[0] = 16*5;
v[0] = 4*239;
for(k = 1; k <= n; k++) {
// 套用公式
div(w, 25, w);
div(v, 239, v);
div(v, 239, v);
sub(w, v, q);
div(q, 2*k-1, q);
if(k%2) // 奇数项
add(s, q, s);
else
// 偶数项
sub(s, q, s);
}
printf("%d.", s[0]);
for(k = 1; k < N; k++)
printf("%04d", s[k]);
printf("\n");
return 0;
}
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 div(int *a, int b, int *c) { // b 为除数
int i, tmp, remain = 0;
for(i = 0; i <= N+1; i++) {
tmp = a[i] + remain;
c[i] = tmp / b;
remain = (tmp % b) * 10000;
}
}
18.Algorithm Gossip: 最大公因数、最小公倍数、因式分解
说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：
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);
}
19.Algorithm Gossip: 完美数
说明如果有一数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
等式后面可以化为：
0 1 2 0 1
所以只要求出因式分解，就可以利用回圈求得等式后面的值，将该值除以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;
}
20.Algorithm Gossip: 阿姆斯壮数
说明
3 3 3
程式找出所有的三位数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;
}
21.Algorithm Gossip: 最大访客数
说明
现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计
不同时间的最大访客数。
解法
这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访
时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假
设访客 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);
}
}
22.Algorithm Gossip: 中序式转后序式（前序式）
说明平常所使用的运算式，主要是将运算元放在运算子的两旁，例如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) {
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;
}
23.Algorithm Gossip: 后序式的运算
说明 将中序式转换为后序式的好处是，不用处理运算子先后顺序问题，只要依序由运算式由
前往后读取即可。
解法运算时由后序式的前方开
始读取，遇到运算元先存入
堆叠，如果遇到运算子，则
由堆叠中取出两个运算元进
行对应的运算，然后将结果
存回堆叠，如果运算式读取
完 毕，那么堆叠顶的值就是
答案了，例如我们计算
12+34+*这个运算式（也就是
(1+2)*(3+4)）： 读取
1
2
+
3
4
+
*
#include <stdio.h>
#include <stdlib.h>
void evalPf(char*);
double cal(double, char, double);
int main(void) {
char input[80];堆叠
1
12
3 // 1+2 后存回
33
334
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;
}
}
24.Algorithm Gossip: 洗扑克牌（乱数排列）
说明
洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如 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;
}
25.Algorithm Gossip: Craps 赌博游戏
说明一个简单的赌博游戏，游戏规则如下：玩家掷两个骰子，点数为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;
}
26.Algorithm Gossip: 约瑟夫问题（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 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12
22 33 13 29 23
由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第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; }
27.Algorithm Gossip: 排列组合
说明将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列
组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。
解法可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 3
4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的
数字旋转至最左边，并逐步增加旋转的间隔，例如：
1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递回处理
2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递回处理
3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递回处理
4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递回处理
#include <stdio.h>
#include <stdlib.h>
#define N 4
void perm(int*, int);
int main(void) {
int num[N+1], i;
for(i = 1; i <= N; i++)
num[i] = i;
perm(num, 1);
return 0;
}
void perm(int* num, int i) {
int j, k, tmp;
if(i < N) {
for(j = i; j <= N; j++) {
tmp = num[j];
// 旋转该区段最右边数字至最左边
for(k = j; k > i; k--)
num[k] = num[k-1];
num[i] = tmp;
perm(num, i+1);
// 还原
for(k = i; k < j; k++)
num[k] = num[k+1];
num[j] = tmp;
}
}
else { // 显示此次排列
for(j = 1; j <= N; j++)
printf("%d ", num[j]);
printf("\n");
}
}
28.Algorithm Gossip: 格雷码（Gray Code）
说明
Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任
两个数之间只有一个位元值不同，例如以下为3位元的Gray Code：
000 001 011 010 110 111 101 100
由定义可以知道，Gray Code的顺序并不是唯一的，例如将上面的数列反过来写，也是一组Gray
Code：
100 101 111 110 010 011 001 000
Gray Code是由贝尔实验室的Frank Gray在1940年代提出的，用来在使用PCM（Pusle Code
Modulation）方法传送讯号时避免出错，并于1953年三月十七日取得美国专利。
解法
由于Gray Code相邻两数之间只改变一个位元，所以可观 察Gray Code从1变0或从0变1时的
位置，假设有4位元的Gray Code如下：
0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000
观察奇数项的变化时，我们发现无论它是第几个Gray Code，永远只改变最右边的位元，如果
是1就改为0，如果是0就改为1。
观察偶数项的变化时，我们发现所改变的位元，是由右边算来第一个1的左边位元。
以上两个变化规则是固定的，无论位元数为何；所以只要判断位元的位置是奇数还是偶数，就
可以决定要改变哪一个位元的值，为了程式撰写方便，将阵列索引 0当作最右边的值，而在列
印结果时，是由索引数字大的开始反向列印。
将2位元的Gray Code当作平面座标来看，可以构成一个四边形，您可以发现从任一顶点出发，
绕四边形周长绕一圈，所经过的顶点座标就是一组 Gray Code，所以您可以得到四组 Gray
Code。
同样的将3位元的Gray Code当作平面座标来看的话，可以构成一个正立方体，如果您可以从任
一顶点出发，将所有的边长走过，并不重复经过顶点的话，所经过的顶点座标顺序之组合也就
是一组Gray Code。
#include <stdio.h>
#include <stdlib.h>
#define MAXBIT 20
#define TRUE 1
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0')
#define NEXT(x) x = (1 - (x))
int main(void) {
char digit[MAXBIT];
int i, bits, odd;
printf("输入位元数：");
scanf("%d", &bits);
for(i = 0; i < bits; i++) {
digit[i] = '0';
printf("0");
}
printf("\n");
odd = TRUE;
while(1) {
if(odd)
CHANGE_BIT(digit[0]);
else {
// 计算第一个1的位置
for(i = 0; i < bits && digit[i] == '0'; i++) ;
if(i == bits - 1) // 最后一个Gray Code
break;
CHANGE_BIT(digit[i+1]);
}
for(i = bits - 1; i >= 0; i--)
printf("%c", digit[i]);
printf("\n");
NEXT(odd);
}
return 0;
}
29.Algorithm Gossip: 产生可能的集合
说明
给定一组数字或符号，产生所有可能的集合（包括空集合）， 例如给定1 2 3，则可能的集合为：
{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
解法
如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意
1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例
如：000
001
010
011
100
101
110
111{}
{3}
{2}
{2,3}
{1}
{1,3}
{1,2}
{1,2,3}了解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned
型别加上&位元运算来产生，这边则是使用阵列搜 寻，首先阵列内容全为0，找第一个1，在还
没找到之前将走访过的内容变为0，而第一个找到的0则变为 1，如此重复直到所有的阵列元素
都变为1为止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111
如果要产生字典顺序，例如若有4个元素，则：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =>
{1,2,4} =>
{1,3} => {1,3,4} =>
{1,4} =>
{2} => {2,3} => {2,3,4} =>
{2,4} =>
{3} => {3,4} =>
{4}
简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而
倒数第二个元素是m的话，例如：
{a b c d e n}
则下一个集合就是{a b c d e+1}，再依序加入后续的元素。
例如有四个元素，而当产生{1 2 3 4}集合时，则下一个集合就是{1 2 3+1}，也就是{1 2 4}，由于
最后一个元素还是4，所以下一个集合就是{1 2+1}，也就是{1 3}，接下来再加入后续元素4，也
就是{1 3 4}，由于又遇到元素4，所以下一个集合是{1 3+1}，也就是{1 4}。
实作
C（无字典顺序）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
char digit[MAXSIZE];
int i, j;
int n;
printf("输入集合个数：");
scanf("%d", &n);
for(i = 0; i < n; i++)
digit[i] = '0';
printf("\n{}"); // 空集合
while(1) {
// 找第一个0，并将找到前所经过的元素变为0
for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++);
if(i == n) // 找不到0
break;else
// 将第一个找到的0变为1
digit[i] = '1';
// 找第一个1，并记录对应位置
for(i = 0; i < n && digit[i] == '0'; i++);
printf("\n{%d", i+1);
for(j = i + 1; j < n; j++)
if(digit[j] == '1')
printf(",%d", j + 1);
printf("}");
}
printf("\n");
return 0;
}
C（字典顺序）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
int set[MAXSIZE];
int i, n, position = 0;
printf("输入集合个数：");
scanf("%d", &n);
printf("\n{}");
set[position] = 1;
while(1) {
printf("\n{%d", set[0]); // 印第一个数
for(i = 1; i <= position; i++)
printf(",%d", set[i]);
printf("}");
if(set[position] < n) { // 递增集合个数
set[position+1] = set[position] + 1;
position++;
}
else if(position != 0) { // 如果不是第一个位置position--;
// 倒退
set[position]++; // 下一个集合尾数
}
else // 已倒退至第一个位置
break;
}
printf("\n");
return 0;
}
30.Algorithm Gossip: 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，也就是往左移一个位置；由于位置左移后，右边的元素会 经
过