1.河内之塔
说明
河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时
北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世
纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64
个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根
石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬
运完毕之时，此塔将毁损，而也就是世界末日来临之时。
解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘
子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处
理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式
的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则
所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，
如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。
#include <stdio.h>
void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
}
else {
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}
}
int main() {
int n;
printf("请输入盘数：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
2.超长整数运算（大数运算）
说明基于记忆体的有效运用，程式语言中规定了各种不同的资料型态，也因此变数所可以表
达的最大整数受到限制，例如123456789123456789这样的整数就不可能储存在long变数中（例
如C/C++等），我们称这为long数，这边翻为超长整数（避免与资料型态的长整数翻译混淆），或
俗称大数运算。
解法一个变数无法表示超长整数，则就使用多个变数，当然这使用阵列最为方便，假设程式
语言的最大资料型态可以储存至65535的数好了，为了计算方便及符合使用十进位制的习惯，让
每一个阵列元素可以储存四个位数，也就是0到9999的数，例如：
很多人问到如何计算像50!这样的问题，解法就是使用程式中的乘法函式，至于要算到多大，就
看需求了。
由于使用阵列来储存数值，关于数值在运算时的加减乘除等各种运算、位数的进位或借位就必
须自行定义，加、减、乘都是由低位数开始运算，而除法则是由高位数开始运算，这边直接提
供加减乘除运算的函式供作参考，以下的N为阵列长度。
void add(int *a, int *b, int *c) {
int i, carry = 0;
for(i = N - 1; i >= 0; i--) {
c[i] = a[i] + b[i] + carry;
if(c[i] < 10000)
carry = 0;
else { // 进位
c[i] = c[i] - 10000;
carry = 1;
}
}
}
void sub(int *a, int *b, int *c) {
int i, borrow = 0;
for(i = N - 1; i >= 0; i--) {
c[i] = a[i] - b[i] - borrow;
if(c[i] >= 0)
borrow = 0;
else { // 借位
c[i] = c[i] + 10000;
borrow = 1;
}
}
}
void mul(int *a, int b, int *c) { // b 为乘数
int i, tmp, carry = 0;
for(i = N - 1; i >=0; i--) {
tmp = a[i] * b + carry;
c[i] = tmp % 10000;
carry = tmp / 10000;
}
}
void div(int *a, int b, int *c) { // b 为除数
int i, tmp, remain = 0;
for(i = 0; i < N; i++) {
tmp = a[i] + remain;
c[i] = tmp / b;
remain = (tmp % b) * 10000;
}
}
3.最大公因数、最小公倍数、因式分解
说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：
GCD*LCM=两数乘积
解法最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当
作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所
有质数，并试试看是不是可以整除，求质数的问题是另一个课题，请参考Eratosthenes 筛选求
质数。
实作（最大公因数、最小公倍数）
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int m, n, r;
int s;
printf("输入两数：");
scanf("%d %d", &m, &n);
s = m * n;
while(n != 0) {
r = m % n;
m = n;
n = r;
}
printf("GCD：%d\n", m);
printf("LCM：%d\n", s/m);
return 0;
}
实作（因式分解）
C（不用质数表）
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int i, n;
printf("请输入整数：");
scanf("%d", &n);
printf("%d = ", n);
for(i = 2; i * i <= n;) {
if(n % i == 0) {
printf("%d * ", i);
n /= i;
}
else
i++;
}
printf("%d\n", n);
return 0;
}
C（使用质数表）
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int prime(int*); // 求质数表
void factor(int*, int); // 求factor
int main(void) {
int ptable[N+1] = {0};
int count, i, temp;
count = prime(ptable);
printf("请输入一数：");
scanf("%d", &temp);
factor(ptable, temp);
printf("\n");
return 0;
}
int prime(int* pNum) {
int i, j;
int prime[N+1];
for(i = 2; i <= N; i++)
prime[i] = 1;
for(i = 2; i*i <= N; i++) {
if(prime[i] == 1) {
for(j = 2*i; j <= N; j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
for(i = 2, j = 0; i < N; i++) {
if(prime[i] == 1)
pNum[j++] = i;
}
return j;
}
void factor(int* table, int num) {
int i;
for(i = 0; table[i] * table[i] <= num;) {
if(num % table[i] == 0) {
printf("%d * ", table[i]);
num /= table[i];
}
else
i++;
}
printf("%d\n", num);
}
4.完美数
说明如果有一数n，其真因数（Proper factor）的总和等于n，则称之为完美数（Perfect Number），
例如以下几个数都是完美数：
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
程式基本上不难，第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数和，不过若n
值很大，则此法会花费许多时间在回圈测试上，十分没有效率，例如求小于10000的所有完美数。
解法如何求小于10000的所有完美数？并将程式写的有效率？基本上有三个步骤：
求出一定数目的质数表
利用质数表求指定数的因式分解
利用因式分解求所有真因数和，并检查是否为完美数
步骤一与步骤二在之前讨论过了，问题在步骤三，如何求真因数和？方法很简单，要先知道
将所有真因数和加上该数本身，会等于该数的两倍，例如：
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28
等式后面可以化为：
2 * 28 = (20
+ 21 + 22) * (70
+ 71)
所以只要求出因式分解，就可以利用回圈求得等式后面的值，将该值除以2就是真因数和了；等
式后面第一眼看时可能想到使用等比级数公式来解，不过会使用到次方运算，可以在回圈走访
因式分解阵列时，同时计算出等式后面的值，这在下面的实作中可以看到。
#include <stdio.h>
#include <stdlib.h>
#define N 1000
#define P 10000
int prime(int*); // 求质数表
int factor(int*, int, int*); // 求factor
int fsum(int*, int); // sum ot proper factor
int main(void) {
int ptable[N+1] = {0}; // 储存质数表
int fact[N+1] = {0}; // 储存因式分解结果
int count1, count2, i;
count1 = prime(ptable);
for(i = 0; i <= P; i++) {
count2 = factor(ptable, i, fact);
if(i == fsum(fact, count2))
printf("Perfect Number: %d\n", i);
}
printf("\n");
return 0;
}
int prime(int* pNum) {
int i, j;
int prime[N+1];
for(i = 2; i <= N; i++)
prime[i] = 1;
for(i = 2; i*i <= N; i++) {
if(prime[i] == 1) {
for(j = 2*i; j <= N; j++) {
if(j % i == 0)
prime[j] = 0;
}
}
}
for(i = 2, j = 0; i < N; i++) {
if(prime[i] == 1)
pNum[j++] = i;
}
return j;
}
int factor(int* table, int num, int* frecord) {
int i, k;
for(i = 0, k = 0; table[i] * table[i] <= num;) {
if(num % table[i] == 0) {
frecord[k] = table[i];
k++;
num /= table[i];
}
else
i++;
}
frecord[k] = num;
return k+1;
}
int fsum(int* farr, int c) {
int i, r, s, q;
i = 0;
r = 1;
s = 1;
q = 1;
while(i < c) {
do {
r *= farr[i];
q += r;
i++;
} while(i < c-1 && farr[i-1] == farr[i]);
s *= q;
r = 1;
q = 1;
}
return s / 2;
}
5.阿姆斯壮数
说明
在三位的整数中，例如153可以满足13
+ 53 + 33
= 153，这样的数称之为Armstrong数，试写出一
程式找出所有的三位数Armstrong数。
解法
Armstrong数的寻找，其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只
要使用除法与余数运算就可以了，例如输入input为abc，则：
a = input / 100
b = (input%100) / 10
c = input % 10
#include <stdio.h>
#include <time.h>
#include <math.h>
int main(void) {
int a, b, c;
int input;
printf("寻找Armstrong数：\n");
for(input = 100; input <= 999; input++) {
a = input / 100;
b = (input % 100) / 10;
c = input % 10;
if(a*a*a + b*b*b + c*c*c == input)
printf("%d ", input);
}
printf("\n");
return 0;
}
6.最大访客数
说明
现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计
不同时间的最大访客数。
解法
这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访
时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假
设访客i 的来访时间为x[i]，而离开时间为y[i]。
在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之
前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
int partition(int[], int, int);
void quicksort(int[], int, int); // 快速排序法
int maxguest(int[], int[], int, int);
int main(void) {
int x[MAX] = {0};
int y[MAX] = {0};
int time = 0;
int count = 0;
printf("\n输入来访与离开125;时间(0~24)：");
printf("\n范例：10 15");
printf("\n输入-1 -1结束");
while(count < MAX) {
printf("\n>>");
scanf("%d %d", &x[count], &y[count]);
if(x[count] < 0)
break;
count++;
}
if(count >= MAX) {
printf("\n超出最大访客数(%d)", MAX);
count--;
}
// 预先排序
quicksort(x, 0, count);
quicksort(y, 0, count);
while(time < 25) {
printf("\n%d 时的最大访客数：%d",
time, maxguest(x, y, count, time));
time++;
}
printf("\n");
return 0;
}
int maxguest(int x[], int y[], int count, int time) {
int i, num = 0;
for(i = 0; i <= count; i++) {
if(time > x[i])
num++;
if(time > y[i])
num--;
}
return num;
}
int partition(int number[], int left, int right) {
int i, j, s;
s = number[right];
i = left - 1;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}
void quicksort(int number[], int left, int right) {
int q;
if(left < right) {
q = partition(number, left, right);
quicksort(number, left, q-1);
quicksort(number, q+1, right);
}
}
7.中序式转后序式（前序式）
说明平常所使用的运算式，主要是将运算元放在运算子的两旁，例如a+b/d这样的式子，这称
之为中序（Infix）表示式，对于人类来说，这样的式子很容易理解，但由于电脑执行指令时是
有顺序的，遇到中序表示式时，无法直接进行运算，而必须进一步判断运算的先后顺序，所以
必须将中序表示式转换为另一种表示方法。
可以将中序表示式转换为后序（Postfix）表示式，后序表示式又称之为逆向波兰表示式（Reverse
polish notation），它是由波兰的数学家卢卡谢维奇提出，例如(a+b)*(c+d)这个式子，表示为后序
表示式时是ab+cd+*。
解法用手算的方式来计算后序式相当的简单，将运算子两旁的运算元依先后顺序全括号起来，
然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始），最后去掉所有的左括号
就可以完成后序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+
如果要用程式来进行中序转后序，则必须使用堆叠，演算法很简单，直接叙述的话就是使用回
圈，取出中序式的字元，遇运算元直接输出，堆叠运算子与左括号， ISP>ICP的话直接输出堆
叠中的运算子，遇右括号输出堆叠中的运算子至左括号。
如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，
其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就
是前序表示式。
实作
C
#include <stdio.h>
#include <stdlib.h>
int postfix(char*); // 中序转后序
int priority(char); // 决定运算子优先顺序
int main(void) {
例如(a+b)*(c+d)
这个式子，依演算
法的输出过程如
下： OP
STACK OUTPUT
( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*
char input[80];
printf("输入中序运算式：");
scanf("%s", input);
postfix(input);
return 0;
}
int postfix(char* infix) {
int i = 0, top = 0;
char stack[80] = {'\0'};
char op;
while(1) {
op = infix[i];
switch(op) {
case '\0':
while(top > 0) {
printf("%c", stack[top]);
top--;
}
printf("\n");
return 0;
// 运算子堆叠
case '(':
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(op)) {
printf("%c", stack[top]);
top--;
}
// 存入堆叠
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
// 遇) 输出至(
case ')':
while(stack[top] != '(') {
printf("%c", stack[top]);
top--;
}
top--; // 不输出(
break;
// 运算元直接输出
default:
printf("%c", op);
break;
}
i++;
}
}
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
default:
p = 0;
break;
}
return p;
}
8.中序式转后序式（前序式）
说明平常所使用的运算式，主要是将运算元放在运算子的两旁，例如a+b/d这样的式子，这称
之为中序（Infix）表示式，对于人类来说，这样的式子很容易理解，但由于电脑执行指令时是
有顺序的，遇到中序表示式时，无法直接进行运算，而必须进一步判断运算的先后顺序，所以
必须将中序表示式转换为另一种表示方法。
可以将中序表示式转换为后序（Postfix）表示式，后序表示式又称之为逆向波兰表示式（Reverse
polish notation），它是由波兰的数学家卢卡谢维奇提出，例如(a+b)*(c+d)这个式子，表示为后序
表示式时是ab+cd+*。
解法用手算的方式来计算后序式相当的简单，将运算子两旁的运算元依先后顺序全括号起来，
然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始），最后去掉所有的左括号
就可以完成后序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+
如果要用程式来进行中序转后序，则必须使用堆叠，演算法很简单，直接叙述的话就是使用回
圈，取出中序式的字元，遇运算元直接输出，堆叠运算子与左括号， ISP>ICP的话直接输出堆
叠中的运算子，遇右括号输出堆叠中的运算子至左括号。
如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反，
其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的值由上往下读出，如此就
是前序表示式。
实作
C
#include <stdio.h>
#include <stdlib.h>
int postfix(char*); // 中序转后序
int priority(char); // 决定运算子优先顺序
int main(void) {
例如(a+b)*(c+d)
这个式子，依演算
法的输出过程如
下： OP
STACK OUTPUT
( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*
char input[80];
printf("输入中序运算式：");
scanf("%s", input);
postfix(input);
return 0;
}
int postfix(char* infix) {
int i = 0, top = 0;
char stack[80] = {'\0'};
char op;
while(1) {
op = infix[i];
switch(op) {
case '\0':
while(top > 0) {
printf("%c", stack[top]);
top--;
}
printf("\n");
return 0;
// 运算子堆叠
case '(':
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(op)) {
printf("%c", stack[top]);
top--;
}
// 存入堆叠
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = op;
}
break;
// 遇) 输出至(
case ')':
while(stack[top] != '(') {
printf("%c", stack[top]);
top--;
}
top--; // 不输出(
break;
// 运算元直接输出
default:
printf("%c", op);
break;
}
i++;
}
}
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
default:
p = 0;
break;
}
return p;
}
9.后序式的运算
说明将中序式转换为后序式的好处是，不用处理运算子先后顺序问题，只要依序由运算式由
前往后读取即可。
解法
#include <stdio.h>
#include <stdlib.h>
void evalPf(char*);
double cal(double, char, double);
int main(void) {
char input[80];
运算时由后序式的前方开
始读取，遇到运算元先存入
堆叠，如果遇到运算子，则
由堆叠中取出两个运算元进
行对应的运算，然后将结果
存回堆叠，如果运算式读取
完毕，那么堆叠顶的值就是
答案了， 例如我们计算
12+34+*这个运算式（也就是
(1+2)*(3+4)）：读取
堆叠
1 1
2 1 2
+ 3 // 1+2 后存回
3 3 3