论文部分内容阅读
摘 要: 本文引入了排列组合中的一些典型例题,通过分析其一题多解思想方法,加深了对
组合数学中的一些重要原理的理解,开拓了我们的解题思路,增强了我们的解题能力。
关键词: 排列;组合;一题多解
【中图分类号】G620
一、引言
1.何谓组合数学?
组合数学,为离散数学的一个重要分支,主要研究某组离散对象满足一定条件的安排(或组态)的存在性、构造、计数及优化计算等问题,是一门研究安排问题的学科。中学数学里学习的排列、组合问题及其推广——重复排列和重复组合问题、分派问题、染色问题、中国邮路问题等都是安排问题的例子。组合数学是计算机出现以后迅速发展起来的一门数学分支,为本世纪计算机革命奠定了坚实的基础,推动了软件技术和信息技术快速发展。组合数学不仅在软件、信息技术中有重要的应用价值,在企业管理、交通规划、战争指挥、金融分析等领域都有重要的应用。组合数学无论在应用上和理论上都具有越来越重要的位置,在应用科学项目有更广阔的发展前景,为我国的社会主义建设事业做出更大的贡献。
2.一题多解思想及其在数学学习中的重要性
所谓一题多解,主要体现在解题时没有唯一的固定模式,而是以其多样化答案为明显的特征,可以通过纵横发散,知识串联,综合沟通,达到举一反三,融会贯通的目的。一题多解是培养学生发散思维的好方法,对于一道题从问题的不同角度出发,根据所给的条件,突破固有的解题思想和思维定势,去寻求不同的解题方法,以此达到预期的效果。
一题多解思想是一重要的数学思想,它对数学思维的训练起着重要作用。数学思想方法是数学的精髓,是知识转化为能力的桥梁,具有普遍的应用意义。在分析和解决问题时,它能指导我们探索揭示问题的本质,抓住解决问题的关键,进一步开拓我们的解题思路。通过一题多解能培养思维的发散性、灵活性、敏捷性;对题目的灵活变通,引申推广,培养思维的深刻性、抽象性;对题目解法的简捷性的反思评估,不断优化思想品质,培养思维的严谨性、批判性。对同一数学问题多角度审视引发的不同联想,是一题多解的思想本源,丰富的合理的联想,是对知识的深刻理解、类比、转化、数形结合、函数及方程等数学思想的灵活运用。数学思想方法的运用往往使我们运算简捷明白,推理机敏,是提高数学能力的必由之路。素质教育的核心问题是能力的培养,其中思维能力的训练培养是教与学的主要方面,利用一题多解更好地训练我们的发散思维、创造思维、灵感思维、逆向思维等。
二、排列组合中一题多解例题解析
设某二年制学校已有连续八届毕业生。现欲从毕业生中选出三名代表参加校友会,要求三名代表互不认识(假如相邻的两届毕业生相互认识),问有多少种选法?
(1)方法一:穷举法(分类穷举)
含1:{1,3,5}{1,3,6}{1,3,7}{1,3,8}{1,4,6}
{1,4,7}{1,4,8}[1,5,7]{1,5,8}{1,6,8}
不含1:{2,4,6}{2,4,7}{2,4,8}{2,5,7}{2,5,8}{2,6,8}
不含1,2:{3,5,7}{3,5,8}{3,6,8}
不含1,2,3:{4,6,8}
故共有20种选法。
穷举法讲求技巧,避免重复列举。穷举法是排列组合中常用的一种解题方法,尤其是对于计算复杂度不大的计数。
(2)方法二:用不相邻组合公式求解。
不相邻组合:从个元素中取出r个而不考虑它的顺序,称为从n中取r个组合,其组合数为Cnr。而不相邻组合指的是从序列A={1,2,3 ,…,n}中取r个,其中不存在i,i+1两个相邻的数同时出现于一个组合中的组合,其计数公式组合数为Cn-r+1r。
解:在图论中我们学习了一种特殊的简单图:路pn。若用1,2,3,…,8来表示8届毕业生,相互认识的两届毕业生用线相连,可得如下图:
p8:——————————————
故问题就转化为求p8的有三个顶点的独立集的个数。
求路pn中由r个点组成的独立集的个数,问题实际上是从{1,2,3,...,n}中取r个不相邻的组合问题,此时n=8,r=3,则所求独立集的个数为:
N=
(3)方法三:插入法
考虑从{1,2,3,…8}中选出3个数不相邻的,则可以转化为从8-3个位置的中间插入3个数。若这5个位置用“○”作标记,可插入的位置用“*”标记,则
* ○ * ○ * ○ * ○ * ○ *
即任意“*”位置选3个形成的组合都是不相邻的,共有C63=20种。
(4)方法四:可以用筛法(容斥原理)
2.容斥原理:容斥原理也称为逐步淘汰原理,是计数的一种基本方法,是组合数学中的重要原理。容斥原理的基本原理如下:
定理:设具有性质p1、p2的S中元素的集合为A1、A2,则S中性质p1、p2都不具备的元素个数是 |∣=∣S|-(|A1|+|A2|)+|A1∩A2|
本题求不相邻组合数,只需考虑在C83的所有组合中筛掉有相邻的组合,即去掉其中存在i,i+1两个相邻的数同时出现在一个组合中的组合。
设对已经选好的组合进行从小到大排序,记a b c,设p1表示a=b-1这个性质,即a,b相邻其数集为A1,设p2表示b=c-1这个性质,具有p2的数集为A2,利用容斥原理得:
|∣= C83-(|A1|+|A2|)+|A1∩A2|
|A1|表示 { i,i+1,c} ,c>i+1 ,则| A1|=
| A2|表示{a,i,i+1},a |A1·A2|表示a,b,c三者都相邻数集即为:{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{6,7,8}
故||=C83-21×2+6=20.
不相邻计数=||=C83-21×2+6=20
综合上面四种方法各有优劣之处,技巧性也很强,但对于一题多解开阔思路都大有益处。穷举虽然显得笨拙但是在大多数排列组合解题中都是行之有效的,这往往局限于运算复杂度不太大的情况下。插入排序这是一种很常见的题型,在计算机相关知识的一些算法中常用到,而且简易明了。不相邻组合看起来有些陌生,它在实际问题中比比皆是,只是我们运用得少些而已,而且这个知识点也很重要。然而容斥原理在数学解题中及许多实际问题中是重要的法宝,一个问题不好从正面入手,不妨从反面想想,养成逆向思考问题的习惯。灵活运用所学知识解题,从多方位剖析解题思路优化解题步骤可以达到培养数学思想的目的。
三、结论
一题多解是训练思维的好素材,通过一题多解,引导我们就多角度,多方位,多观点分析思考问题,从而扩充思维,不仅局限于固有的方法,力求标新立异,谋求创新;多样化的题型和解题方法,引导我们参与问题要有不同的广度和深度,通过一题多解促使我努力寻求不同的求解方法及其共同的本质,以及思考方式的共性,这最终上升到多解归一,多题归一的高度,使我们更好地掌握数学思想和方法;教育必须注重对学生素质的全面发展,数学教师在教学过程中重点应放在对学生思维和能力的培养和训练,通过一题多解,增强学生的分析、综合、推理、应用能力等,充分发挥各方面的积极主动性,提高教学效益,更好的培养学生综合运用知识的能力。
参考文献
[1]刁在筠,郑汉鼎.运筹学.北京:高等教育出版社,1996
[2]卢开澄.组合数学(计算机科学组合学丛书).北京:清华大学出版社,1991
[3]彭波.数据结构教程.北京:清华大学出版社,2004
[4]叶上雄.中学教育学.北京:高等教育出版社,2005
[5]欧阳绛.思维的技巧.北京:当代中国出版社,2002
组合数学中的一些重要原理的理解,开拓了我们的解题思路,增强了我们的解题能力。
关键词: 排列;组合;一题多解
【中图分类号】G620
一、引言
1.何谓组合数学?
组合数学,为离散数学的一个重要分支,主要研究某组离散对象满足一定条件的安排(或组态)的存在性、构造、计数及优化计算等问题,是一门研究安排问题的学科。中学数学里学习的排列、组合问题及其推广——重复排列和重复组合问题、分派问题、染色问题、中国邮路问题等都是安排问题的例子。组合数学是计算机出现以后迅速发展起来的一门数学分支,为本世纪计算机革命奠定了坚实的基础,推动了软件技术和信息技术快速发展。组合数学不仅在软件、信息技术中有重要的应用价值,在企业管理、交通规划、战争指挥、金融分析等领域都有重要的应用。组合数学无论在应用上和理论上都具有越来越重要的位置,在应用科学项目有更广阔的发展前景,为我国的社会主义建设事业做出更大的贡献。
2.一题多解思想及其在数学学习中的重要性
所谓一题多解,主要体现在解题时没有唯一的固定模式,而是以其多样化答案为明显的特征,可以通过纵横发散,知识串联,综合沟通,达到举一反三,融会贯通的目的。一题多解是培养学生发散思维的好方法,对于一道题从问题的不同角度出发,根据所给的条件,突破固有的解题思想和思维定势,去寻求不同的解题方法,以此达到预期的效果。
一题多解思想是一重要的数学思想,它对数学思维的训练起着重要作用。数学思想方法是数学的精髓,是知识转化为能力的桥梁,具有普遍的应用意义。在分析和解决问题时,它能指导我们探索揭示问题的本质,抓住解决问题的关键,进一步开拓我们的解题思路。通过一题多解能培养思维的发散性、灵活性、敏捷性;对题目的灵活变通,引申推广,培养思维的深刻性、抽象性;对题目解法的简捷性的反思评估,不断优化思想品质,培养思维的严谨性、批判性。对同一数学问题多角度审视引发的不同联想,是一题多解的思想本源,丰富的合理的联想,是对知识的深刻理解、类比、转化、数形结合、函数及方程等数学思想的灵活运用。数学思想方法的运用往往使我们运算简捷明白,推理机敏,是提高数学能力的必由之路。素质教育的核心问题是能力的培养,其中思维能力的训练培养是教与学的主要方面,利用一题多解更好地训练我们的发散思维、创造思维、灵感思维、逆向思维等。
二、排列组合中一题多解例题解析
设某二年制学校已有连续八届毕业生。现欲从毕业生中选出三名代表参加校友会,要求三名代表互不认识(假如相邻的两届毕业生相互认识),问有多少种选法?
(1)方法一:穷举法(分类穷举)
含1:{1,3,5}{1,3,6}{1,3,7}{1,3,8}{1,4,6}
{1,4,7}{1,4,8}[1,5,7]{1,5,8}{1,6,8}
不含1:{2,4,6}{2,4,7}{2,4,8}{2,5,7}{2,5,8}{2,6,8}
不含1,2:{3,5,7}{3,5,8}{3,6,8}
不含1,2,3:{4,6,8}
故共有20种选法。
穷举法讲求技巧,避免重复列举。穷举法是排列组合中常用的一种解题方法,尤其是对于计算复杂度不大的计数。
(2)方法二:用不相邻组合公式求解。
不相邻组合:从个元素中取出r个而不考虑它的顺序,称为从n中取r个组合,其组合数为Cnr。而不相邻组合指的是从序列A={1,2,3 ,…,n}中取r个,其中不存在i,i+1两个相邻的数同时出现于一个组合中的组合,其计数公式组合数为Cn-r+1r。
解:在图论中我们学习了一种特殊的简单图:路pn。若用1,2,3,…,8来表示8届毕业生,相互认识的两届毕业生用线相连,可得如下图:
p8:——————————————
故问题就转化为求p8的有三个顶点的独立集的个数。
求路pn中由r个点组成的独立集的个数,问题实际上是从{1,2,3,...,n}中取r个不相邻的组合问题,此时n=8,r=3,则所求独立集的个数为:
N=
(3)方法三:插入法
考虑从{1,2,3,…8}中选出3个数不相邻的,则可以转化为从8-3个位置的中间插入3个数。若这5个位置用“○”作标记,可插入的位置用“*”标记,则
* ○ * ○ * ○ * ○ * ○ *
即任意“*”位置选3个形成的组合都是不相邻的,共有C63=20种。
(4)方法四:可以用筛法(容斥原理)
2.容斥原理:容斥原理也称为逐步淘汰原理,是计数的一种基本方法,是组合数学中的重要原理。容斥原理的基本原理如下:
定理:设具有性质p1、p2的S中元素的集合为A1、A2,则S中性质p1、p2都不具备的元素个数是 |∣=∣S|-(|A1|+|A2|)+|A1∩A2|
本题求不相邻组合数,只需考虑在C83的所有组合中筛掉有相邻的组合,即去掉其中存在i,i+1两个相邻的数同时出现在一个组合中的组合。
设对已经选好的组合进行从小到大排序,记a b c,设p1表示a=b-1这个性质,即a,b相邻其数集为A1,设p2表示b=c-1这个性质,具有p2的数集为A2,利用容斥原理得:
|∣= C83-(|A1|+|A2|)+|A1∩A2|
|A1|表示 { i,i+1,c} ,c>i+1 ,则| A1|=
| A2|表示{a,i,i+1},a |A1·A2|表示a,b,c三者都相邻数集即为:{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{6,7,8}
故||=C83-21×2+6=20.
不相邻计数=||=C83-21×2+6=20
综合上面四种方法各有优劣之处,技巧性也很强,但对于一题多解开阔思路都大有益处。穷举虽然显得笨拙但是在大多数排列组合解题中都是行之有效的,这往往局限于运算复杂度不太大的情况下。插入排序这是一种很常见的题型,在计算机相关知识的一些算法中常用到,而且简易明了。不相邻组合看起来有些陌生,它在实际问题中比比皆是,只是我们运用得少些而已,而且这个知识点也很重要。然而容斥原理在数学解题中及许多实际问题中是重要的法宝,一个问题不好从正面入手,不妨从反面想想,养成逆向思考问题的习惯。灵活运用所学知识解题,从多方位剖析解题思路优化解题步骤可以达到培养数学思想的目的。
三、结论
一题多解是训练思维的好素材,通过一题多解,引导我们就多角度,多方位,多观点分析思考问题,从而扩充思维,不仅局限于固有的方法,力求标新立异,谋求创新;多样化的题型和解题方法,引导我们参与问题要有不同的广度和深度,通过一题多解促使我努力寻求不同的求解方法及其共同的本质,以及思考方式的共性,这最终上升到多解归一,多题归一的高度,使我们更好地掌握数学思想和方法;教育必须注重对学生素质的全面发展,数学教师在教学过程中重点应放在对学生思维和能力的培养和训练,通过一题多解,增强学生的分析、综合、推理、应用能力等,充分发挥各方面的积极主动性,提高教学效益,更好的培养学生综合运用知识的能力。
参考文献
[1]刁在筠,郑汉鼎.运筹学.北京:高等教育出版社,1996
[2]卢开澄.组合数学(计算机科学组合学丛书).北京:清华大学出版社,1991
[3]彭波.数据结构教程.北京:清华大学出版社,2004
[4]叶上雄.中学教育学.北京:高等教育出版社,2005
[5]欧阳绛.思维的技巧.北京:当代中国出版社,2002