资源预览内容
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
第9页 / 共22页
第10页 / 共22页
亲,该文档总共22页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章:生成排列和组合4.3 生成组合北京航空航天大学主要内容n生成组合算法 字典序(压缩序) 反射Gray序 回顾n集合的排列生成n递归原理n邻位对换法n逆序生成算法4.3 生成组合n基本概念n集合的组合 n元集合Sxn1, , x1, x0的所有组合(子 集)共有2n个。(S的幂集2S)。 注意到长度为n的二进制数也是2n个,两者 有何联系? n元集合S与长度为n的二进制数一一对应。n设计一个算法将S的所有组合列举出来 。例:01000101x1x5x7 Sx7, x6, , x1, x0的一个组合x7, x5, x1对应 10100010 一个二进制数唯一确定S一个组合。 n位二进制数与0到2n1之间十进制数一一对应。生成组合基2算法n初始: an1a1a0000nDo while an1a1a01111)求出使得aj=0的最小整数j2) 用1替换aj并用0替换每个aj1,a0。当an1a1a0111时算法结束。n算法按二进制数顺序生成,称为n元组字典序。字典序对应的组合生成n例:集合S=4,3,2,1的组合生成。00000001100102 00112,1 01003 01013,1 01103,2 01113,2,11000410014,1 10104,2 10114,2,1 11004,3 11014,3,1 11104,3,2 11114,3,2,1n上述生成组合的算法也称为压缩序。n以压缩序生成的相邻组合可能相差较大 。是否可以使得相邻的组合尽可能相似 ?算法2:反射Gray码序生成算法n特点:使得相邻的组合仅相差一个元素 (增加一个或者删除一个)。n如:n(=1,2,3)元集的组合n=1, ,x00 1n=2, ,x0, x0, x1, x100 0 1 1 1 1 0nn=3000 001 x0 011 x0 , x1 010 x1 110 x2, x1 111 x2, x1, x0 101 x2, x0 100 x2 几何表示(Gray序)n=101n=200011110n=3000001101100111 011110010n=4,是超立方体n阶Gray反射码的归纳定义1)1阶反射Gray码是 ; 2)设n1且n1反射Gray码已经构造;为了构 建n阶反射Gray码,首先以n1阶反射Gray码 所给出的顺序列出0和1的n1-元组,把0添到 每个(n1)元组的开头,然后再反序列出 n1阶反射格雷(Gray)码的全部n1元组, 并把 1加到全部n1元组的开头.n阶反射Gray码以000开始,并以100开始 结束,形成循环码。例000111 102阶Gray码00011110000 0111 13阶Gray码递归方法构造反射Gray码序生成组合以反射Gray码序生成组合算法初始:an1a1a0000nDo while an1a1a0100 1)计算(an1a1a0)= an1+a1+a0 2)如果(an1a1a0)是偶数,则改变a0(0 变1或1变0)3)否则,确定这样j,使得aj1,而对于所 有ij, ai0,然后改变aj+1.称为逐次法。例:逐次法生成反射Gray码n用逐次法生成4阶反射Gray码。0000000100110010011001110101010011001101111111101010101110011000定理4.3.1: 算法的正确性证明n逐次算法产生n阶反射Gray码。 证明:对n归纳证明。1. n=1时显然成立。2. 设n1时,结论成立。3. 当n时, 分为两种情况:(1)n阶Gray码的前2n-1个组合是由n-1阶Gray 码在开头添加0形成,除第2n-1个元组( 0100)外,该算法用于前2n-11个元组,与 用于n-1阶生成顺序一致(注:前加个0不影响 算法)。对n阶反射码第2n-1个元组(0100) ,运用逐次算法:(0100)1,则得 到(1100)正好是2n-1+1个n阶反射Gray 码。(2)考虑n阶反射Gray码后一半前后连 续的两个n元组:1an2a1a0 1bn2b1b0那么,在n-1阶反射Gray码中: an2a1a0在bn2b1b0之后,即 bn2b1b0 an2a1a0 注意到(1an2a1a0)与(1bn2b1b0)奇 偶性相反。1) 若(1an2a1a0)是偶数,那么 (an2a1a0)是奇数, (bn2b1b0) 是偶数,由归纳假设: an2a1a0由 bn2b1b0改变b0得到,因此,由算法 1an2a1a0改变a0得到1bn2b1b0。2) 若(1an2a1a0)是奇数可类似证明 。即算法用于1an2a1a0得到 1bn2b1b0 。由归纳法假设,结论成立。证毕。例:在8阶反射Gray码中, 确定10100110, 00011100的后继. (10100110)=4是偶数,改变最后一位:10100111 ; (00011100)=3是奇数,而j=3,故改变第4位数, 得到: 00010100。小结n学习了两种组合生成算法:n压缩序生成算法生成集合的所有组合,按 字典序排列。n反射Gray码序逐次生成算法。相邻的组合 仅相差一个元素。n两种算法均无需存储先前组合,具有各 自特点,可用于解决不同问题。作业n4.6 练习题 11,12,13,17,18,23
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号