南京大学：《计算机问题求解》课程教学资源（课件讲稿）组合与计数

计算机问题求解一论题2-4 -组合与计数 2016年03月17日

计算机问题求解 – 论题2-4 - 组合与计数 2016年03月17日

问题1： 计数在算法分析中为什么很重要？

(1) for i 1 to n-1 (2】 for j i+1 to n (3】 iE(A[i]>A[j]】 (4) exchange A[i]and A[j] How many times is the comparison A[i]A[j]made in Line 3? critical operation Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint finite sets is the sum of the sizes of the sets. =∑1S

critical operation

问题2： 你如何理解这里所体现 的“抽象”过程？ 我们究竟要数什么？

我们究竟要数什么？

操作计数与子集计数 相同的情况，不同的抽象： 在排序的例子里，对任意含两个元素的子 集，我们需要做一次比较 则比较次数等于个元素的集合所有的两 个元素的子集的个数。 n(n-1) 2

操作计数 与 子集计数 相同的情况，不同的抽象： 在排序的例子里，对任意含两个元素的子 集，我们需要做一次比较 则比较次数等于n个元素的集合所有的两 个元素的子集的个数

你能再解释一下抽象的过程吗？ (1 for i 1 to r (2) for j 1 to m (3) S=0 (4) for k 1 to n (5) SS A[i,k]B[k,j] (6] c[i,j]S How many multiplications (expressed in terms of r,m,and n)does this pseudocode carry out in total among all the iterations of Line 5? T =USj. =∑S=∑n=mn j- i 乘法原则是否是必须明确给出的呢？

你能再解释一下抽象的过程吗？ 乘法原则是否是必须明确给出的呢？

(1) for i 1 to n-1 这个 (2) minval A[i] (3) minindex i (4) for j=ito n (5) if (A[j]2*A[i-1]) (12) bigjump bigjump 1 easily solvable pieces.If we can decompose the problem into smaller pieces and so the smaller pieces,then we may be able to ethr add or multiply soitosmaller problemsinrder to solve the larger problem.n this

这个 算法 需要 执行 多少 次比 较操 作？

乘法原则的两个版本不一样吗？ Principle 1.3 (Product Principle) The size of a union of m disjoint sets, each of size n is mn. 其实，我们还有 问题3： Principle 1.4 (Product Principle,Version 2) 一个乘法原理： If a set S of lists of length m has the properties that 做一件事情有m 通俗地 1.there are i different first elements of lists in S.and 个步骤，如果完 说说1.4 2. for each j>I and each choice of the first j-1eleme成第步的方法有 是什么 list inS,there are i choices of elements in positionj,种，那么完成这 lists, 意思？ 件事情的方法有 then there are ii…ia=Π，ig lists in S. *i2*.*im种方 法

乘法原则的两个版本不一样吗？ 其实，我们还有 一个乘法原理： 做一件事情有m 个步骤，如果完 成第j步的方法有 i j种，那么完成这 件事情的方法有 i1 *i2 *……*im种方 法

从数1ist到数函数 Principle 1.4 (Product Principle,Version 2) If a set S of lists of length m has the properties that 1.there are i different first elements of lists in S,and 2.for eachj I and each choice of the first j-1 elements of a list in S,there are i;choices of elements in position j of those lists, then there are ii2…im=Π-ig lists in S. 问题4：这与数函数有什么关系？

从数list到数函数

问题6： (1) trianglecount =0 你能解释这个原 (2) for i=1 to n 理的应用吗？ (3) for j=i+1 to n (4) for k j+1 to n (5) if points i,j,and k are not collinear (6) trianglecount trianglecount 1 Among all iterations of line 5 of the pseudocode,what is the total number of times this line checks three points to see if they are collinear? Principle 1.5 (Bijection Principle) Two sets have the same size if and only if there is a one-to-one function from one set onto the other