常见的计数方法——枚举法
(1)字典排列法:从首位开始,按一定的顺序(比如从小到大)枚举第一位,对于每种情况再按从小到大的顺序枚举第二位,依次类推。
(2)分类枚举: 先有序分类,再有序枚举。
(3)树形图:确定起点,按照一定的顺序一一罗列,画出树状图,最后数终点个数。
总结:这三种计数方法都是枚举法中的一种,各种枚举法都需要有条理、不重复、不遗漏,一目了然。
【例1】汤姆、杰瑞和得鲁比都有蛀牙,他们一起去牙医诊所看病,医生发现他们一共有8颗蛀牙,他们三人可能分别有几颗蛀牙?
【分析】三人情况:都有蛀牙说明每个人的蛀牙数目不能为0,每人至少有1颗,一共有8颗蛀牙,所以最多的蛀牙数是6。题中有三个人的名字,所以三个人是有次序的,我们将汤姆看成是首位,杰瑞看成第二位,德鲁比看成第三位,则可以运用字典排列法枚举。
汤姆: 1 1 1 1 1 1 汤姆: 2 2 2 2 2 杰瑞: 1 2 3 4 5 6 杰瑞: 1 2 3 4 5 得鲁比:6 5 4 3 2 1 得鲁比: 5 4 3 2 1
汤姆: 3 3 3 3 汤姆: 4 4 4
杰瑞: 1 2 3 4 杰瑞: 1 2 3
得鲁比:4 3 2 1 得鲁比:3 2 1
汤姆: 5 5 汤姆: 6
杰瑞: 1 2 杰瑞: 1
得鲁比:2 1 得鲁比:1
总共有6+5+4+3+2+1=21种情况。
答案: 21
知识点拨
例题精讲
【例2】下午茶的时候,老师给同学们准备了苹果,香蕉和橘子三种水果,每种都有足够多个,昊昊想挑3个水果吃,请问:他一共有多少中选择?
【分析】分类枚举:先有序分类,再有序枚举。
一种水果:苹苹苹,香香香,橘橘橘
两种水果:苹香香,苹苹香,苹橘橘,苹苹橘,香橘橘,香香橘
三种水果:苹香橘
一共:3+6+1=10(种)
答案: 10
【例3】一个人在三个城市A、B、C中游览。他今天在这个城市,明天就必须到另一个城市。这个人从A 城出发,4天后还回到A城,那么这个人有几种旅游路线?
【分析】列出树形图如下,共有6种路线。
答案:6
第三讲排序算法(7.28)(语言提高班) 目录 训练1.明明的随机数(Noip2006普及组第1题) (1) 训练2.众数(masses.cpp) (2) 训练3.车厢重组(carry.cpp) (2) 训练4.军事机密(secret.cpp) (2) 训练5.排名 (3) 训练6.奖学金(Noip2007 普及组第1题) (3) 训练7.统计数字(Noip2007) (5) 训练8.输油管道问题 (5) 训练9.奇数单增序列 (6) 训练10.整数奇偶排序 (6) 训练11:合影效果 (7) 训练12:分数线划定 (7) 训练13:病人排队 (8) 训练14:单词排序 (9) 训练1.明明的随机数(Noip2006普及组第1题) 【问题描述】 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 【输入文件】 输入文件random.in 有2行, 第1行为1个正整数,表示所生成的随机数的个数:N 第2行有N个用空格隔开的正整数,为所产生的随机数。 【输出文件】 输出文件random.out 也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。 【输入样例】 10 20 40 32 67 40 20 89 300 400 15 【输出样例】 8 15 20 32 40 67 89 300 400
高考数学排列组合难题解决方法 1.分类计数原理(加法原理) 完成一件事,有n 类办法,在第1类办法中有1m 种不同的方法,在第2类办法中有2m 种不同的方法,…,在第n 类办法中有n m 种不同的方法,那么完成这件事共有: 12n N m m m =+++ 种不同的方法. 2.分步计数原理(乘法原理) 完成一件事,需要分成n 个步骤,做第1步有1m 种不同的方法,做第2步有2m 种不同的方法,…,做第n 步有n m 种不同的方法,那么完成这件事共有: 12n N m m m =??? 种不同的方法. 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件. 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有13C 然后排首位共有1 4C 最后排其它位置共有34A 由分步计数原理得113 4 34288C C A = C 14A 34C 13 位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件,往往是考虑一个约束条件的同时还要兼顾其它条件
本文由我司收集整编,推荐下载,如有疑问,请与我司联系实现全排列的两种算法:字典序列法以及递归算法(java)2014/10/19 0 一.全排列之字典序列法 /** * 这是一个实现全排列的字典序列算法,可适用于有数据重复以及无数据重复 的字符串----注意:字符要先从小到大排序* 算法描述:例如:645321 的下一个数: * 1.左边的数要大于右边:从最右- 最左,遍历查询是否有邻近左边的数小于右边的 数,有就停止遍历,本例:4 5. * 2.把找到的左边那个数,与其右边的所有数比较,从 右向左逐一比较,找到第一个比它大的,然后交换。本例:比4 大的右边第一个数 是5. * 3.将两个数对换,则字符可分为65,4321,把4321 从小到大排序:1234* 4. 下一个字符序列是:651234. span > * * @param ary //要排列的数组*/public static void dictorySerial(int[] ary1) {Arrays.sort(ary1);System.out.println( 1: + Arrays.toString(ary1));int i = 2;while (true) {int j;for (j = ary1.length - 1; j j--) {if (ary1[j - 1] ary1[j]) {for (int k = ary1.length - 1; k j - 1; k--) {if (ary1[k] ary1[j - 1]) {int temp = ary1[j - 1];ary1[j - 1] = ary1[k];ary1[k] = temp;break;}}int[] ary2 = new int[ary1.length - j];System.arraycopy(ary1, j, ary2, 0, ary2.length);Arrays.sort(ary2);System.arraycopy(ary2, 0, ary1, j, ary2.length);System.out.println((i++) + : + Arrays.toString(ary1));break;}}if (j == 0) {break;}}}二.全排列之递归算法 /** * 这是关于java 全排列的递归算法,本算法不适用于字符串中有重复数字。- --注意:交换两个数后,后面要在交换过来,不要影响要排列的字符序列(*)* 算法过程:如:123 的全排列:* 1.可以看成:以1 开头的全排列,以2 开头的全 排列,以3 开头的全排列/span 表示成1(23),2(13),3(12)的全排列,即23 全排列,13 全排列,12 全排列. span > span > span > span > span > span > span > span > span > span > span > span > span >public static void recurrence(int[] ary2, int start, int end) {if (start == end) {System.out.println((++i) + : + Arrays.toString(ary2));} else {for (int i = start; i = end; i++) {swap(ary2, start, i);recurrence(ary2, start + 1, end);swap(ary2, start, i);System.out.println(Arrays.toString(ary2));}}}public static void swap(int[] ary2, int start,
小学生查字典口诀 学查字典并不难,偏旁部首看端详。 没有部首查起笔,形声字儿查形旁; 头底两层是部首,要让字头当偏旁; 左右两边是部首,取左去右有保障; 内心外壳是部首,舍去里边查外框; 整个字儿是部首,此字本身是偏旁; 一字头上生“二角”,取其下底把“角”砍; 下底如果不成部,左上角当此字旁; 有些生字较特殊,顶天立地当偏旁; 多查多想抓规律,相同部首不能忘。 查字典常用的三种方法是: 音序查字法、部首查字法和数笔画查字法。 ?如果很容易确定部首,但不确定读音就可以用部首查字法;?如果知道读音,但不会写这个字,就用音序查字法; ?如果是独体字就用数笔画查字法。
字、词典是无声的老师,这位老师随时会帮你解决疑难,扫除 学习中的“拦路虎”。你会只花少量的时间,非常方便地得到 较多、较全面、较准确的知识。熟练查字、词典,首先要学会 检字。下边以《新华字典》为例介绍这几种查字法。 一、音序查字法 音序检字法是按字音查字词的一种方法。很多字典或词典是按汉语拼音字母的顺序编排的。根据一个字的汉语拼音第一个字母,就可以在“汉语拼音音节表”中找到这个字的拼音音节在正文中的页码,再按照这个字的声调到那一页中去找。凡是要查只知道读音而不知道写法或意义的字,都可以用这种方法,但必须熟悉汉语拼音字母顺序和汉语拼音音节。 运用条件: ①字音要读得正确; ②准确无误地了解这个字的声母、韵母; ③掌握字母的写法。 知道了这个字的读音,不知道它的写法,或不知道它的意思, 就必须运用音序查字法查字。 查字步骤: ①确定音部。按要查字的读音确定音节的第一个字母——音部。
②查音节索引。在《汉语拼音音节索引》中所确定的音部栏里,找出要查字的音节,并看准该音节后面所标的正文页码。 ③翻阅正文。按页码翻阅正文,找出要查的字。 在学习中遇到不理解的字或不会写的字,只要能读准字音,就可以运用音序检字法去查检。 下面的歌诀,可以帮助同们掌握这种检字法: 音序检字须认真,读准字音很要紧。 打头字母定音部,再找音节看《索引》; 按照例字找同音,对照页码翻正文; 根据声调找汉字,字形字义记在心。 部首检字法:部首检字法属于按形查字中的一种方法。它是根据汉字的部首去查检的。凡字典正文中的单字是按部首归类进行排列的,都可以运用部首检字。 部首检字的基本步骤? ⑴确定出部首。先对所要查的字确定出查什么部。 ⑵查《部首目录》。在《部首目录》中查出该部首在《检字表》中的页码。 ⑶查《检字表》。按照页码在《检字表》中这个字的余画(即除去部首还余几画)里查出这个字在字典正文中的页码。
第2次课枚举法中的字典排列 小热身 体会一下,“分给两个人”和“分成两堆”有什么区别呢? (1)把5个苹果全部分给两个人,共有多少种不同的分法? (2)把5个苹果分成两堆,共有多少种不同的分法? 例题1:卡莉娅、墨莫、小高三个人去游乐园玩,三人在藏宝屋中一共发现了4件宝物,三人找到的宝物数量共有多少种不同的可能?(可能有人没有发现宝物) 练习1:老师准备了6个笔记本奖励萱萱、小高、墨莫三人,每人至少得到1本笔记本,请问:老师有多少种不同的奖励方法? 例题2:老师要求每个同学写出3个自然数,并且要求这3个数的和是8。如果两个同学写出的3个自然数相同,只是顺序不一样,则算是同一种写法。试问:同学们最多能得出多少种不同的写法? 练习2:三个大于0的整数之和(数与数可以相同)等于10,共有多少组这样的三个数?
例题3:如下图所示,有7个按键,上面分别写着1、2、3、4、5、6、7这七个数字。请问: (1)从中选出2个按键,使它们上面的数字的差等于2,一共有多少种选法? (2)从中选出2个按键,使它们上面的数字的和大于9,一共有多少种选法? 练习3:有一次,著名的探险家大米得到一个宝箱,但是宝箱有密码锁,密码锁下面有一行小字,密码是和大于11的两个数,而且这两个数不能相同,不用考虑数的先后顺序,你知道密码共有多少种可能吗? 例题4:如图,数一数图中包含星星的长方形(包括正方形)有多少个? 练习4:如图,数一数图中包含星星的正方形有多少个?
作业: 1、有4支完全相同的铅笔要分给3位同学,每位同学至少分1支,共有多少种不同的分法? 2、有面值分别为1元、10元和50元的纸币若干,每种面值的纸币张数都大于 3、如果从中任意取3张,那么能组成的钱数共有多少种? 3、从1、2、3、 4、 5、6这六个数字中选出2个数字,使它们的数字的差等于2,一共有多少种选法? 4、数一数,下图包含星星的长方形(包括正方形)有多少个? 5、在下图中,一共能找出多少个含“☆”的三角形。
行测答题技巧:排列组合问题之捆绑法,插空法和插板法 “相邻问题”捆绑法,即在解决对于某几个元素要求相邻的问题时,先将其“捆绑”后整体考虑,也就是将相邻元素视作“一个”大元素进行排序,然后再考虑大元素内部各元素间排列顺序的解题策略。 例1.若有A、B、C、D、E五个人排队,要求A和B两个人必须站在相邻位置,则有多少排队方法? 【解析】:题目要求A和B两个人必须排在一起,首先将A和B两个人“捆绑”,视其为“一个人”,也即对“A,B”、C、D、E“四个人”进行排列,有 种排法。又因为捆绑在一起的A、B两人也要排序,有种排法。根据分步 乘法原理,总的排法有种。 例2.有8本不同的书,其中数学书3本,外语书2本,其它学科书3本。若将这些书排成一列放在书架上,让数学书排在一起,外语书也恰好排在一起的排法共有多少种? 【解析】:把3本数学书“捆绑”在一起看成一本大书,2本外语书也“捆绑”在一起看成一本大书,与其它3本书一起看作5个元素,共有种排法;又3本数学书有种排法,2本外语书有种排法;根据分步乘法原理共有排法种。 【王永恒提示】:运用捆绑法解决排列组合问题时,一定要注意“捆绑”起来的大元素内部的顺序问题。解题过程是“先捆绑,再排列”。 “不邻问题”插空法,即在解决对于某几个元素要求不相邻的问题时,先将其它元素排好,再将指定的不相邻的元素插入已排好元素的间隙或两端位置,从而将问题解决的策略。 例3.若有A、B、C、D、E五个人排队,要求A和B两个人必须不站在一起,则有多少排队方法?
【解析】:题目要求A和B两个人必须隔开。首先将C、D、E三个人排列,有种排法;若排成D C E,则D、C、E“中间”和“两端”共有四个空位置,也即是:︺ D ︺ C ︺ E ︺,此时可将A、B两人插到四个空位置中的任意两个位置,有种插法。由乘法原理,共有排队方法: 。 例4.在一张节目单中原有6个节目,若保持这些节目相对顺序不变,再添加进去3个节目,则所有不同的添加方法共有多少种? 【解析】:直接解答较为麻烦,可根据插空法去解题,故可先用一个节目去插7个空位(原来的6个节目排好后,中间和两端共有7个空位),有种方法;再用另一个节目去插8个空位,有种方法;用最后一个节目去插9个空位,有方法,由乘法原理得:所有不同的添加方法为=504种。 例4.一条马路上有编号为1、2、……、9的九盏路灯,为了节约用电,可以把其中的三盏关掉,但不能同时关掉相邻的两盏或三盏,则所有不同的关灯方法有多少种? 【解析】:若直接解答须分类讨论,情况较复杂。故可把六盏亮着的灯看作六个元素,然后用不亮的三盏灯去插7个空位,共有种方法(请您想想为什么不是),因此所有不同的关灯方法有种。 【王永恒提示】:运用插空法解决排列组合问题时,一定要注意插空位置包括先排好元素“中间空位”和“两端空位”。解题过程是“先排列,再插空”。 练习:一张节目表上原有3个节目,如果保持这3个节目的相对顺序不变,再添加进去2个新节目,有多少种安排方法?(国考2008-57) A.20 B.12 C.6 D.4
算法分析与设计实验报告 第 2 次实验
这次的实验和上一次的字典序问题有一些相似,主要不同的地方在于要写出下 附录:完整代码 #include