离散数学：8-2 组合分析初步

复习思考题17设T是各边带权均为1的n阶带权图的一棵最小生成树，则W(T)=_______。

对于高度为h的4叉正则树：至多有_______片树叶；至少有_______片树叶。m叉正则树中,若有s个分支点,则共有_____结点.设T是n(n≥3)阶无向树，则T是二部图。()设T是n(n≥3)阶无向树，则T是欧拉图。()设T*是n(n≥3)阶无向树的对偶图，T*是哈密顿图

()第8章组合分析初步

8.1加法法则和乘法法则8.2基本排列组合的计数方法8.3递推方程的求解与应用多重集的组合定理8.7设S={a1,a2,…,

ak},则S的r组合数为推论1

设S={n1a1,n2a2,…,nkak},且对i=1,2,…,k有nir，则S的r组合数为

S的

r组合形式为{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi为非负整数.这个不定方程的非负整数解的个数即为S的r组合数。r个球扔到k个盒子里多重集的组合推论2

设S={a1,a2,…,

ak}，rk，则S中每个元素至少取一个的r组合数为

1…101…101…10……01…1x1个1x2个1x3个1xk个1实例9一个学生要在相继的5天内安排15个小时的学习时间，问有多少种方法？若要求每天至少学习1小时，又有多少种方法？解：设这5天记为a1,a2,…,

a5

则第一种安排相当于多重集

S={a1,a2,…,

a5}的15组合数问题，

r=15,k=5第二种安排可由推论2得出，r=15,k=5实例10有3类明信片，分别是3、4、5张，把它们全部送给5个朋友(允许有的人得到0张)，问有多少种不同的方式？解：考虑第1类明信片，5个朋友所得到的明信片数分别为x1

,x2,…,x5

,其和为3，得到不定方程

该方程的非负整数解的个数是将第1类明信片送5个朋友的方法数，结果为：类似地处理后两种明信片，所以，所求方式共有：N1N2N3种。x1+x2+…+xk=3

xi

N,i=1,2,…,5

实例11已知：x0,y1,z2，求方程

x+y+z=10

的整数解个数。解：根据定理8.7及推论2，相当于k=3、r=10在x0,y1,z2下的r-组合问题

r’r-1-2,k=3,代入定理8.7得

1…101…101…1x个1

y个1

z个1实例12设S是具有3个元素的集合，求在S中可定义不同的对称且反对称的二元关系的个数解：设S={1,2,3},在S定义的对称且反对称二元关系中，意味着其关系矩阵中除主对角线外均为0，而主对角线上有3个元素，每一位均可为0或1，所以共23=8种不同的对称且反对称关系。实例17设A、B分别为m元集和n元集，m、n为正整数，则从A到B有多少个函数？其中，(1)多少个单射的函数？(2)多少个双射的函数？解：从A到B的函数构成集合BA，|BA|=nm意味m<n,

单射的函数的个数为从

n个元素中选取m个不同元素的方式，为Pnm.(2)意味m=n,

双射的函数的个数=n!=m!……nmn8.3递推方程的求解与应用递推方程的求解与组合计数有着密切的关系，在计算机科学技术的领域有着重要的应用。递归算法是计算机中经常使用的算法，如二分检索、二分归并排序、快速排序、Hanoi塔的移动算法等分析递归算法的主要技术就是求解递推方程。递推方程的定义定义设序列a0,a1,…,an,…，简记为{an},一个把an与某些ai(i<n)联系起来的等式叫作关于序列{an}的递推方程。当给定递推方程和适当的初值就唯一确定了序列.

例如，

Fibonacci数列：1，1，2，3，5，8，…，记作{fn}.递推方程

fn

=fn1+fn2

初值f0

=1，f1=1

阶乘计算数列：1，2，6，24，5！，…,记作{F(n)}

递推方程

F(n)=nF(n1)

初值

F(1)=1递推方程举例1用递推的角度来考察n阶完全图Kn的边数en的问题从Kn-1到Kn新增加一个顶点需要增加n-1条边，分别连到Kn-1的各个顶点。边数递推关系为：en=en-1+(n-1)(n≥1),e1=0en=en-2+(n-2)+(n-1)

=en-3+(n-3)+(n-2)+(n-1)=……=e2+2+3+…+(n-1)=

e1+1+2+…+(n-1)=(n2-n)/2迭代过程

递推方程举例1验证n阶完全图Kn的边数en=(n2-n)/2

(n≥1)用归纳法证明：当n=1时，代入上式：e1=(12-1)/2=0(平凡图)设当n=k时上式成立，即ek=(k2-k)/2则当n=k+1时，由递推关系得

ek+1=ek+k

=(k2-k)/2

+k=(k2+k)/2

=[(k2+2k+1)-(k+1)]/2

=[(k+1)2-(k+1)]/2

证明过程

ek=ek-1+(k-1)递推方程举例2----Hanoi塔下图中有A、B、C三个柱子，在A柱子上放着n个大小不同的圆盘，其中小圆盘放在大圆盘的上边，从A柱将这些圆盘移到C柱上去。这里把一个圆盘从一个柱子移到另一个柱子称作1次移动，在移动和放置时允许使用B柱，但不允许大圆盘放到小的上面。问把所有的圆盘从A移动C，最少需要移动多少次？ABC递推方程举例2——Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。ABC移动第1次移动第2次递推方程举例2----Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。ABC移动第3次移动第4次递推方程举例2----Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。ABC移动第5次移动第6次递推方程举例2----Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。ABC移动第7次递推方程举例2----Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。ABCT(n-1)T(n-1)1Hanoi(A,C,n)算法if(n=1)

move(A,C);else

Hanoi(A,B,n-1);

move(A,C);Hanoi(B,C,n-1);

递推方程举例2----Hanoi塔递推算法(1)用同样的算法把上面的n-1个盘子从A柱移到B柱(2)用1次移动把下面最大的盘子移到C柱(3)用同样的算法把B柱上的n-1个盘子移到C柱。设算法移动n个盘子的总次数为T(n)，得递推方程T(n)=2T(n-1)+1且T(1)=1，(初始条件)ABCT(n-1)T(n-1)1递推方程举例2----Hanoi塔由递推方程得出T(n)直接与n的关系：T(n)=2T(n-1)+1，T(1)=1，

=2[2T(n-2)+1]+1

=22[2T(n-3)+1]+2+1

=23[2T(n-4)+1]+22+2+1=……=2n-1T(1)+2n-2+2n-3+…+2+1

=2n-1+2n-2+2n-3+…+2+1=2n

-1迭代过程

递推方程举例2----Hanoi塔验证结果T(n)=2n

-1用归纳法证明：当n=1时，代入上式：T(1)=21-1=1(正确)设当n=k时上式成立，即T(k)=2k

-1则当n=k+1时，由递推关系得T(k+1)=2T(k)+1=2(2k–1)+1=2k+1–2+1=2k+1–1(正确)证明过程

T(k)=2T(k-1)+1Hanoi塔问题据说古代的僧侣按此方法移动64个金盘子，认为当64个金盘子全部移完后，世界末日就到了。若每秒移动1次，则移动64个盘子需要：264–1=18446744073709551615(秒)

超过5000亿年！其算法的T(n)=2n

–1是n的指数函数，其时间复杂度随n的增加呈指数爆炸性增长。因此，在处理实际问题时，通常不能选择指数时间的算法，为了对算法的效率做出估计，求解递推方程是经常使用的方法。递推方程的迭代求解方法迭代过程从原始递推方程开始，推导直到表达式中没有函数项为止验证过程为保证结果的正确性，需要代入原来递推方程进行验证迭代求解方法的适用范围一般适用于依赖关系比较简单的递推方程用递推方程分析算法的效率分而治之算法它把一个问题分成几个同类型的较小的问题，这些小问题再各自被分为同样的更小的问题，如此继续，直到问题变得如此之小以致于可以很容易地解决它们；然后重新整合所得到的这些小问题的解，从而得到原问题的解。二分归并排序二分归并排序的主要思想将被排序的数组划分成相等的两个子数组，然后递归使用同样的算法分别对两个子数组最后将两个排好序的子数组归并成一个数组。二分归并排序算法Mergesort(A,p,r)

//对数组A的下标p到r之间的数排序

if(p<r)

q=[(p+r)/2];

Mergesort(A,p,q);

Mergesort(A,q+1,r);

Merge(A,p,q,r);

//把排好序的数组A(p,q)与A(q+1,r)归并二分归并排序算法[19,14,11,18,30,17,6,20][19,14,11,18],[30,17,6,20][19,14],[11,18],[30,17],[6,20][19],[14],[11],[18],[30],[17],[6],[20][14,19],[11,18],[17,30],[6,20][11,14,18,19],[6,17,20,30][6,11,14,17,18,19,20,30]二分归并排序算法设要比较的数组元素个数为n=2k，W(n)表示该算法在最坏情况下所做的比较次数，将n个数组元素分为两个子数组A和B(大小相等)，排序数组A或B的工作量分别为W(n/2)。因为数组A和B总共有n个元素，归并它们至多需要n-1次比较，因此，对n个数进行二分归并排序最坏情况下的比较次数満足如下递推方程：W(n)=2W(n/2)+n-1,n=2kW(1)=0二分归并排序算法迭代求解过程W(n)=2W(n/2)+n–1,n=2k,W(1)=0=2W(2k-1)+2k–

1

=2[2W(2k-2)+2k-1–

1]+2k-1=22W(2k-2)+2k–2+2k–1=22[2W(2k-3)+2k-2–1]+2k–2+2k–1=23W(2k-3)+2k–22+2k–2+2k–1=……=2kW(2k-k)+k2k–(2k-1+2k-2+…+2+1)=k2k–2k+1=nlog2n–n+1二分归并排序算法的算法复杂度为O(nlog2n)二分归并排序算法结果验证过程

W(n)=nlog2n–n+1用归纳法证明：当n=1时，代入上式：W(1)=1log21–1+1=0(正确)设当n=k时上式成立，即W(k)=klog2k–k+1则当n=2k时，由递推关系得

W(2k)=

2W(k)+2k–1

=2[klog2k–k+1]+2k–1

=2klog2k

–2k+2

+2k–1=2k(log2k+1)–2k+1=2klog22k–2k+1(正确)W(n)=2W(n/2)+n–1递推方程的实例——算法分析哪种排序算法的时间复杂度比较低？插入排序算法

快速排序算法归并排序算法

插入排序算法Insertsort(A,n)

{forj=2tondo

{x=A[j]

i=j-1

whilei>0andA[i]>xdo

{A[i+1]=A[i]

i=i-1

}

A[i+1]=x

}

}插入排序算法在最坏情况的时间复杂度W(n)

W(n)=W(n

1)+n

1

W(1)=0易得W(n)=0+1+…+(n-1)

=n(n-1)/2

=O(n2)快速排序算法Quicksort(A,p,r){ifp<rq=Partition(A,p,r)A[p]A[q]Quicksort(A,p,q-1)Quicksort(A,q+1,r)

}基本思想通过一趟排序将待排序数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的都要小然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到数据排序。

5

8163427

521634

87

521

4

3

687

321

4568

7

1

23

4567

8快速排序算法Quicksort(A,p,r)

{ifp<rq=Partition(A,p,r)

A[p]A[q]Quicksort(A,p,q-1)Quicksort(A,q+1,r)

}设n个数的平均比较次数是T(n),若首元素在第k个位置划分后的子问题规模分别为k-1和n-k,平均比较次数分别是T(k-1)和T(n-k),而划分过程需要的比较次数是O(n),所以总的比较次数