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

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

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

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

(1) for i 1 to n-1 2) for j=i+1 to n 3】 iE(A[i打>A[j1) (4) exchange A[i]and A[il How many times is the comparison Ali]Alj]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. Us. IS:l

critical operation

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

我们究竟要数什么？

操作计数与子集计数 相同的情况，不同的抽象： 在排序的例子里，对任意含两个元素的子 集，我们需要做一次比较 则比较次数等于个元素的集合所有的两 个元素的子集的个数。 ()= 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,] (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? 7=U Tl= U=∑ISl=∑=mn i-l 乘法原则是否是必须明确给出的呢？

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

(1) for i =1 to n-1 (2) minval A[i] (3) minindex i (4) for j=i to n (5) if (A[j]minval) (6) minval A[j] (7) minindex j (8) exchange A[i]and A[minindex] (9) bigjump =0 (10) for i 2 to n (11) if(A[i]>2*A[i-1]) (12) bigjump bigjump 1 这个算法需要执行多少次比较操作？

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

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

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

从数1ist到数函数 How many functions are there from a two-element set to a three-element set? How many functions are there from a three-element set to a two-element set? How many functions are there from a m-element set to a n-element set? T(m,n)=n*T(m-1,n) T(1,n)=n T(m,n)=nm

从数list到数函数 How many functions are there from a two-element set to a three-element set? How many functions are there from a three-element set to a two-element set? How many functions are there from a m-element set to a n-element set? T(m,n)=n*T(m-1,n) … T(1,n)=n T(m,n)=n m

问题4；这与数函数有什么关系？ 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 each>I and each choice of the first j-I elements of a list in S.there are i choices of elements in position j of those lists, then there are ii.=is lists in S. 用B中元素构造长度为3的ist。 每个ist其实就是一个A到T的函数！ 这个ist有多少种可能性？ A集合 B集合 ·如果A=m,B=n呢？

A集合 B集合 • 用B中元素构造长度为3的list。 • 每个list其实就是一个A到T的函数！ • 这个list有多少种可能性？ • 如果|A|=m,|B|=n呢？