排列组合中染色问题精华版课件教学资料.pptx

《排列组合中染色问题精华版课件教学资料.pptx》由会员分享，可在线阅读，更多相关《排列组合中染色问题精华版课件教学资料.pptx（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排列组合中染色问题课件排列组合中染色问题课件例.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。例.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。ABCD 分析：A 4种 B 3种 C 3种 D 3种变式1.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。变式1.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。BADC分析：A 4种 B 3种 C

2、3种 D？为什么第四个区域不确定是几种情况呢？解：分类：BD同色：BD异色：36+48=84种变式2.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。变式2.将红、黄、绿、黑四种不同的颜色涂入如图中的区域内，要求相邻的两个区域的颜色都不相同，则不同的涂色方法有（）种。分析：BD可能相同可能不同因此影响E的判断。对BD进行分类。解：分类：BD同色 BD不同色 48+24=72种变式3：用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种涂色方法？变式3：用红

3、、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种涂色方法？变式4用四种颜色给四川、青海、西藏、云南四省（区）的地图染色，每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同的染色方法有多少种？变式4用四种颜色给四川、青海、西藏、云南四省（区）的地图染色，每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同的染色方法有多少种？分析：给四川染色有4种方法，给青海染色有3种方法，给西藏染色有2种方法，给云南染色有2种方法练习1：某城市在中心广场建造一个花圃，花圃分为6个部分（如图）。现要栽种4种不同颜色的花，每部分

4、栽种一种且相邻部分不能栽种同样颜色的花，共有多少不同的栽种方法a1练习2：某伞厂所生产的伞品种齐全，其中品牌为太阳伞的伞的伞蓬都由太阳光的七种颜色组成，这七种颜色分别涂在伞蓬的八个区域内，且恰有一种颜色涂在相对的区域内，则不同颜色图案的此类太阳伞至多有（）种（A）40320（B）5040（C）20160（D）2520总结对区域染色的常见思路：（1）直接根据两个基本原理求解；（2）根据所用的颜色的种数分类；（3）根据某两个区域同色或不同色分类；（4）根据相间区域使用的种类分类。作业（1）用5种颜色给图中的5个车站候车牌（A、B、C、D、E）染色，要求相邻的两个车站间的候车牌颜色不同，有多少种不同

5、的染色方法？（2）如图为一张有5个行政区划分的地图，今要用5种颜色给地图着色要求相邻的区域不同色（B与E，C与D不算相邻区域），共有多少种方案？排列组合中涂色问题排列组合中涂色问题 与涂色问题有关的试题新颖有趣,其中包含着丰富的数学思想。解决涂色问题方法技巧性强且灵活多变，故这类问题的利于培养学生的创新思维能力、分析问题与观察问题的能力，有利于开发学生的智力。本文拟总结涂色问题的常见类型及求解方法。1.、区域涂色问题1.根据分步计数原理，对各个区域分步涂色，这是处理 染色问题的基本方法。例1、用5种不同的颜色给图中标、的各部分涂色，每部分只涂一种颜色，相邻部分涂不同颜色，则不同的涂色方法有多少

6、种？分析：先给号区域涂色有5种方法，再给号涂色有4种方法，接着给号涂色方法有3种，由于号与、不相邻，因此号有4种涂法，根据分步计数原理，不同的涂色方法有2、根据共用了多少种颜色讨论，分别计算出各种出各种 情形的种数，再用加法原理求出不同的涂色方法种数。例2、（2003江苏卷）四种不同的颜色涂在如图所示的6个区域，且相邻两个区域不能同色 分析：依题意只能选用4种颜色，要分四类：（1）与同色、与同色，则有（2）与同色、与同色，则有（3）与同色、与同色，则有（5）与同色、与同色，则有（4）与同色、与同色，则有所以根据加法原理得涂色方法总数为例3、（2003年全国高考题）如图所示，一个地区分为5个行政

7、区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着方法共有多少种？分析：依题意至少要用3种颜色 3.根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形的种数，再用加法原理求出不同涂色方法总数。例4.用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内，每个区域涂一种颜色，相邻两个区域涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？4.根据相间区使用颜色的种类分类例5如图，6个扇形区域A、B、C、D、E、F，现给这6个区域着色，要求同一区域涂同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种不同的颜色可有

8、多少种方法？二、点的涂色问题方法：（1）可根据共用了多少种颜色分类讨论，（2）根据相对顶点是否同色分类讨论，（3）将空间问题平面化，转化成区域涂色 问题。四、面涂色问题例9、从给定的六种不同颜色中选用若干种颜色，将一个正方体的6个面涂色，每两个具有公共棱的面涂成不同的颜色，则不同的涂色方案共有多少种？分析：显然，至少需要3三种颜色，由于有多种不同情况，仍应考虑利用加法原理分类、乘法原理分步进行讨论排列组合问题排列组合问题的的1313种常用解题种常用解题策略策略13 Strategies For Arrangement and Combination13 Strategies For Arran

9、gement and Combination编者的话编者的话1.数学是充满着灵感的学科,排列组合是不乏灵感的一门分支2.排列组合使我们的生活,工作与学习充满规律,有条不紊3.入门前,排列组合无从下手;入门后,排列组合得心应手4.在没有特殊说明的情况下,排列组合的元素都是不同的,这 是因为世界上没有两件完全一样的事物编写说明编写说明 排列组合属于数学中相对独立的一门分支学科,它研究的核心问题是在给定条件下的某事件可能出现的情况总数.排列组合既是学习概率论与数理统计的理论基础,又是组合数学中最基本的概念.由于排列组合问题条件隐晦,题目多变,解题时技巧性强,数字庞大,难以验证,入门困难,因此本人总结

10、自己曾经学习时的笔记,将排列组合问题的解题核心思想以及几种常用的解题策略罗列于本课件,适用于已有排列组合基础的学习者作巩固提高用,需要说明的是,本课件所收录的解题策略并不一定能解决所有的排列组合问题.By:Castelu目录目录 Contents排列排列数与数与组合合数数的公式的公式说明明-Introduction排列排列组合的解合的解题指指导思想思想-Idea13种种常用解常用解题策略策略-Strategy12种种标准原始准原始题型型-Example1234排列数与组合数的公式说明排列数与组合数的公式说明排列数排列数与组合数的公式说明排列数与组合数的公式说明组合数排列数与组合数的公式说明排列

11、数与组合数的公式说明区别与联系Back1.明确题目要求我们去做一件什么事情 What should we do?2.有必要的话,将题目转换成已知的标准原始题型或转换成一种新 的,便于理解的等效模型-Modeling3.决定采用分类的方法还是分步的方法,或是分类与分步并存的方 法去完成这件事情.在执行事件的过程中,关注各步骤是排列问 题(有序),还是组合问题(无序),需要用到何种策略.切记所有完成事情的渠道都考虑到以后才可以结束分类,在每个渠道中,事情完成 以后才可结束分步,否则会因考虑不周全而出错 How should we do?排列组合的解题指导思想排列组合的解题指导思想Back1313种

12、常用解题策略种常用解题策略2.2.分类法分类法1.1.枚举法枚举法3.3.分步法分步法4.4.幂指法幂指法5.5.捆绑法捆绑法6.6.插空法插空法7.7.隔板法隔板法8.8.倍缩法倍缩法9.9.正难则反正难则反10.10.先选后排先选后排11.11.优先法优先法12.12.切割法切割法13.13.作图法作图法1313种常用解题策略种常用解题策略No.1 No.1 枚举法枚举法1313种常用解题策略种常用解题策略No.1 No.1 枚举法枚举法阅读材料阅读材料1313种常用解题策略种常用解题策略No.1 No.1 枚举法枚举法阅读材料阅读材料1313种常用解题策略种常用解题策略No.1 No.1

13、 枚举法枚举法阅读材料阅读材料1313种常用解题策略种常用解题策略No.2No.2 分类法分类法1313种常用解题策略种常用解题策略No.3No.3 分步法分步法1313种常用解题策略种常用解题策略No.4No.4 幂指法幂指法1313种常用解题策略种常用解题策略No.5No.5 捆绑法捆绑法1313种常用解题策略种常用解题策略No.6No.6 插空法插空法1313种常用解题策略种常用解题策略No.7No.7 隔板法隔板法1313种常用解题策略种常用解题策略No.8No.8 倍缩法倍缩法1313种常用解题策略种常用解题策略No.9No.9 正难则反正难则反1313种常用解题策略种常用解题策略N

14、o.10No.10 先选后排先选后排1313种常用解题策略种常用解题策略No.11No.11 优先法优先法1313种常用解题策略种常用解题策略No.12No.12 切割法切割法1313种常用解题策略种常用解题策略No.13No.13 作图法作图法策略清单策略清单枚举法枚举法分类法分类法分步法分步法幂指法幂指法捆绑法捆绑法插空法插空法隔板法隔板法策略实用程度策略实用程度6 6101010108 89 99 99 9相对难易程度相对难易程度易易易易易易易易中中中中难难建议训练题量建议训练题量少少多多多多中中多多多多多多倍缩法倍缩法正难则反正难则反先选后排先选后排优先法优先法切割法切割法作图法作图法

15、策略实用程度策略实用程度9 99 99 99 98 87 7相对难易程度相对难易程度易易中中难难中中难难中中建议训练题量建议训练题量中中多多多多多多中中中中说明说明:1.解决实际排列组合问题时,往往需要各种策略的搭配使用2.本表中,策略实用程度的参考总分为10分,评分仅作参考Back1 12 2种标准原始题型种标准原始题型 标准原始题型 我们已经学习了排列组合解题的指导思想和13种常用解题策略.根据解题指导思想的第2条,我们要将题目转换成已知的标准原始题型或转换成一种新的,便于理解的等效模型.接下来的学习,要求我们熟悉12种标准原始题型,为解决排列组合问题打下更加坚实的基础.需要说明的是,这1

16、2种题型并非代表所有的标准原始题型.一般地,标准原始题型有如下2个重要作用:1.为各种技巧策略提供展示的舞台2.为题目的转换提供理论依据说明:1.我们会指出每道题目所涉及的解题策略,但由于分类法和分步法几乎涵盖在所有的原始题型中,除非相当必要,不再特别指出2.我们在介绍完例题以后,一般都会设置变式题.对于部分例题,我们会采用一题多解的模式,使读者能够熟练地运用各种解题策略1212种标准原始题型种标准原始题型投信问题投信问题例题例题No.4No.4 幂指法幂指法1212种标准原始题型种标准原始题型投信问题投信问题变式变式No.4No.4 幂指法幂指法1212种标准原始题型种标准原始题型排队问题排

17、队问题例题例题1 1No.5No.5 捆绑法捆绑法No.6No.6 插空法插空法图解:_ A _ B _ B _1212种标准原始题型种标准原始题型排队问题排队问题例题例题2 2No.8No.8 倍缩法倍缩法1212种标准原始题型种标准原始题型排队问题排队问题例题例题3 3No.5No.5 捆绑法捆绑法No.9No.9 正难则反正难则反思考:此题假若使用”分类法”,应如何入手?提示:甲,乙,丙均不相邻 插空法甲乙相邻而不与丙相邻 捆绑法,插空法甲丙相邻而不与乙相邻 捆绑法,插空法乙丙相邻而不与甲相邻 捆绑法,插空法 最终,将每一类的结果用分类计数原理相加即可得到答案5761212种标准原始题型

18、种标准原始题型排队问题排队问题例题例题4 4No.12No.12 切割法切割法No.11No.11 优先法优先法1212种标准原始题型种标准原始题型排队问题排队问题例题例题5 5No.12No.12 切割法切割法1212种标准原始题型种标准原始题型排队问题排队问题例题例题6 6No.11No.11 优先法优先法No.12No.12 切割法切割法思考:此题假若使用”倍缩法”,应如何入手?提示:根据分析,我们不难发现,本题涉及到了”部分元素的顺序一定”的概念.因此,我们可以考虑使用传统的”倍缩法”策略解决这一问题其分析步骤为:总体的全排列数为10!每行各自的全排列数均为5!然后,再运用”倍缩法”公

19、式即可得到答案252 事实上,将两种解题方法统一起来,可以进一步得出一个排列与组合的恒等式1212种标准原始题型种标准原始题型排队问题排队问题变式变式1 1No.5No.5 捆绑法捆绑法No.6No.6 插空法插空法图解:_ C _ C _ C _ C _1212种标准原始题型种标准原始题型排队问题排队问题变式变式2 2BANo.11No.11 优先法优先法1212种标准原始题型种标准原始题型排队问题排队问题提高题提高题DCAB矩阵法矩阵法思考:若使用初等排列组合策略,应如何入手?提示:根据顺时针的跳跃次数和逆时针的跳跃次数进行分类.设顺时针的跳跃次数为x,逆时针的跳跃次数为y,不难发现:x+

20、y=8x-y mod 4=0解方程组,得出x,y后,再对每种分类情况运用解题策略,即可得到最终答案1281212种标准原始题型种标准原始题型数字问题数字问题例题例题No.11No.11 优先法优先法1212种标准原始题型种标准原始题型混合问题混合问题例题例题No.10No.10 先选后排先选后排1212种标准原始题型种标准原始题型混合问题混合问题变式变式No.10No.10 先选后排先选后排No.2No.2 分类法分类法1212种标准原始题型种标准原始题型相同元素问题相同元素问题例题例题No.7No.7 隔板法隔板法图解:球 _ 球 _ 球 _ 球 _ 球1212种标准原始题型种标准原始题型相

21、同元素问题相同元素问题变式变式No.7No.7 隔板法隔板法1212种标准原始题型种标准原始题型成对问题成对问题例题例题No.11No.11 优先法优先法1212种标准原始题型种标准原始题型错排问题错排问题例题例题No.13No.13 作图法作图法1212种标准原始题型种标准原始题型错排问题错排问题阅读材料阅读材料容斥原理容斥原理No.9No.9 正难则反正难则反1212种标准原始题型种标准原始题型错排问题错排问题变式变式错排公式错排公式1212种标准原始题型种标准原始题型多重约束问题多重约束问题例题例题No.1 No.1 枚举法枚举法思考:第二步可否使用错排公式解决?1212种标准原始题型种

22、标准原始题型多重约束问题多重约束问题变式变式No.1 No.1 枚举法枚举法1212种标准原始题型种标准原始题型双能问题双能问题例题例题No.2No.2 分类法分类法1212种标准原始题型种标准原始题型多选问题多选问题例题例题1212种标准原始题型种标准原始题型多选问题多选问题例题例题No.2No.2 分类法分类法1212种标准原始题型种标准原始题型涂色问题涂色问题例题例题1 11234No.11No.11 优先法优先法1212种标准原始题型种标准原始题型涂色问题涂色问题例题例题2 2ABCDNo.2No.2 分类法分类法E1212种标准原始题型种标准原始题型涂色问题涂色问题阅读材料阅读材料1

23、 2.n12n.1212种标准原始题型种标准原始题型涂色问题涂色问题阅读材料阅读材料1212种标准原始题型种标准原始题型涂色问题涂色问题阅读材料阅读材料2nNo.11No.11 优先法优先法No.12No.12 切割法切割法递推法递推法No.2No.2 分类法分类法1212种标准原始题型种标准原始题型涂色问题涂色问题变式变式涂色数列涂色数列思考:此题假若使用”分类法”,应如何入手?提示:A,C,E种植同种植物A,E种植同种植物A,C种植同种植物C,E种植同种植物A,C,E均不种植同种植物1212种标准原始题型种标准原始题型淘汰赛问题淘汰赛问题例题例题原始题型清单原始题型清单投信问题投信问题排队

24、问题排队问题数字问题数字问题混合问题混合问题相同元素相同元素成对问题成对问题错排问题错排问题题型实用程度题型实用程度9 910109 910109 98 81010相对难易程度相对难易程度易易中中中中难难中中中中难难建议训练题量建议训练题量中中多多多多多多中中中中多多多重约束多重约束双能问题双能问题多选问题多选问题涂色问题涂色问题淘汰赛淘汰赛题型实用程度题型实用程度8 81010101010109 9相对难易程度相对难易程度易易难难难难难难难难建议训练题量建议训练题量中中多多多多多多中中说明说明:1.解决实际排列组合问题时,题型的转换一定要灵活2.本表中,题型实用程度的参考总分为10分,评分仅

25、作参考排列组合问题的思考循环排列组合问题的思考循环明确目标事件明确目标事件转换标准或等效模型转换标准或等效模型运用各种技巧策略运用各种技巧策略What to doModelingStrategy结束语结束语 行文至此,终于到了收尾的时刻.本人始终认为:由于课件篇幅有限,加上编写仓促,部分观点并不成熟,还没有足够的机会将更多的实用策略和题型展现给读者.在编写课件的同时,本人也学到了不少内容,并对排列组合问题有着这样的感受:微小条件的改变,可能可以引起策略的极大变化;所谓难题,难在我们不知道要运用哪种策略去解决它,即使知道,我们也很难找出最简便的策略,并且,策略间的组合也需要较强数学能力.在今后的学习中,我们一定要牢记解排列组合问题的思考循环,对于灵活的题目,我们需要变通,尝试创造出更多的标准原始题型.By:CasteluThe EndThe End