经典算法大全
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: 阿姆斯壮数
13.AlgorithmGossip:背包问题（KnapsackProblem）
说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物
品，假设是水果好了，水果的编号、单价与重量如下所示：
解法背包问题是关于最佳化的问题，要解最佳化问题可以使用「动态规划」（Dynamic
programming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加
入至集合中，最后得到的就是最佳解。
以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表
示最后一个放至背包的水果，假设有负重量 1～8的背包8个，并对每个背包求其最佳解。
逐步将水果放入背包中，并求该阶段的最佳解：
由最后一个表格，可以得知在背包负重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;
};
背包负重 1 2 3 4 5 6 7 8
value 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0
item 3 2 3 ０ 1 3 2 3 背包负重 1 2 3 4 5 6 7 8
value 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0
item 3 2 3 ０ 1 3 2 3
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.AlgorithmGossip:蒙地卡罗法求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.AlgorithmGossip:Eratosthenes筛选求质数
说明除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的
求出质数则一直是程式设计人员与数学家努力的课题，在这边介绍一个着名的 Eratosthenes求质
数方法。
解法首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以
整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？
首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设
A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整 除N。不过在程式中使用开根号会精确度的问题，所以可以使用 i*i <= N进行检查，且执行更快 。
再来假设有一个筛子存放1～N，例如：
先将2的倍数筛去：
再将3的倍数筛去：
再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的
数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）。
检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍
数，使得程式中的if的检查动作可以减少。
实作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;
};
背包负重 1 2 3 4 5 6 7 8
value 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0
item 3 2 3 ０ 1 3 2 3 背包负重 1 2 3 4 5 6 7 8
value 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0
item 3 2 3 ０ 1 3 2 3
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]);
} }
16.AlgorithmGossip:超长整数运算（大数运算）
说明基于记忆体的有效运用，程式语言中规定了各种不同的资料型态，也因此变数所可以表
达的最大整数受到限制，例如123456789123456789这样的 整数就不可能储存在long变数中（例
如C/C++等），我们称这为long数，这边翻为超长整数（避免与资料型态的长整数翻译混淆），或俗称大数运算。
解法一个变数无法表示超长整数，则就使用多个变数，当然这使用阵列最为方便，假设程式
语言的最大资料型态可以储存至65535的数好了，为了计算方便及符合使用十进位制的习惯，让
每一个阵列元素可以储存四个位数，也就是0到9999的数，例如：
很多人问到如何计算像50!这样的问题，解法就是使用程式中的乘法函式，至于要算到多大，就
看需求了。
由于使用阵列来储存数值，关于数值在运算时的加减乘除等各种运算、位数的进位或借位就必
须自行定义，加、减、乘都是由低位数开始运算，而除法则是由高位数开始运算，这边直接提
供加减乘除运算的函式供作参考，以下的N为阵列长度。
#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;
}17.AlgorithmGossip:长PI
说明圆周率后的小数位数是无止境的，如何使用电脑来计算这无止境的小数是一些数学家与程式设计师所感兴趣的，在这边介绍一个公式配合 大数运算，可以计算指定位数的圆周率。
解法首先介绍J.Marchin的圆周率公式
可以将这个公式整理为：
也就是说第n项，若为奇数则为正数，为偶数则为负数，而项数表示方式为：
如果我们要计算圆周率至10的负L次方，由于[16/52*n-1 - 4/2392*n-1]中16/52*n-1比4/2392*n-1来的
大，具有决定性，所以表示至少必须计算至第n项：
将上面的等式取log并经过化简，我们可以求得：
在上式中[]为高斯符号，也就是取至整数（不大于L/1.39794的整数）；为了计简方便，可以在程
式中使用下面这个公式来计简第n项：
至于大数运算的演算法，请参考之前的文章，必须注意的是在输出时，由于是输出阵列中的整
数值，如果阵列中整数位数不满四位，则必须补上0，在C语言中只要 使用格式指定字%04d，
使得不足位数部份自动补上0再输出，至于Java的部份，使用 NumberFormat来作格式化。
#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;
}18.AlgorithmGossip:最大公因数、最小公倍数、因式分解
说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：
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.AlgorithmGossip:完美数
说明如果有一数n，其真因数（Proper factor）的总和等于n，则称之为完美数（Perfect Number），
例如以下几个数都是完美数：
程式基本上不难，第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数和，不过若n
值很大，则此法会花费许多时间在回圈测试上，十分没有效率，例如求小于10000的所有完美数 。
解法如何求小于10000的所有完美数？并将程式写的有效率？基本上有三个步骤：
求出一定数目的质数表
利用质数表求指定数的因式分解
利用因式分解求所有真因数和，并检查是否为完美数
步骤一 与 步骤二 在之前讨论过了，问题在步骤三，如何求真因数和？方法很简单，要先知道
将所有真因数和加上该数本身，会等于该数的两倍，例如：
所以只要求出因式分解，就可以利用回圈求得等式后面的值，将该值除以2就是真因数和了；等
式后面第一眼看时可能想到使用等比级数公式来解，不过会使用到次方运算，可以在回圈走访
因式分解阵列时，同时计算出等式后面的值，这在下面的实作中可以看到。
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;
} }20.AlgorithmGossip:阿姆斯壮数
说明
在三位的整数中，例如153可以满足13 + 53 + 33 = 153，这样的数称之为Armstrong数，试写出一
程式找出所有的三位数Armstrong数。
解法
Armstrong数的寻找，其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只
要使用除法与余数运算就可以了，例如输入 input为abc，则：
#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;
}