离散数学 课件 chapter 2 组合数学与数论初步.pptx

2 排列组合与数论初步 2.0 引例 例1 从烟台出发，到北京、上海、西安、杭州、拉萨等5个城市旅游，最后回到烟台。已知所有城市间的单向路线的费用，旅游费用可以按路线的费用累加得到，那么按照怎样的顺序游玩这些城市，费用最省？ 例2 甲数是36，甲、乙两数的最小公倍数是288，最大公约数是4，乙数应该是多少？ 内容2.1 基本计数原则2.2 排列2.3 组合2.4 鸽笼原理2.5 素数2.6 最大公约数与最小公倍数 2.1 基本计数原则 分析计算机算法的时间复杂性和空间复杂性时，需要对计算机的基本运行次数和占用的存储空间进行计数，这是计数的基本运用。基本的计数原则有加法原则和乘法原则。 2.1 计数原则——加法原则实现一个任务，有 种不同的方式可以选择，每种方式都可以独立完成任务，在第 种方式中，有 种具体的实现方式。则实现这个任务的方式有： 学生请老师推荐一本程序设计的入门教材，该老师熟悉C、C++、Java三门编程语言，已知这三门语言的入门教材分别有4、5和6本。那么该教师可以有4+5+6=15种选择方式。 2.1 计数原则——乘法原则实现一个任务，有 个步骤，在第 个步骤中，有 种具体的实现方式。则实现这个任务的方式有： 已知ASCII码（American Standard Code for Information Interchange）由7位二进制数组成，请问这种表示形式可以表示多少个不同的ASCII符号？ ? 2.1 计数原则——乘法原则求小于10000的正整数中含1的数字的个数。 解：将不足4位的正整数用4位数表示，如1表示为0001。因此，不包含1的正整数数量为：?因此，包含1的正整数数量为：9999-6560=3439。 2.2 排列 排列组合问题是计算机科学中的典型问题，在实际生产中也有着广泛的应用。 设 A={a1,a2,…,an}是包含 n 个不同元素的集合，从集合 A 中任取 r 个元素排成一列，称为从集合 A 中取 r 个数的一个排列。A={a,b,c,d}，r=2，得到的全体排列如下：ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc??? 2.2 排列计算20000-69999的偶数中，由不同数字组成的5位数的个数。 解：最高位为2，3，4，5，6，而偶数最低位是0,2,4,6,8。因此分为以下两种情况： （1）最高位为2，4，6，最低位只能是除了最高位外的4位选择，根据乘法原则，有 （2）最高位为3，5时，最低位可以是0,2,4,6,8中的任意1位，根据乘法原则，有?? 根据加法原则，总个数为4032+3360=7392。 2.2 排列A单位有7人，B单位有3人，集体合影。（1）B单位3人在一起，（2）A单位人在两端，且B单位3人不能相邻。?? 2.2 排列——圆周排列从包含n 个不同元素的集合A 中任取 r 个元素排列一个圆周，称为圆周排列，简称圆排列。abcdabcdbcdacdabdabc?? 2.2 排列——圆周排列5对夫妇出席一次宴会，围一个圆桌坐下。计算有几种不同的方案。如果要求夫妻相邻，又有多少种方案？?解：（1）5对夫妇围一个圆桌，相当于10人的圆周排列，其方案数为：（2）如果要求夫妻相邻，相当于5对人的圆桌排列，其方案数为：? 2.3 组合从{1,2,3,…,n}中选择3个数字，如果不考虑取出数字的先后顺序，有多少种取法？解：3个不同数字的排列有3!=6种，因此，上述取法有?从{1,2,3,…,n}中选择 r 个数字，如果不考虑取出数字的先后顺序，有多少种取法？? 2.3 组合 2.3 组合 2.3 组合从1到300中任取3个数字使其和能被3整除，有多少种方法？ 解：将1到300根据对3取余的结果，将其分为以下3个集合：A={1,4,7,…,298}B={2,5,8,…,299}C={0,3,6,…,300}取3个数字，使其和被3整除，有两种策略：（1）从上述任一集合中取3个元素：（2）从上述三个集合中取1个：??? 2.4 鸽笼原理将 只鸽子放进 个笼子，至少有一个笼子里至少放着2只鸽子。n+1 只鸽子1 只鸽子n只鸽子平均到n个笼子 2.4 鸽笼原理从1到100中任意选51个数，那么其中一定存在两个数的和是101。 1，2，3，4，5，6，7，8，9，10，11，12，13，…，98，99，100解：1到100这100个数中，存在50对和为101的数字，如下： 从中任选51个，则至少可以选择其中的一对，因此，一定存在两个数的和是101。 2.4 鸽笼原