第一章初等模型

1、数学建模简明教程数学建模简明教程杨尚俊杨尚俊 编著编著安徽大学出版社出版安徽大学出版社出版 20062006年年引引 言言0.1 0.1 数学的重要性数学的重要性0.2 0.2 本书主要内容本书主要内容0.3 0.3 本课程主要特点本课程主要特点0.1 0.1 数学的重要性数学的重要性n新世纪国家间的竞争主要是经济竞争新世纪国家间的竞争主要是经济竞争, ,是人是人才的竞争才的竞争; ;人才培养的关键是素质教育人才培养的关键是素质教育, ,数数学教育在素质教育中占据重要地位学教育在素质教育中占据重要地位. .n当今社会正日益数学化当今社会正日益数学化, ,数学是高科技的基数学是高科技的基础础.

2、.n数学在工程技术以及国民生产中发挥愈来数学在工程技术以及国民生产中发挥愈来愈重要的作用甚至是决定性的作用愈重要的作用甚至是决定性的作用. .素质教育的重要性素质教育的重要性n素质教育既是素质教育既是“科教兴国科教兴国”战略的必然选择战略的必然选择, ,也也是教育自身进一步发展的客观需要是教育自身进一步发展的客观需要, ,更是高校发更是高校发展的灵魂和动力展的灵魂和动力. .n理工科的特征往往体现在严谨理工科的特征往往体现在严谨, ,规范的教育体系规范的教育体系上上, ,而综合性大学更重要的是强调个性化教育而综合性大学更重要的是强调个性化教育. .能充分挖掘每个学生的潜力的个性化教育往往能充分

3、挖掘每个学生的潜力的个性化教育往往是一所综合性大学的重要特征和体现是一所综合性大学的重要特征和体现, ,而数学建而数学建模的教育及实践正符合这方面的要求模的教育及实践正符合这方面的要求. . 数学是高科技的基础数学是高科技的基础n社会进步依赖于科学的创新而数学对于科学的发展社会进步依赖于科学的创新而数学对于科学的发展则具有根本的意义则具有根本的意义. .在今天在今天, ,数学已成为高科技的基数学已成为高科技的基础础, ,并且在一定意义上并且在一定意义上, ,可以说是现代文明的标志可以说是现代文明的标志 (2002(2002年北京国际数学家大会东道国欢迎词摘录年北京国际数学家大会东道国欢迎词摘录

4、).).n各行各业日益依赖于数学各行各业日益依赖于数学, ,可以说可以说, ,当今社会正日益当今社会正日益数学化数学化. .数学正在向一切领域渗透数学正在向一切领域渗透, ,数学正在不停地数学正在不停地与别的学科结合产生活跃的新兴学科与别的学科结合产生活跃的新兴学科.”.”高科技本高科技本质上是一种数学技术质上是一种数学技术”的观点正在被越来越多的人的观点正在被越来越多的人接受接受. . 20022002年年8 8月在中国首都北京举行国际数学月在中国首都北京举行国际数学家家20022002年大会年大会, ,这是该国际最高级数学学术会这是该国际最高级数学学术会议第一次在一个发展中国家举行议第一次

5、在一个发展中国家举行. .我国政府非我国政府非常重视和支持这次会议常重视和支持这次会议, ,最高领导人出席了会最高领导人出席了会议开幕式议开幕式, ,并为得奖者授奖并为得奖者授奖. .这是李岚清副总这是李岚清副总理在致大会欢迎词中的一段话理在致大会欢迎词中的一段话. . 数学在生产中起重要作用的例子数学在生产中起重要作用的例子n曾经有一家电器公司生产中出现成品率只曾经有一家电器公司生产中出现成品率只有有84%,84%,并仅有并仅有50%50%的发货日期可以兑现所造的发货日期可以兑现所造成的严重亏损问题成的严重亏损问题. . 他们应用统计质量控他们应用统计质量控制在很短时间就成功地发现和解决了问

6、题制在很短时间就成功地发现和解决了问题, ,使成品率稳定在使成品率稳定在95%95%以上以上, ,按期发货率也达按期发货率也达到到95%,95%,当年就实现扭亏增盈当年就实现扭亏增盈12001200万美元万美元. .n这个故事告诉我们这个故事告诉我们: :数学可以在国民生产中数学可以在国民生产中发挥重要作用发挥重要作用, ,甚至决定性作用甚至决定性作用. .Mathematical Science,Technology,Economic Compitive- Mathematical Science,Technology,Economic Compitive- ness,Nationalnes

7、s,National Academy Press, Washington D.C.1991. Academy Press, Washington D.C.1991.该公司最先发现出现电器元件的各种性能波动太大该公司最先发现出现电器元件的各种性能波动太大. .他们首先用数学技术找出产生元件性能波动的原因他们首先用数学技术找出产生元件性能波动的原因是在自动控制的酸洗工序中确定酸洗液是在自动控制的酸洗工序中确定酸洗液PHPH值的机制值的机制有问题有问题, ,产生校正过度产生校正过度. .他们再用数学技术他们再用数学技术( (优选法优选法) )重新校正减少了起伏重新校正减少了起伏, ,从而解决了这个大

8、问题从而解决了这个大问题. .这份这份报告提出的如下结论也颇有启发性报告提出的如下结论也颇有启发性:“:“在经济竞争在经济竞争中数学科学是必不可少的中数学科学是必不可少的. .数学科学是一种关键性数学科学是一种关键性的的, ,能够实行的技术能够实行的技术.”.” 这个例子取自这个例子取自GlimmGlimm教授主持编撰的代表教授主持编撰的代表美国数学科学委员会给美国政府的公开报告美国数学科学委员会给美国政府的公开报告: :0.2 0.2 本课程的主要内容本课程的主要内容n初等方法建模初等方法建模n微分方程方法建模微分方程方法建模n层次分析方法建模层次分析方法建模n矩阵分析方法建模矩阵分析方法建

9、模n数学规划方法建模数学规划方法建模n依靠智力巧妙建模依靠智力巧妙建模n大学生数学建模竞赛和大学生数学建模竞赛和MatlabMatlab编程及应用编程及应用0.3 0.3 本课程的特点本课程的特点n以讨论具体实际问题为主要线索以讨论具体实际问题为主要线索. .n以讲授数学建模的思路与方法为主要目的以讲授数学建模的思路与方法为主要目的. .n强调启发思路和分析、解决问题的技巧强调启发思路和分析、解决问题的技巧. . n按求解所讨论的具体数学模型的需要介绍按求解所讨论的具体数学模型的需要介绍有关数学背景知识和基本方法有关数学背景知识和基本方法, ,即实际问题即实际问题需要什么介绍什么需要什么介绍什

10、么, ,不强求数学方面的系统不强求数学方面的系统性与完整性性与完整性. .第第1 1章章 初等模型初等模型 1.1 1.1 例子与定义例子与定义 1.2 1.2 其它初等模型其它初等模型1.1 1.1 例子与定义例子与定义例例1 1 航行问题航行问题: :已知已知: :沿长江在相距沿长江在相距750km750km的两个码头的两个码头A A与与B B之间之间, ,顺顺水航行时间是水航行时间是 30hr;30hr;逆水航行时间是逆水航行时间是50hr.50hr.试分别求出船和水的平均速度试分别求出船和水的平均速度. .AB解解: :令船和水的平均速度分别是令船和水的平均速度分别是x x和和y,y,

11、由题意得二由题意得二元方程组元方程组: :求解此方程组得求解此方程组得 x=20, y=5.x=20, y=5.答案答案: :船和水的平均速度分别是船和水的平均速度分别是20km/hr20km/hr和和5km/hr.5km/hr.5075030750yxyx必要的简化与说明必要的简化与说明 这里这里, ,只考虑平均速度是基本的简化只考虑平均速度是基本的简化, ,因因为船和水的速度是随时间为船和水的速度是随时间, ,地点而变化的地点而变化的. .严严格讲格讲, ,已知的顺水已知的顺水, ,逆水航行时间是船在该河逆水航行时间是船在该河段上常年航行的平均时间段上常年航行的平均时间; ;而要求的船和水

12、而要求的船和水的平均速度也应是该船和水在该河段上常年的平均速度也应是该船和水在该河段上常年航行的平均速度航行的平均速度. . 若把实际问题看作原型的话若把实际问题看作原型的话, ,则数学模型是将原则数学模型是将原型经过简化提炼而构成的替代物型经过简化提炼而构成的替代物. .这里值得注意的这里值得注意的是是: :简化是构作数学模型的必要前提简化是构作数学模型的必要前提. . 解决本问题也需要速度等相关的物理概念解决本问题也需要速度等相关的物理概念. . 解决本问题的步骤解决本问题的步骤: :按照题意设定未知量并按照题意设定未知量并决定未知量满足的数学公式决定未知量满足的数学公式; ;求出这个方程

13、求出这个方程组的解组的解; ;并在讨论解的存在性与唯一性之后并在讨论解的存在性与唯一性之后确定该解就是原问题所需要的解确定该解就是原问题所需要的解. . 别忘了验证解的正确性别忘了验证解的正确性. .什么是数学模型什么是数学模型? ?n如果要下一个定义的话如果要下一个定义的话, ,可以说可以说: :数学模型数学模型是对是对一个实际问题一个实际问题, ,按照其内在规律作出一些必要按照其内在规律作出一些必要的假设的假设( (目的为了简化和去掉不确定的因素使目的为了简化和去掉不确定的因素使之能归结为一个确定的数学问题之能归结为一个确定的数学问题) )并应用适当并应用适当数学工具导出的一个数学结构数学

14、工具导出的一个数学结构. .借助数学的分借助数学的分析与计算全面探讨并求出所得数学模型的解析与计算全面探讨并求出所得数学模型的解, ,再利用有关的背景知识可以成功地将所得数学再利用有关的背景知识可以成功地将所得数学解用来解释和回答原先的实际问题解用来解释和回答原先的实际问题. .这一整个这一整个过程称为数学建模过程称为数学建模. .可用下面的图表直观地表可用下面的图表直观地表示数学建模过程的各阶段及其联系示数学建模过程的各阶段及其联系. .实际问题实际问题抽象抽象, ,简化简化, ,假设假设, ,确定变量与参数确定变量与参数建立数学模型并求解建立数学模型并求解, ,确定参数确定参数交付使用从而

15、产生经济交付使用从而产生经济, ,社会效益社会效益用实际背景或数据等来检验数学模型用实际背景或数据等来检验数学模型若不符合实际若不符合实际若符合实际若符合实际例例2 2 气象预报问题气象预报问题气象观测与气象观测与气象预报气象预报偏微分方程组的初偏微分方程组的初值边值混合问题值边值混合问题求出数值解确定求出数值解确定有关参数有关参数作作24hr,48hr24hr,48hr和和72hr72hr预报预报简化简化, ,归纳归纳使用巨型使用巨型计算机计算机用数值结果用数值结果解释气象解释气象分析偏差及其分析偏差及其产生原因产生原因 作为天气现象的数学模型在一百多年前就已经作为天气现象的数学模型在一百多

16、年前就已经很成功地解决了很成功地解决了, ,它是一个特殊的二阶非线性偏微分它是一个特殊的二阶非线性偏微分方程组的初值方程组的初值, ,边值混合问题边值混合问题. .遗憾的是遗憾的是, ,这个偏微分这个偏微分方程组的混合问题很难求解方程组的混合问题很难求解, ,不要说不要说, ,精确解找不到精确解找不到, ,就是求很粗糙近似解的计算量也惊人地巨大就是求很粗糙近似解的计算量也惊人地巨大. .在现代在现代巨型电子计算机未出世以前巨型电子计算机未出世以前, ,即使通过求此混合问题即使通过求此混合问题很粗糙近似解来作短期天气预报也是不现实的很粗糙近似解来作短期天气预报也是不现实的, ,因为因为化一个月甚

17、至更多时间也完成不了所需的计算化一个月甚至更多时间也完成不了所需的计算. .直到直到2020世纪世纪8080年代出现每秒可完成上亿次运算的巨型计算年代出现每秒可完成上亿次运算的巨型计算机以后机以后, , 数值天气预报这个多年的梦想才得以实现数值天气预报这个多年的梦想才得以实现. .目前我国也研制成功每秒千亿次运算水平的巨型机目前我国也研制成功每秒千亿次运算水平的巨型机, ,保证了中央气象台每天及时而准确地发布各种天气预保证了中央气象台每天及时而准确地发布各种天气预报报, ,为国民生产及人民生活作出巨大贡献为国民生产及人民生活作出巨大贡献. .实际问题与其数学模型之间的关系实际问题与其数学模型之

18、间的关系n大家知道大家知道原型原型与与模型模型之间的关系之间的关系. .若把实际问题看若把实际问题看作原型的话作原型的话, ,则数学模型是将原型经过精致地简化则数学模型是将原型经过精致地简化, ,提炼而构成的替代物提炼而构成的替代物. .n这里必须强调两点这里必须强调两点: :第一第一, ,一般来说一般来说, ,原型是复杂和原型是复杂和困难的困难的, ,必须把它归结为数学模型才能解决必须把它归结为数学模型才能解决; ;第二第二, ,数学模型不是原型原封不动的复制品数学模型不是原型原封不动的复制品, ,它只是在突它只是在突出反映原型某些方面性质的近似物出反映原型某些方面性质的近似物. .这里难免

19、会存这里难免会存在数学模型与原型的差异甚至矛盾在数学模型与原型的差异甚至矛盾, ,冲突冲突. .但对我但对我们来讲们来讲, ,原型是根本的原型是根本的, ,当二者出现无法解释的矛当二者出现无法解释的矛盾时盾时, ,必须修改相关的数学模型以适应原型必须修改相关的数学模型以适应原型. .例例3 3 安全过河问题安全过河问题问题问题: : 一位老师带三名小学生一位老师带三名小学生: :甲甲, ,乙和丙过河乙和丙过河. .假假设仅有一条小渡船设仅有一条小渡船, ,最多能容纳二人最多能容纳二人; ;并且只有老并且只有老师能划船师能划船. .此外此外, ,学生乙很顽皮学生乙很顽皮, ,无老师在场时他肯无老

20、师在场时他肯定要欺负甲和丙定要欺负甲和丙. . 老师应如何安排过河方案使四老师应如何安排过河方案使四人都到达彼岸并且不发生学生乙与学生甲人都到达彼岸并且不发生学生乙与学生甲, ,丙单独丙单独相处而发生打架伤人的事故相处而发生打架伤人的事故? ?甲甲乙乙丙丙师师 过河问题过河问题的解的解一种安全过河方案是一种安全过河方案是: : 师乙过去师乙过去, , 接着师回接着师回; ; 师甲去师甲去, , 接着师乙回接着师乙回; ; 师丙过去师丙过去, , 接着师回接着师回; ; 师乙过去师乙过去. . 师甲丙师甲丙乙乙师乙丙师乙丙甲甲师乙师乙甲丙甲丙师甲乙丙师甲乙丙师甲乙丙师甲乙丙 实际问题及其数学模型

21、不仅可以涉及实际问题及其数学模型不仅可以涉及数量关系数量关系, ,也可以涉及方案也可以涉及方案, ,规则规则, ,措施等措施等方面方面, ,过河问题就是一例过河问题就是一例. . n过河问题过河问题(1)(1)的答案唯一吗的答案唯一吗? ?n不允许重复时有几个答案不允许重复时有几个答案? ?n最少渡河次数是多少最少渡河次数是多少? ?n如果每人都能划船结论又是如何如果每人都能划船结论又是如何? ? 思考题思考题1-11-1例例4 4 安全过河问题安全过河问题问题问题：三个商人每人带一随从过河：三个商人每人带一随从过河. .假设仅有一条假设仅有一条小渡船小渡船, ,最多能容纳二人最多能容纳二人;

22、 ;并且因他们正处于偏并且因他们正处于偏僻地带僻地带, ,这几个不安分的随从在他们人数超过商这几个不安分的随从在他们人数超过商人人数时将图谋不轨人人数时将图谋不轨. .应如何安排过河方案使六应如何安排过河方案使六人到达彼岸之前都不发生随从数超过商人数情人到达彼岸之前都不发生随从数超过商人数情况而引发杀人越货的事故况而引发杀人越货的事故? ?从从1商商1从从2从从3商商2商商3 切莫以为数学建模问题都像例切莫以为数学建模问题都像例1,1,例例3 3那那么简单么简单. .不信的话不信的话, ,请你不要参看下面一张幻请你不要参看下面一张幻灯片灯片, ,试着对例试着对例4 4中的问题中的问题, ,给出

23、你的安全过给出你的安全过河方案河方案. .你能较快地写出一个安全过河方案你能较快地写出一个安全过河方案吗吗? ? 2 2从过去从过去 接着接着1 1从回来从回来; ; 2 2从过去从过去 接着接着1 1从回来从回来; ; 2 2商过去商过去 接着接着1 1商商1 1从回来从回来; ; 2 2商过去商过去 接着接着1 1从回来从回来; ; 2 2从过去从过去 接着接着1 1从回来从回来; ; 2 2从过去从过去. . 过河问题过河问题的解的解相关的数学表示与分析相关的数学表示与分析n河岸的人员状态可用二维向量河岸的人员状态可用二维向量(x,y)(x,y)表示表示, ,意指在意指在所考虑的时刻所考

24、虑的时刻, ,该岸有该岸有x x商人和商人和y y随从随从.x,y.x,y的取值范的取值范围是围是0,1,2,3.0,1,2,3.易见易见: :每岸共有每岸共有4 42 2=16=16种可能的人种可能的人员状态员状态; ;两岸人员状态互相唯一决定两岸人员状态互相唯一决定, ,例如例如, ,若此岸若此岸状态向量为状态向量为(x,y),(x,y),则彼岸状态向量则彼岸状态向量为为(3-x,3-y).(3-x,3-y).n一岸的安全状态向量一岸的安全状态向量(x,y)(x,y)应满足条件应满足条件:x:x y y或或x=0.x=0.但当此岸出现但当此岸出现 xy xy 时时, ,彼岸状态向量彼岸状态

25、向量(x(x ,y,y )=(3-)=(3-x,3-y)x,3-y)将出现将出现 x x yy xy 也认为是不安全的状态也认为是不安全的状态. .n所以所以, ,每岸的每岸的1616种状态中恰有种状态中恰有1010种是安全的种是安全的, ,它它们组成的集合是们组成的集合是S=(x,y)|x=0S=(x,y)|x=0 x=3x=3x=y.x=y.n上述分析也适用于有上述分析也适用于有n n个商人及个商人及n n个随从的情况个随从的情况, ,其中其中,n,n为任意正整数为任意正整数. .此时此时, ,安全集为安全集为 S=(x,y)|x=0S=(x,y)|x=0 x=nx=nx=y.x=y.n在

26、直角坐标系下安全集在直角坐标系下安全集S S的点组成的点组成字形字形, ,详见下图详见下图. .xy(0,0)(3,3)(2,2)(1,1)(0,1)(0,2)(0,3)(3,0)(3,2)(3,1)此岸状态图此岸状态图图图 1-11-1解决安全过河问题解决安全过河问题(2)(2)的数学模型的数学模型 基于前面的分析建立解决基于前面的分析建立解决n n商商n n从安全过河问题的从安全过河问题的字形棋盘单人跳棋模型字形棋盘单人跳棋模型: :在此岸安全集在此岸安全集S S组成的组成的字形棋盘上字形棋盘上, ,经奇数步经奇数步从起点从起点(n,n)(n,n)跳到终点跳到终点(0,0)(0,0)为成功

27、为成功. .跳棋规则是跳棋规则是: :每步在水平或垂直方向跳每步在水平或垂直方向跳1 1或或2 2格格; ;或在或在4545 斜线方斜线方向跳向跳1 1格格. .奇数步向下向左跳奇数步向下向左跳; ;偶数步向上向右跳偶数步向上向右跳. .一个成功的跳棋过程将给出一个成功的跳棋过程将给出n n商商n n从安全过河问题的从安全过河问题的一个方案一个方案. .例如例如, ,图图1-11-1所示的成功跳棋过程正好对所示的成功跳棋过程正好对应我们前面提出的那个安全过河方案应我们前面提出的那个安全过河方案. .关于安全过河问题关于安全过河问题(2)(2)解的讨论解的讨论n一般来说一般来说, ,该问题只要有

28、一个解就有无穷多个解该问题只要有一个解就有无穷多个解. .因为因为: :在这个解的第在这个解的第1 1步之前增加两步步之前增加两步:“1:“1随从过随从过去去, ,接着再回来接着再回来”, ,走完此两步仍回到原状态走完此两步仍回到原状态. .显然显然, ,把这两步作任意次循环把这两步作任意次循环, ,都将回到原状态都将回到原状态. .所以所以, ,由由一个已知解可以构造出无穷多个不同的解一个已知解可以构造出无穷多个不同的解. .换句话换句话说说, ,此问题解的唯一性一般不成立此问题解的唯一性一般不成立. .n我们应把两个这样的解看作同一类我们应把两个这样的解看作同一类: :其中一个解除其中一个

29、解除多一个循环之外多一个循环之外, ,与另一个解完全相同与另一个解完全相同, ,这里这里, ,循环循环指的是偶数步来回过渡指的是偶数步来回过渡, ,并保持循环前和循环后两并保持循环前和循环后两岸状态完全一样岸状态完全一样. .今后今后, ,同一类的解中恒取那个同一类的解中恒取那个”不允许重复的解不允许重复的解”为代表为代表. .n注意注意: :即使不区别商人随从间的置换即使不区别商人随从间的置换, ,对于不允许对于不允许重复的解重复的解, ,解的唯一性一般地也是不成立的解的唯一性一般地也是不成立的. .例如例如, ,对于安全过河问题对于安全过河问题(2),(2),仔细观察图仔细观察图1-11-

30、1不难发现不难发现: :从从(3,3)(3,3)出发出发, ,经经“2 2从过去从过去, ,接着接着1 1从回来从回来”或或“1 1商商1 1从过去从过去, ,接着接着1 1商回来商回来”都达到同样的状都达到同样的状态态:”1:”1从在彼岸从在彼岸, ,其余人员在此岸其余人员在此岸”. .因此因此, ,安全安全过河问题过河问题(2)(2)至少有两个不允许重复的解至少有两个不允许重复的解. .n每个不允许重复的解的渡河次数称为最少渡河次每个不允许重复的解的渡河次数称为最少渡河次数数. .例如例如, ,对图对图1-11-1表示的那个不允许重复解最少表示的那个不允许重复解最少渡河次数是渡河次数是11

31、.11.你能证明你能证明:”:”对任何正整数对任何正整数n,nn,n商商n n从的安从的安全过河问题全过河问题, ,不允许重复的解一定是有限不允许重复的解一定是有限个个”吗吗? ?你能证明你能证明: :对对3 3商商3 3从安全过河问题从安全过河问题, ,不允许不允许重复的解个数是重复的解个数是4 4吗吗? ?思考题思考题1-21-2安全过河问题安全过河问题(2)(2)的各种推广的各种推广1. 1. 渡船容量不变渡船容量不变( (即至多容即至多容2 2人人),),仅商人仅商人, ,随从随从人数有所改变人数有所改变思考题思考题1-31-3 对任意正整数对任意正整数n n 2,2,讨论讨论n n商

32、人和商人和n n随从能否安全过随从能否安全过河河, ,若能若能, ,并给出答案并给出答案. .思考题思考题1-41-4 对任意正整数对任意正整数n n 2,2,讨论讨论n+1n+1商人和商人和n n随从能否安全随从能否安全过河过河? ?若能并给出答案若能并给出答案. .2. 2. 渡船容量和商从人数都改变渡船容量和商从人数都改变思考题思考题1-51-5 假设渡船至多容假设渡船至多容3 3人人,5,5商人和商人和5 5随从能否安全过河随从能否安全过河? ?若能若能, ,请给出答案请给出答案. .并考虑怎样作更一般性的推广并考虑怎样作更一般性的推广? ? 思考题思考题1-61-6 假设渡船至多容假

33、设渡船至多容4 4人人, ,能否证明能否证明: :对任意正整数对任意正整数n,nn,n商人和商人和n n随从都能安全过河随从都能安全过河? ?给出你的答案的严格给出你的答案的严格证明证明. . 1.2 1.2 其它初等模型其它初等模型n小兔繁殖问题小兔繁殖问题n汉诺塔问题汉诺塔问题n圆内接三角形计数问题圆内接三角形计数问题n双层玻璃窗保温功效可行性分析双层玻璃窗保温功效可行性分析n代表席位公平分配问题代表席位公平分配问题n最优价格制定问题最优价格制定问题小兔繁殖问题小兔繁殖问题假设假设: :一对刚出生的小兔一对刚出生的小兔( (一公一母一公一母) )被放到一被放到一个水草丰盛的孤岛上个水草丰盛

34、的孤岛上;2;2月龄及以上的每对月龄及以上的每对兔子每一个月恰好繁殖一对新兔兔子每一个月恰好繁殖一对新兔( (也是一也是一公一母公一母););在观察期间没有任何兔子死去在观察期间没有任何兔子死去. .问题问题: :试计算在观察期间的第试计算在观察期间的第n n个月岛上兔子个月岛上兔子总对数总对数. .解解: :记第记第n n个月内兔子总对数为个月内兔子总对数为f fn n. .则显然则显然f f1 1=1;=1;因一月龄的兔不能繁殖因一月龄的兔不能繁殖, ,故故f f2 2=1.=1.当当n n 3 3时时, ,为了计算第为了计算第n n月兔子对数月兔子对数f fn n, ,要把前一个月要把前

35、一个月的兔子对数的兔子对数f fn-1n-1加上新生兔子对数加上新生兔子对数, ,而新生兔子而新生兔子对数正好等于对数正好等于f fn-2n-2( (因每对兔子一次生一对因每对兔子一次生一对).).这这就证明数列就证明数列ffn n 满足初始条件满足初始条件:f:f1 1=f=f2 2=1=1和递推关和递推关系系: : f fn n=f=fn-1n-1+f+fn-2n-2,n,n 3.3.不难依次求得数列不难依次求得数列ffn n 前若干项前若干项( (参看图参看图1-2)1-2)的值的值如上表所示如上表所示: :n n1 12 23 34 45 56 67 78 8f fn n1 11 12

36、 23 35 58 813132121123456考察期考察期间月数间月数图图 1-21-21月龄兔月龄兔2月龄兔月龄兔FibonacciFibonacci数列数列 数列数列ffn n 在理论和运用方面都非常有用在理论和运用方面都非常有用, ,被称为被称为FibonacciFibonacci数列数列. .可以方便地编程计可以方便地编程计算数列算数列ffn n,也可以证明它满足下列封闭公也可以证明它满足下列封闭公式式: : f fn n=(1/=(1/ 5)(u5)(un n-v-vn n),n=1,2,),n=1,2, (2.1) (2.1) 其中其中,u=(1+,u=(1+ 5)/2,v=(

37、1-5)/2,v=(1- 5)/2.5)/2.试用试用MatlabMatlab编程求编程求f fn n, ,其中其中n n为任意正整数为任意正整数. .你能严格证明公式你能严格证明公式(2.1)(2.1)吗吗? ?思考题思考题 1-71-7汉诺塔问题汉诺塔问题: :一个著名数学游戏一个著名数学游戏游戏规则游戏规则: :今有安装在一块木板上的今有安装在一块木板上的3 3根柱子和若干根柱子和若干中心有孔的盘子中心有孔的盘子. .这些盘子的直径两两不同这些盘子的直径两两不同. .开始开始时时, ,它们已按大小的次序套在第一根柱子上它们已按大小的次序套在第一根柱子上, ,使得使得每个盘子的下面没有比它

38、小的盘子每个盘子的下面没有比它小的盘子. .每一次把每一次把1 1个个盘子从一根柱子移动到另一根柱子盘子从一根柱子移动到另一根柱子, ,但是不允许但是不允许这个盘子放在任何比它小的盘子上面这个盘子放在任何比它小的盘子上面. .游戏的最游戏的最终目标是把所有的盘子都放到第三根柱子上终目标是把所有的盘子都放到第三根柱子上, ,并并保持按大小次序放置保持按大小次序放置, ,大盘子在下面大盘子在下面. .问题问题: :令令h hn n表示解表示解n n个盘子汉诺塔问题所需要的最少个盘子汉诺塔问题所需要的最少移动次数移动次数. .试建立关于试建立关于h hn n的递推关系并求出的递推关系并求出h hn

39、n的封的封闭公式闭公式. .111222213333ABCD汉诺塔问题的解法汉诺塔问题的解法开始时开始时n n个盘子放在柱个盘子放在柱1.1.按照游戏规则我们可以用按照游戏规则我们可以用h hn-1n-1次移动将上边的次移动将上边的n-1n-1个盘子移到柱个盘子移到柱2.2.在这些在这些移动中保留最大的盘子不动移动中保留最大的盘子不动, ,然后我们用一次移然后我们用一次移动将最大盘子移动到柱动将最大盘子移动到柱3.3.我们可以再使用我们可以再使用h hn-1n-1次次移动将柱移动将柱2 2上的上的n-1n-1个盘子移到柱个盘子移到柱3,3,把它们放到把它们放到最大的盘子上面最大的盘子上面( (

40、这个最大的盘子一直放在柱这个最大的盘子一直放在柱3 3的底部的底部).).容易看出容易看出, ,使用更少的次数是不可能达使用更少的次数是不可能达到目的的到目的的. .这就证明了这就证明了h hn n=2h=2hn-1n-1+1.+1.初始条件是初始条件是h h1 1=1,=1,因为依照规因为依照规则一个盘子可以经则一个盘子可以经1 1次移动从柱次移动从柱1 1移到柱移到柱3.3. h hn n=2h=2hn-1n-1+1+1 =2(2h =2(2hn-2n-2+1)+1+1)+1 =2 =22 2h hn-2n-2+2+1+2+1 =2 =22 2(2h(2hn-3n-3+1)+2+1+1)+

41、2+1 =2 =23 3h hn-3n-3+2+22 2+2+1+2+1 = = =2=2n-1n-1h h1 1+2+2n-2n-2+ + +2+1+2+1 =2 =2n-1n-1+2+2n-2 n-2 + + +2+1 +2+1 用了初始条件用了初始条件h h1 1=1=1 =2 =2n n-1-1 用了等比级数公式用了等比级数公式用迭代方法求解这个递推关系用迭代方法求解这个递推关系 在汉诺地方有一座塔在汉诺地方有一座塔, , 那里的僧侣们严格那里的僧侣们严格按照这个游戏规则从一个柱子到另一个柱子按照这个游戏规则从一个柱子到另一个柱子移动移动6464个金盘子个金盘子. . 他们一秒钟移动一

42、个盘子他们一秒钟移动一个盘子. . 据说当他们结束游戏时世界就到了末日据说当他们结束游戏时世界就到了末日. . 试问试问: : 这个世界在僧侣们开始移动盘子多这个世界在僧侣们开始移动盘子多久以后终结久以后终结? ? 答案答案: 2: 26464-1-1秒秒 50005000亿年亿年一个古老的传说一个古老的传说过圆周上等分点的三角形计数问题过圆周上等分点的三角形计数问题假设假设n(n( 2)2)为给定的正整数为给定的正整数, ,并已知圆周并已知圆周上的上的n n个等分点个等分点. .试计算以这些等分点试计算以这些等分点为顶点的一切可能的锐为顶点的一切可能的锐, ,直直, ,钝角三角钝角三角形个数

43、形个数. . 下图显示下图显示n=8n=8的情形的情形. .12836547用循环数组用循环数组(i,j,k)(i,j,k)来刻画所讨论三角形的构形来刻画所讨论三角形的构形, ,其中其中i,j,ki,j,k分别表示该三角形按反时针方向相分别表示该三角形按反时针方向相邻二点间所夹已知等分点的个数邻二点间所夹已知等分点的个数. .易见易见, ,经旋转经旋转后能重合的三角形构形相等后能重合的三角形构形相等; ;所讨论三角形的所讨论三角形的构形满足下列条件构形满足下列条件: : i,j,k i,j,k 0,i+j+k=n-3. (0,i+j+k=n-3. (* *) )例如例如, ,在上面例子中的锐角

44、三角形在上面例子中的锐角三角形472,472,直角三角形直角三角形156,156,钝角三角形钝角三角形238238可分别刻画为可分别刻画为 (2,2,1),(3,0,2)(2,2,1),(3,0,2)和和(0,4,1).(0,4,1).建立数学模型建立数学模型n构形构形(0,4,1)(0,4,1)与与(0,1,4)(0,1,4)视为不同视为不同, ,因对应三角因对应三角形形238238与与235235旋转后不重合旋转后不重合. .n设设ABCABC为有构形为有构形(i,j,k(i,j,k) )的三角形的三角形, ,显然显然, ,ABCABC为为直角直角三角形三角形 maxi,j,kmaxi,j

45、,k = =n/2-1;n/2-1;ABCABC为为锐角锐角三角形三角形 maxi,j,kmaxi,j,k n/2-1;n/2-1;ABCABC为为钝角钝角三角形三角形 maxi,j,kmaxi,j,k n/2-1.n/2-1.注注 记记n (i,j,k(i,j,k) )中的中的i,j,ki,j,k两两不同两两不同, ,则则(i,k,j(i,k,j) )视为与视为与 (i,j,k(i,j,k) )构形不同的三角形构形构形不同的三角形构形. .n 在具体计算直在具体计算直, ,钝角三角形个数时钝角三角形个数时, ,只要确定一只要确定一切满足条件切满足条件( (* *) )的不同的不同( (非等边非等边) )三角形构形三角形构形(i,j,k)(i,j,k)的个数的个数a,a,再乘以再乘以n n即可即可. .计算锐角三角形计算锐角三角形个数时个数时, ,还要计算等边三角形还要计算等边三角形(i=j=k)(i=j=k)构形的个数构形的个数b.b.则锐角三角形个数等于则锐角三角形个数等于 n(a+b/3).n(a+b/3).n=8n=8时共计有时共计有 锐角构形一个锐角构形一个:(1,2,2);:(1,2,2); 直角构形直角构形3 3个个:(1,1,3),(0,2,3)