独家整理算法书籍与训练题干货

1.汉若塔 .........................................................................................................................................................2

2.费式数列 .....................................................................................................................................................3

3. 巴斯卡三角形 ...........................................................................................................................................4

4.三色棋 .........................................................................................................................................................5

5.老鼠走迷官（一） .....................................................................................................................................7

6.老鼠走迷官（二） .....................................................................................................................................9

7.骑士走棋盘 ...............................................................................................................................................10

14.蒙地卡罗法求 PI....................................................................................................................................31

15.Eratosthenes 筛选求质数 ........................................................................................................................32

16.超长整数运算（大数运算） .................................................................................................................34

17.长 PI........................................................................................................................................................36

18.最大公因数、最小公倍数、因式分解 .................................................................................................39

19.完美数 .....................................................................................................................................................42

20.阿姆斯壮数 .............................................................................................................................................45

21.最大访客数 .............................................................................................................................................46

22.中序式转后序式（前序式） .................................................................................................................48

23.后序式的运算 .........................................................................................................................................52

30.m 元素集合的 n 个元素子集 .................................................................................................................66

31.数字拆解 .................................................................................................................................................68

32.得分排行 .................................................................................................................................................71

33.选择、插入、气泡排序 .........................................................................................................................73

34.Shell 排序法 - 改良的插入排序..........................................................................................................77

35.Shaker 排序法 - 改良的气泡排序 .......................................................................................................80

36.排序法 - 改良的选择排序 ....................................................................................................................82

37.快速排序法（一） .................................................................................................................................86

38.快速排序法（二） .................................................................................................................................88

39.快速排序法（三） .................................................................................................................................90

46.稀疏矩阵 ...............................................................................................................................................110

47.多维矩阵转一维矩阵 ...........................................................................................................................111

48.上三角、下三角、对称矩阵 ...............................................................................................................113

49.奇数魔方阵 ...........................................................................................................................................115

50.4N 魔方阵.............................................................................................................................................117

51.2(2N+1) 魔方阵....................................................................................................................................119

1.汉若塔

说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡

志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）

所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移

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("请输入盘数：");

scanf("%d", &n);

hanoi(n, 'A', 'B', 'C');

return 0;

}

2.费式数列

说明

Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生

产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。

如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植

#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++)

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

printf(" ");

} /* 排版设定结束 */

printf("%3d", combi(n, r));

}

printf("\n");

}

}

4.三色棋

说明

三色旗的问题最早由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 RED 'r'

#define SWAP(x, y) { char temp; \

temp = color[x]; \

color[x] = color[y]; \

int bFlag = 0;

int i;

for(i = 0; i < strlen(color); i++)

printf("%c ", color[i]);

printf("\n");