C++中你必须知道的23种算法
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.最大公因数、最小公倍数、因式分解
说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：
易做图*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("易做图：%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("
补充：软件开发 , C++ ,
