C语言经典算法-5

其他经典例题跳转链接

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) 魔方阵

26.约瑟夫问题（Josephus Problem）

说明据说着名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
解法约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：

使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示：

14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23

由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

#include <stdio.h> 
#include <stdlib.h> 
#define N 41 
#define M 3 int main(void) { int man[N] = {0}; int count = 1; int i = 0, pos = -1; int alive = 0; while(count <= N) { do { pos = (pos+1) % N;  // 环状处理 if(man[pos] == 0) i++; if(i == M) {  // 报数为3了 i = 0; break; } } while(1); man[pos] = count; count++; } printf("\n约琴夫排列："); for(i = 0; i < N; i++) printf("%d ", man[i]); printf("\n\n您想要救多少人？"); scanf("%d", &alive); printf("\nL表示这%d人要放的位置：\n", alive); for(i = 0; i < N; i++) { if(man[i] > alive) 	printf("D"); else 	printf("L"); if((i+1) % 5 == 0) 	printf("  "); } printf("\n"); return 0; } 

27.排列组合

说明将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。
解法可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：

1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递回处理
2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递回处理
3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递回处理
4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递回处理

#include <stdio.h> 
#include <stdlib.h> 
#define N 4 void perm(int*, int); int main(void) { int num[N+1], i; for(i = 1; i <= N; i++) num[i] = i; perm(num, 1); return 0; 
} void perm(int* num, int i) { int j, k, tmp; if(i < N) { for(j = i; j <= N; j++) { tmp = num[j]; // 旋转该区段最右边数字至最左边 for(k = j; k > i; k--) num[k] = num[k-1]; num[i] = tmp; perm(num, i+1); // 还原 for(k = i; k < j; k++) num[k] = num[k+1]; num[j] = tmp; } } else {  // 显示此次排列 for(j = 1; j <= N; j++) printf("%d ", num[j]); printf("\n"); } 
}  

28.格雷码（Gray Code）

说明
Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任两个数之间只有一个位元值不同，例如以下为3位元的Gray Code：

000 001 011 010 110 111 101 100

由定义可以知道，Gray Code的顺序并不是唯一的，例如将上面的数列反过来写，也是一组Gray Code：

100 101 111 110 010 011 001 000

Gray Code是由贝尔实验室的Frank Gray在1940年代提出的，用来在使用PCM（Pusle Code Modulation）方法传送讯号时避免出错，并于1953年三月十七日取得美国专利。
解法
由于Gray Code相邻两数之间只改变一个位元，所以可观 察Gray Code从1变0或从0变1时的位置，假设有4位元的Gray Code如下：

0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

观察奇数项的变化时，我们发现无论它是第几个Gray Code，永远只改变最右边的位元，如果是1就改为0，如果是0就改为1。

观察偶数项的变化时，我们发现所改变的位元，是由右边算来第一个1的左边位元。

以上两个变化规则是固定的，无论位元数为何；所以只要判断位元的位置是奇数还是偶数，就可以决定要改变哪一个位元的值，为了程式撰写方便，将阵列索引 0当作最右边的值，而在列印结果时，是由索引数字大的开始反向列印。

将2位元的Gray Code当作平面座标来看，可以构成一个四边形，您可以发现从任一顶点出发，绕四边形周长绕一圈，所经过的顶点座标就是一组Gray Code，所以您可以得到四组Gray Code。

同样的将3位元的Gray Code当作平面座标来看的话，可以构成一个正立方体，如果您可以从任一顶点出发，将所有的边长走过，并不重复经过顶点的话，所经过的顶点座标顺序之组合也就是一组Gray Code。

#include <stdio.h> 
#include <stdlib.h> #define MAXBIT 20 
#define TRUE 1 
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0') 
#define NEXT(x) x = (1 - (x)) int main(void) { char digit[MAXBIT]; int i, bits, odd; printf("输入位元数："); scanf("%d", &bits); for(i = 0; i < bits; i++) { digit[i] = '0'; printf("0"); } printf("\n"); odd = TRUE; while(1) { if(odd) CHANGE_BIT(digit[0]); else { // 计算第一个1的位置 for(i = 0; i < bits && digit[i] == '0'; i++) ; if(i == bits - 1) // 最后一个Gray Code break; CHANGE_BIT(digit[i+1]); } for(i = bits - 1; i >= 0; i--) printf("%c", digit[i]); printf("\n"); NEXT(odd); } return 0; 
} 

29.产生可能的集合

说明
给定一组数字或符号，产生所有可能的集合（包括空集合），例如给定1 2 3，则可能的集合为：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
解法
如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例如：

Input	Set
000	{}
001	{3}
010	{2}
011	{2,3}
100	{1}
101	{1,3}
110	{1,2}
111	{1,2,3}

了解这个方法之后，剩下的就是如何产生二进位数？有许多方法可以使用，您可以使用unsigned型别加上&位元运算来产生，这边则是使用阵列搜 寻，首先阵列内容全为0，找第一个1，在还没找到之前将走访过的内容变为0，而第一个找到的0则变为 1，如此重复直到所有的阵列元素都变为1为止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111

如果要产生字典顺序，例如若有4个元素，则：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =>
{1,2,4} =>
{1,3} => {1,3,4} =>
{1,4} =>
{2} => {2,3} => {2,3,4} =>
{2,4} =>
{3} => {3,4} =>
{4}

简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而倒数第二个元素是m的话，例如：
{a b c d e n}

则下一个集合就是{a b c d e+1}，再依序加入后续的元素。

例如有四个元素，而当产生{1 2 3 4}集合时，则下一个集合就是{1 2 3+1}，也就是{1 2 4}，由于最后一个元素还是4，所以下一个集合就是{1 2+1}，也就是{1 3}，接下来再加入后续元素4，也就是{1 3 4}，由于又遇到元素4，所以下一个集合是{1 3+1}，也就是{1 4}。
实作

C（无字典顺序） 
#include <stdio.h> 
#include <stdlib.h> #define MAXSIZE 20 int main(void) { char digit[MAXSIZE]; int i, j; int n; printf("输入集合个数："); scanf("%d", &n); for(i = 0; i < n; i++) digit[i] = '0'; printf("\n{}"); // 空集合 while(1) { // 找第一个0，并将找到前所经过的元素变为0 for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++); if(i == n)  // 找不到0 break; else          // 将第一个找到的0变为1 digit[i] = '1'; // 找第一个1，并记录对应位置 for(i = 0; i < n && digit[i] == '0'; i++); printf("\n{%d", i+1); for(j = i + 1; j < n; j++) if(digit[j] == '1') printf(",%d", j + 1); printf("}"); } printf("\n"); return 0; 
} 

C（字典顺序） 
#include <stdio.h> 
#include <stdlib.h> #define MAXSIZE 20 int main(void) { int set[MAXSIZE]; int i, n, position = 0; printf("输入集合个数："); scanf("%d", &n); printf("\n{}"); set[position] = 1; while(1) { printf("\n{%d", set[0]);  // 印第一个数 for(i = 1; i <= position; i++) printf(",%d", set[i]); printf("}"); if(set[position] < n) {  // 递增集合个数 set[position+1] = set[position] + 1; position++; } else if(position != 0) {  // 如果不是第一个位置 position--;       // 倒退 set[position]++;  // 下一个集合尾数 } else  // 已倒退至第一个位置 break; } printf("\n"); return 0; 
} 

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

说明
假设有个集合拥有m个元素，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有那些？
解法
假设有5个元素的集点，取出3个元素的可能子集如下：
{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5}

这些子集已经使用字典顺序排列，如此才可以观察出一些规则：
如果最右一个元素小于m，则如同码表一样的不断加1
如果右边一位已至最大值，则加1的位置往左移
每次加1的位置往左移后，必须重新调整右边的元素为递减顺序

所以关键点就在于哪一个位置必须进行加1的动作，到底是最右一个位置要加1？还是其它的位置？

在实际撰写程式时，可以使用一个变数positon来记录加1的位置，position的初值设定为n-1，因为我们要使用阵列，而最右边的索引值为最大 的n-1，在position位置的值若小于m就不断加1，如果大于m了，position就减1，也就是往左移一个位置；由于位置左移后，右边的元素会 经过调整，所以我们必须检查最右边的元素是否小于m，如果是，则position调整回n-1，如果不是，则positon维持不变。
实作

#include <stdio.h> 
#include <stdlib.h> #define MAX 20 int main(void) { int set[MAX]; int m, n, position; int i; printf("输入集合个数 m："); scanf("%d", &m); printf("输入取出元素 n："); scanf("%d", &n); for(i = 0; i < n; i++) set[i] = i + 1; // 显示第一个集合 for(i = 0; i < n; i++) printf("%d ", set[i]); putchar('\n'); position = n - 1; while(1) { if(set[n-1] == m) position--; else position = n - 1; set[position]++; // 调整右边元素 for(i = position + 1; i < n; i++) set[i] = set[i-1] + 1; for(i = 0; i < n; i++) printf("%d ", set[i]); putchar('\n'); if(set[0] >= m - n + 1) break; } return 0; 
} 

系列好文，点击链接即可跳转
上一篇：
C语言经典算法-4
最大访客数、中序式转后序式（前序式）、后序式的运算、洗扑克牌（乱数排列）、Craps赌博游戏
下一篇：
C语言经典算法-6
数字拆解、得分排行，选择、插入、气泡排序、Shell 排序法 - 改良的插入排序、Shaker 排序法 - 改良的气泡排序