C语言经典算法-6

其他经典例题跳转链接

C语言经典算法-1
1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官（一）6. 老鼠走迷官（二）7. 骑士走棋盘8. 八皇后9. 八枚银币10. 生命游戏

C语言经典算法-2
字串核对、双色、三色河内塔、背包问题（Knapsack Problem）、蒙地卡罗法求 PI、Eratosthenes筛选求质数

C语言经典算法-3
超长整数运算（大数运算）、长 PI、最大公因数、最小公倍数、因式分解、完美数、阿姆斯壮数

C语言经典算法-4
最大访客数、中序式转后序式（前序式）、后序式的运算、洗扑克牌（乱数排列）、Craps赌博游戏

C语言经典算法-5
约瑟夫问题（Josephus Problem）、排列组合、格雷码（Gray Code)、产生可能的集合、m元素集合的n个元素子集

C语言经典算法-6
数字拆解、得分排行，选择、插入、气泡排序、Shell 排序法 - 改良的插入排序、Shaker 排序法 - 改良的气泡排序

C语言经典算法-7
排序法 - 改良的选择排序、快速排序法（一）、快速排序法（二）、快速排序法（三）、合并排序法

C语言经典算法-8
基数排序法、循序搜寻法（使用卫兵）、二分搜寻法（搜寻原则的代表）、插补搜寻法、费氏搜寻法

C语言经典算法-9
稀疏矩阵、多维矩阵转一维矩阵、上三角、下三角、对称矩阵、奇数魔方阵、4N 魔方阵、2(2N+1) 魔方阵

31.数字拆解

说明
这个题目来自于 数字拆解，我将之改为C语言的版本，并加上说明。

题目是这样的：
3 = 2+1 = 1+1+1 所以3有三种拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

共七种

依此类推，请问一个指定数字NUM的拆解方法个数有多少个？
解法
我们以上例中最后一个数字5的拆解为例，假设f( n )为数字n的可拆解方式个数，而f(x, y)为使用y以下的数字来拆解x的方法个数，则观察：
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

使用函式来表示的话：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)

其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大于1的数字来拆解1没有意义，所以f(1, 4) = f(1, 1)，而同样的，f(0, 5)会等于f(0, 0)，所以：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)

依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解，其中f(4,1)其实就是f(5-1, min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n为要拆解的数字，而min()表示取两者中较小的数。

使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时，将每列的索引0与索引1元素值设定为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种：

for(i = 0; i < NUM +1; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 
}

接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM x (NUM/2+1)，以数字10为例，其维度为10 x 6我们的表格将会如下所示：
1 1 0 0 0 0
1 1 0 0 0 0
1 1 2 0 0 0
1 1 2 3 0 0
1 1 3 4 5 0
1 1 3 5 6 7
1 1 4 7 9 0
1 1 4 8 0 0
1 1 5 0 0 0
1 1 0 0 0 0

实作

C 
#include <stdio.h> 
#include <stdlib.h> 
#define NUM 10    //  要拆解的数字 
#define DEBUG 0 int main(void) { int table[NUM][NUM/2+1] = {0}; // 动态规画表格 int count = 0; int result = 0; int i, j, k; printf("数字拆解\n"); printf("3 = 2+1 = 1+1+1 所以3有三种拆法\n"); printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");   printf("共五种\n"); printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");printf("共七种\n"); printf("依此类推，求 %d 有几种拆法？", NUM); // 初始化 for(i = 0; i < NUM; i++){ table[i][0] = 1;  // 任何数以0以下的数拆解必只有1种 table[i][1] = 1;  // 任何数以1以下的数拆解必只有1种 }        // 动态规划 for(i = 2; i <= NUM; i++){ for(j = 2; j <= i; j++){ if(i + j > NUM) // 大于 NUM continue; count = 0;    for(k = 1 ; k <= j; k++){ count += table[i-k][(i-k >= k) ? k : i-k];                  } table[i][j] = count; }            } // 计算并显示结果 for(k = 1 ; k <= NUM; k++) result += table[NUM-k][(NUM-k >= k) ? k : NUM-k];                    printf("\n\nresult: %d\n", result); if(DEBUG) { printf("\n除错资讯\n"); for(i = 0; i < NUM; i++) { for(j = 0; j < NUM/2+1; j++) printf("%2d", table[i][j]); printf("\n"); } } return 0; 
} 

32.得分排行

说明假设有一教师依学生座号输入考试分数，现希望在输入完毕后自动显示学生分数的排行，当然学生的分数可能相同。
解法这个问题基本上要解不难，只要使用额外的一个排行阵列走访分数阵列就可以了，直接使用下面的程式片段作说明：

for(i = 0; i < count; i++) { juni[i] = 1; for(j = 0; j < count; j++) { if(score[j] > score[i]) juni[i]++; } 
} 
printf("得分\t排行\n"); 
for(i = 0; i < count; i++) printf("%d\t%d\n", score[i], juni[i]); 

上面这个方法虽然简单，但是反覆计算的次数是n^2，如果n值变大，那么运算的时间就会拖长；改变juni阵列的长度为n+2，并将初始值设定为0，如下所示：

接下来走访分数阵列，并在分数所对应的排行阵列索引元素上加1，如下所示：

将排行阵列最右边的元素设定为1，然后依序将右边的元素值加至左边一个元素，最后排行阵列中的「分数+1」」就是得该分数的排行，如下所示：

这样的方式看起来复杂，其实不过在计算某分数之前排行的人数，假设89分之前的排行人数为x人，则89分自然就是x+1了，这也是为什么排行阵列最右边要设定为1的原因；如果89分有y人，则88分自然就是x+y+1，整个阵列右边元素向左加的原因正是如此。
如果分数有负分的情况，由于C/C++或Java等程式语言无法处理负的索引，所以必须加上一个偏移值，将所有的分数先往右偏移一个范围即可，最后显示的时候记得减回偏移值就可以了。

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 100 
#define MIN 0 int main(void) { int score[MAX+1] = {0}; int juni[MAX+2] = {0}; int count = 0, i; do { printf("输入分数，-1结束："); scanf("%d", &score[count++]); } while(score[count-1] != -1);count--; for(i = 0; i < count; i++) juni[score[i]]++; juni[MAX+1] = 1; for(i = MAX; i >= MIN; i--) juni[i] = juni[i] + juni[i+1]; printf("得分\t排行\n"); for(i = 0; i < count; i++) printf("%d\t%d\n", score[i], juni[score[i]+1]); return 0; 
} 

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

说明选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最快的时间复杂度都是O(n2)），然而它们排序的方式确是值得观察与探讨的。
解法
选择排序
将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个最小值，并放入前端已排序部份的最后一个，例如：

排序前：70 80 31 37 10 1 48 60 33 80

[1] 80 31 37 10 70 48 60 33 80 选出最小值1
[1 10] 31 37 80 70 48 60 33 80 选出最小值10
[1 10 31] 37 80 70 48 60 33 80 选出最小值31
[1 10 31 33] 80 70 48 60 37 80 …
[1 10 31 33 37] 70 48 60 80 80 …
[1 10 31 33 37 48] 70 60 80 80 …
[1 10 31 33 37 48 60] 70 80 80 …
[1 10 31 33 37 48 60 70] 80 80 …
[1 10 31 33 37 48 60 70 80] 80 …

插入排序
像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如：

排序前：92 77 67 8 6 84 55 85 43 67

[77 92] 67 8 6 84 55 85 43 67 将77插入92前
[67 77 92] 8 6 84 55 85 43 67 将67插入77前
[8 67 77 92] 6 84 55 85 43 67 将8插入67前
[6 8 67 77 92] 84 55 85 43 67 将6插入8前
[6 8 67 77 84 92] 55 85 43 67 将84插入92前
[6 8 55 67 77 84 92] 85 43 67 将55插入67前
[6 8 55 67 77 84 85 92] 43 67 …
[6 8 43 55 67 77 84 85 92] 67 …
[6 8 43 55 67 67 77 84 85 92] …

气泡排序法
顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。

基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如：

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] …
27 6 9 18 49 [50 58 80 90 95] …
6 9 18 27 [49 50 58 80 90 95] …
6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束

在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的i+2至n已经排序完毕，这也增进了气泡排序的效率。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void selsort(int[]);  // 选择排序 
void insort(int[]);   // 插入排序 
void bubsort(int[]);  // 气泡排序 int main(void) {  int number[MAX] = {0}; int i;  srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } printf("\n请选择排序方式：\n"); printf("(1)选择排序\n(2)插入排序\n(3)气泡排序\n:"); scanf("%d", &i); switch(i) { case 1: selsort(number); break; case 2: insort(number); break; case 3: bubsort(number); break; default: printf("选项错误(1..3)\n"); } return 0; 
} void selsort(int number[]) { int i, j, k, m; for(i = 0; i < MAX-1; i++) { m = i; for(j = i+1; j < MAX; j++) if(number[j] < number[m]) m = j; if( i != m) SWAP(number[i], number[m]) printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } } void insort(int number[]) { int i, j, k, tmp; for(j = 1; j < MAX; j++) { tmp = number[j]; i = j - 1; while(tmp < number[i]) { number[i+1] = number[i]; i--; if(i == -1) break; } number[i+1] = tmp; printf("第 %d 次排序：", j); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } 
} void bubsort(int number[]) { int i, j, k, flag = 1; for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } 
} 

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

说明
插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速度不快。

排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。
解法
Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时并不是所有的元素同时进行时，而是取一段间隔。

Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来间隔设定为n/8、n/16，直到间隔为1之后的最 后一次排序终止，由于上一次的排序动作都会将固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此最后几次的排序动作将 可以大幅减低。

举个例子来说，假设有一未排序的数字如右：89 12 65 97 61 81 27 2 61 98

数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5，此时我们对间隔为5的数字进行排序，如下所示：

画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商，也就是2，则第二次的插入排序对象如下所示：

再来间隔设定为2 / 2 = 1，此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了，所以最后一次的插入排序几乎没作什么排序动作了：

将间隔设定为n / 2是D.L Shell最初所提出，在教科书中使用这个间隔比较好说明，然而Shell排序法的关键在于间隔的选定，例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度：

其中4*(2j)2 + 3*(2j) + 1不可超过元素总数n值，使用上式找出j后代入4*(2j)2 + 3*(2j) + 1求得第一个间隔，然后将2j除以2代入求得第二个间隔，再来依此类推。

后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快；另外Shell排序法的概念也可以用来改良气泡排序法。
实作

C 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shellsort(int[]); int main(void) { int number[MAX] = {0}; int i;  srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } shellsort(number); return 0; 
} void shellsort(int number[]) { int i, j, k, gap, t; gap = MAX / 2; while(gap > 0) { for(k = 0; k < gap; k++) { for(i = k+gap; i < MAX; i+=gap) { for(j = i - gap; j >= k; j-=gap) { if(number[j] > number[j+gap]) { SWAP(number[j], number[j+gap]); } else break; } } } printf("\ngap = %d：", gap); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n"); gap /= 2; } 
} 

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

说明
请看看之前介绍过的气泡排序法：

 for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } 
} 

事实上这个气泡排序法已经不是单纯的气泡排序了，它使用了旗标与右端左移两个方法来改进排序的效能，而Shaker排序法使用到后面这个观念进一步改良气泡排序法。
解法
在上面的气泡排序法中，交换的动作并不会一直进行至阵列的最后一个，而是会进行至MAX-i-1，所以排序的过程中，阵列右方排序好的元素会一直增加，使得左边排序的次数逐渐减少，如我们的例子所示：

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] …
27 6 9 18 49 [50 58 80 90 95] …
6 9 18 27 [49 50 58 80 90 95] …
6 9 18 [27 49 50 58 80 90 95]

方括号括住的部份表示已排序完毕，Shaker排序使用了这个概念，如果让左边的元素也具有这样的性质，让左右两边的元素都能先排序完成，如此未排序的元素会集中在中间，由于左右两边同时排序，中间未排序的部份将会很快的减少。

方法就在于气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作，而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。

一个排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 [81]
向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]

如上所示，括号中表示左右两边已排序完成的部份，当left > right时，则排序完成。

实作

C 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shakersort(int[]); int main(void) { int number[MAX] = {0}; int i;  srand(time(NULL)); 

系列好文，点击链接即可跳转

C语言经典算法-5
约瑟夫问题（Josephus Problem）、排列组合、格雷码（Gray Code)、产生可能的集合、m元素集合的n个元素子集

C语言经典算法-7
排序法 - 改良的选择排序、快速排序法（一）、快速排序法（二）、快速排序法（三）、合并排序法