做盗版视频网站违法吗,网站uv pv,唐山网站建设推广,最近发生的重大新闻文章目录 其他经典例题跳转链接26.约瑟夫问题#xff08;Josephus Problem#xff09;27.排列组合28.格雷码#xff08;Gray Code#xff09;29.产生可能的集合30.m元素集合的n个元素子集 其他经典例题跳转链接
C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. … 文章目录 其他经典例题跳转链接26.约瑟夫问题Josephus Problem27.排列组合28.格雷码Gray Code29.产生可能的集合30.m元素集合的n个元素子集 其他经典例题跳转链接
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(2N1) 魔方阵
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 (pos1) % 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((i1) % 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[N1], 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, i1); // 还原 for(k i; k j; k) num[k] num[k1]; 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年代提出的用来在使用PCMPusle 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[i1]); } 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所对应的数字所产生的就是一个集合例如
InputSet000{}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 e1}再依序加入后续的元素。
例如有四个元素而当产生{1 2 3 4}集合时则下一个集合就是{1 2 31}也就是{1 2 4}由于最后一个元素还是4所以下一个集合就是{1 21}也就是{1 3}接下来再加入后续元素4也就是{1 3 4}由于又遇到元素4所以下一个集合是{1 31}也就是{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, i1); 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[position1] 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 排序法 - 改良的气泡排序
