作业中的问题1做作业不抄题2不按照布置题的次序答题3不.ppt

设集合S={1, 2, 3, …, n}，于是S中的元素存 在一种自然顺序1 2… n 。如果A，B是S的两个r-组合(子集)，且在集合A∪B－A∩B中(即：在其中一个集合中而不在两个集合中)的最小元素属于A，则称组合A以字典序先于B。 例:集合{1,2,3,4}的两个组合A={1,2,3};B={2,3,4}, 它们中不同的元素是1和4,其中1小,而且在A中,所以A以字典序先于B。即拿不同的元素比较次序。 组合中的元素本身是无序的，但为了方便 讨论，我们规定{1, 2, …, n}中的任一r-组合均按字典序书写成如下“单词”的形式： a1a2…ar 其中a1a2…ar 特别是书写成 “单词”形式中不允许有相同的元素重复出现。 回到前个例子：从{1,2,3,4}中选出2-组合中 2 3 的前后组合是：1 4和2 4。下面说的组合都有序. 定理4.4.1设a1a2…ar 是{1, 2, …, n}的一个r-组合。 在字典 顺序中，第一个r-组合是123…r；最后一个r-组合是 (n-r+1)(n-r+2) …n 。如果a1a2…ar ≠ (n-r+1)(n-r+2) …n ，则a1a2…ar 的直接后继r-组合是： a1a2…ak－1 (ak+1)(ak+2)… (ak+r-k+1) 其中，k是满足akn且ak＋1不在a1a2…ar中的最大整数, 即从ak开始改变字符，按加1方式。 根据上述定理，我们可以描述生成{1, 2, …, n} 的字典序r-组合的算法如下： 1. 输出正整数n，r，并且r ≤ n； 2. 构造{1, 2, …, n}的字典序的第一个r-组合a1a2…ar ＝1 2…r，并输出； 3. 当a1a2…ar ≠ (n-r+1)(n- r+2)…n时，做 ⅰ) 确定最大的整数k，使得ak＋1 ≤ n且ak＋1 不在a1a2…ar 之中； ⅱ) 构造r-组合 a1a2…ak－1 (ak+1)(ak+2)… (ak+r-k+1) 作为新的r-组合a1a2…ar ； ⅲ) 输出r-组合a1a2…ar ； 这里有一个用C++编写的求r-组合的程序，提供给大家参考： 产生字典序r-组合的程序 此算法以升序列出{1,2,…8}的所有4-组合。 以下用C++程序编写。 # include fstream. h # include iomanip. h const n=8 main c Int a[n]={1,2,…8} Int h[4]={0} Int s,t,u,v Ofstream myf (“c://out.txt); for (s = 0; s＜＝n - 4;s++); { for (t=s+1; t ＜＝n – 3;t++) for (u=t+1; u ＜＝n – 2 ;u++) for (v=u+1; v ＜＝n – 1 ;v++) { h[0] = a[s] ;h[1] = a[t]; h[2] = a[u]; h[3] = a[v] for (int q =0 ;q ＜4;q++) myf h[q]“ “; myfend;}} 结束 产生字典序r-组合的程序 此算法以升序列出{1,2,…,n}的所有r-组合。 输入：r，n 输出：以升序列出{1,2,…,n}的所有r组合。 1.procedure combination(r,n) 2. for i:=1 to r do 3. si=i 4. print s1,…,sr //打印第一个r组合 5. for i:=2 to c(n, r) do 6. begin 7. m:=r 8. max_va