3 排列组合的综合应用 学员版.docx

3 排列组合的综合应用 学员版.docx

《3 排列组合的综合应用 学员版.docx》由会员分享，可在线阅读，更多相关《3 排列组合的综合应用 学员版.docx（9页珍藏版）》请在冰点文库上搜索。

3排列组合的综合应用学员版

第三讲排练组合及简单统筹

第一部分排列组合的综合应用

排列组合是数学中风格独特的一部分内容.它具有广泛的实际应用.　　排列组合的综合应用具有一定难度.突破难点的关键：

首先必须准确、透彻的理解加法原理、乘法原理；即排列组合的基石.其次注意两点：

1对问题的分析、考虑是否能归纳为排列、组合问题？

若能，再判断是属于排列问题还是组合问题？

②对题目所给的条件限制要作仔细推敲认真分析.有时利用图示法，可使问题简化便于正确理解与把握.

例1从5幅国画，3幅油画，2幅水彩画中选取两幅不同类型的画布置教室，问有几种选法？

例2一学生把一个一元硬币连续掷三次，试列出各种可能的排列.

例3用0～9这十个数字可组成多少个无重复数字的四位数.

例4从右图中11个交点中任取3个点，可画出多少个三角形？

例57个相同的球，放入4个不同的盒子里，每个盒子至少放一个，不同的放法有多少种？

（请注意，球无区别，盒是有区别的，且不允许空盒）

例6.在6名女同学，5名男同学中，选4名女同学，3名男同学，男女相间站成一排，问共有多少种排法？

例7.甲、乙两人打乒乓球，谁先连胜头两局，则谁赢.如果没有人连胜头两局，则谁先胜三局谁赢，打到决出输赢为止，问有多少种可能情况？

第二部分简单的统筹规化问题

　　最优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间的前提下，努力争取获得在允许范围内的最佳效益．因此，最优化问题成为现代应用数学的一个重要研究对象，它在生产、科学研究以及日常生活中都有广泛的应用．作为数学爱好者，接触一些简单的实际问题，了解一些优化的思想是十分有益的．

例1妈妈让小明给客人烧水沏茶．洗开水壶要用1分钟，烧开水要用15分钟．洗茶壶要用1分钟，洗茶杯要用1分钟，拿茶叶要用2分钟．小明估算了一下，完成这些工作要20分钟．为了使客人早点喝上茶，按你认为最合理的安排，多少分钟就能沏茶了？

例2用一只平底锅煎饼，每次能同时放两个饼．如果煎1个饼需要2分钟（假定正、反面各需1分钟），问煎1993个饼至少需要几分钟？

例3有157吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10公升与5公升．问如何选派车辆才能使运输耗油量最少？

这时共需用油多少公升？

例4有1993名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？

家庭作业

1.有3封不同的信，投入4个邮筒，一共有多少种不同的投法？

2.小虎给3个好朋友写信，由于粗心，结果3个好朋友收到的信都是错的，请问有多少种收信的可能？

3.用0、1、2、3、4、5、6这七个数字可组成多少个比300000大的无重复数字的六位偶数？

　　4.如右图：

在摆成棋盘眼形的20个点中，选不在同一直线上的三点作出以它们为顶点的三角形，问总共能作多少个三角形？

　5．用一只平底锅煎饼，每次能同时放两个饼．如果煎一个饼需要4分钟（假定正、反面各需2分钟），问煎m个饼至少需要几分钟？

　　6.有十张币值分别为1分、2分、5分、1角、2角、5角、1元、2元、5元、10元的人民币，能组成多少种不同的币值？

并请研究是否可组成最小币值1分与最大币值（总和）之间的所有可能的币值.

习题六解答

　　1.若投一封信看作一个步骤，则完成投信的任务可分三步，每封信4个邮筒都可投，即每个步骤都有4种方法.故由乘法原理：

共有不同的投法4×4×4=64种.

　　2.甲（或乙）胜就写一个甲（或乙）字，

　　画树形图：

　　由图可见共有14种可能.

　　甲甲、甲乙甲甲、甲乙甲乙甲、甲乙甲乙乙、甲乙乙甲甲、甲乙乙甲乙、甲乙乙乙、乙甲甲甲、乙甲甲乙甲、乙甲甲乙乙、乙甲乙甲甲、乙甲乙甲乙、乙甲乙乙、乙乙.

　　3.现有4名女同学，3名男同学，男女相间站成一排，则站在两端的都是女同学.将位置从右到左编号，第1、3、5、7号位是女同学，第2、4、6号位是男同学.于是完成适合题意的排列可分两步：

　　第一步：

从6名女同学中任选4名排在第1、3、5、7号位.有P46种排法.

　　第二步：

从5名男同学中任选3名排在第2、4、6号位，有P35种排法.

　　因此，由乘法原理排出不同队形数为

　　P46·P35=6×5×4×3×5×4×3=21600.

　　4.图示：

　　分两类：

　　第一类：

十万位上是3或5之一的六位偶数有

　　P12·P14·P45个.

　　第二类：

十万位上是4或6之一的六位偶数有

　　P12·P13·P45个.

　　∴P12P14P45+P12P13P45=1680.

　　5.五点共线有4组，四点共线的有9组，三点共线的有8组，利用排除法：

　　C320-4C35-9C34-8C33

　　=1140-4×10-9×4-8

　　=1056.

　　6.因为任一张人民币的币值都大于所有币值比它小的人民币的币值的和，例如1角的大于1分、2分、5分的和，因此不论取多少张，它们组成的币值都不重复，所以组成的币值与组合总数一致，有

　　C110+C210+……+C1010=210-1=1023种.

　　因为由这些人民币能组成的最小的币值是1分，最大的币值是十张币值的和，即1888分，而1023＜1888，可见从1分到1888分中间有一些币值不能组成.

第十四讲简单的统筹规化问题

　　最优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间的前提下，努力争取获得在允许范围内的最佳效益．因此，最优化问题成为现代应用数学的一个重要研究对象，它在生产、科学研究以及日常生活中都有广泛的应用．作为数学爱好者，接触一些简单的实际问题，了解一些优化的思想是十分有益的．

例1妈妈让小明给客人烧水沏茶．洗开水壶要用1分钟，烧开水要用15分钟．洗茶壶要用1分钟，洗茶杯要用1分钟，拿茶叶要用2分钟．小明估算了一下，完成这些工作要20分钟．为了使客人早点喝上茶，按你认为最合理的安排，多少分钟就能沏茶了？

分析本题取自华罗庚教授1965年发表的《统筹方法平话》．烧水沏茶的情况是：

开水要烧，开水壶要洗，茶壶茶杯要洗，茶叶要取．怎样安排工作程序最省时间呢？

　　办法甲：

洗好开水壶，灌上凉水，放在火上，在等待水开的时候，洗茶杯，拿茶叶，等水开了，沏茶喝．

　　办法乙：

先做好一切准备工作，洗开水壶，洗壶杯，拿茶叶，灌水烧水，坐等水开了沏茶喝．

　　办法丙：

洗开水壶，灌上凉水，放在火上坐待水开，开了之后急急忙忙找茶叶，洗壶杯，沏茶喝．

　　谁都能一眼看出第一种办法好，因为后两种办法都“窝了工”．

　　开水壶不洗，不能烧开水，固为洗开水壶是烧开水的先决条件，没开水、没茶叶、不洗壶杯，我们不能沏茶，因而这些又是沏茶的先决条件．它们的相互关系可以用下图的箭头图来显示．

　　箭杆上的数字表示完成这一工作所需的时间，例如→表示从把水放在炉上到水开的时间是15分钟．从图上可以一眼看出，办法甲总共要16分钟，而办法乙、丙需20分钟．

　　洗壶杯、拿茶叶没有什么先后关系，而且是由同一个人来做，因此可以将上图合并成下图．

解先洗开水壶用1分钟，接着烧开水用15分钟，在等待水开的过程中，同时洗壶杯、拿茶叶，水开了就沏茶，总共用了16分钟．又因为烧开水的15分钟不能减少，烧水前必须用1分钟洗开水壶，所以用16分钟是最少的．

　　说明：

本题涉及到的统筹方法，是生产、建设、工程和企业管理中合理安排工作的一种科学方法，它对于进行合理调度、加快工作进展，提高工作效率，保证工作质量是十分有效的．

例2用一只平底锅煎饼，每次能同时放两个饼．如果煎1个饼需要2分钟（假定正、反面各需1分钟），问煎1993个饼至少需要几分钟？

分析由于1993数目较大，直接入手不容易．我们不妨先从较小的数目来进行探索规律．

　　如果只煎1个饼，显然需要2分钟；

　　如果煎2个饼，仍然需要2分钟；

　　如果煎3个饼，初学者看来认为至少需要4分钟：

因为先煎2个饼要2分钟；再单独煎第3个饼，又需要2分，所以一共需要4分钟．但是，这不是最佳方案．最优方法应该是：

　　首先煎第1号、第2号饼的正面用1分钟；

　　其次煎第1号饼的反面及第3号饼的正面又用1分钟；

　　最后煎第2号、第3号饼的反面再用1分钟；这样总共只用3分钟就煎好了3个饼．

解：

如果煎1993个饼，最优方案应该是：

　　煎第1、2、3号饼用“分析”中的方法只需要3分钟；煎后面1990个饼时，每两个饼需要2分钟，分1990÷2=995（次）煎完，共需要2×995=1990（分钟）；这样总共需要3+1990=1993（分钟）．

　　说明：

通过本例可以看出，掌握优化的思想，合理统筹安排操作程序，就能够节省时间，提高效率．

例35个人各拿一个水桶在自来水龙头前等候打水，他们打水所需的时间分别是1分钟、2分钟、3分钟、4分钟和5分钟．如果只有一个水龙头，试问怎样适当安排他们的打水顺序，才能使每个人排队和打水时间的总和最小？

并求出最小值．

分析5个人排队一共有5×4×3×2×1=120种顺序，把所有情形的时间总和都计算出来，就太繁琐了．凭直觉，应该把打水时间少的人排在前面所费的总时间会省些．考虑用“逐步调整”法来严格求解．

解：

首先证明要使所费总时间最省，应该把打水时间需1分钟的人排在第一位置．

　　假如第一位置的人打水时间要a分钟（其中2≤a≤5），而打水需1分钟的人排在第b位（其中2≤b≤5）．我们将这两个人位置交换，其他三人位置不变动．这样调整以后第b位后面的人每人排队打水所费的时间与调整前相同，并且前b个人每人打水所费时间也未受影响，但是第二位至第b位的人排队等候的时间都减少了（a-1）分钟，这说明调整后五个人排队和打水时间的总和减少了．换言之，把打水需1分钟的人排在第一位置所费总时间最省．

　　其次，根据同样道理，再将打水需2分钟的人调整到第二位置；将打水需3、4、5分钟的人逐次调整到第三、四、五位．所以将五人按照打水所需时间由少到多的顺序排队，所费时间最省．这样得出5人排队和打水时间总和的最小值是

　　1×5+2×4+3×3+4×2+5×1=35（分钟）．

　　说明：

本题涉及到排序不等式，有兴趣的读者可参阅高年级的数学奥林匹克教材．排队提水的问题，在其他一些场合也是会遇到的．例如，有一台机床要加工n个工件，每个工件需要的加工时间不一样，问应该按照什么次序加工，才能使总的等待时间最短．

例4有157吨货物要从甲地运往乙地，大卡车的载重量是5吨，小卡车的载重量是2吨，大卡车与小卡车每车次的耗油量分别是10公升与5公升．问如何选派车辆才能使运输耗油量最少？

这时共需用油多少公升？

解：

依题意，大卡车每吨耗油量为10÷5=2（公升）；小卡车每吨耗油量为5÷2=2.5（公升）．为了节省汽油应尽量选派大卡车运货，又由于

　　157=5×31+2，

　　因此，最优调运方案是：

选派31车次大卡车及1车次小卡车即可将货物全部运完，且这时耗油量最少，只需用油

　　10×31+5×1=315（公升）

　　说明：

本题是1960年上海市数学竞赛试题．上述解法是最朴素的优化思想——选派每吨耗油量较少的卡车．下面用代数的知识来解题：

　　设选派大卡车a车次，小卡车b车次，依题意：

　　5a+2b=157，即10a=314-4b．

　　于是总耗油量为：

　　W=10a+5b=314=4b+5b=314+b．

　　显然，当b越小时，W也越小．

　　又由5a+2b=157易知，b最小值是1，故W的最小值是314+1=315（公升）．若取b=0，则需派32车次大卡车，耗油量则需320公升．

例6有1993名少先队员分散在一条公路上值勤宣传交通法规，问完成任务后应该在公路的什么地点集合，可以使他们从各自的宣传岗位沿公路走到集合地点的路程总和最小？