第二节古代数学游戏PPT课件

.,1,古代数学游戏中的数学文化,.,2,客观世界的许多变化都呈现出前因后果的规律，即某种现象的变化结果与紧靠它前面的一个或多个结果密切相关，这种现象反映到数学上，就是递推关系。通过建立递推关系解决问题的方法，称之为递推方法递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想，这种方法是探索数学规律和解题思路的重要方法之一，它对于几乎是所有的数学分支都有重要的作用.,一、与数列有关的数学游戏,.,3,例1平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？,假设用ak表示k条直线最多能把圆的内部分成的部分数。这里k=0，1，2，。如图可见,.,4,归纳出递推公式an=ann.（）即画第n1条直线时，最多增加n部分。原因是这样的：第一条直线最多把圆分成两部分，故a1=2。当画第二条直线时，要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二条直线的序号。同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就应和前两条直线在圆内各有一个交点。两个交点把第三条直线在圆内部分成三条线段。而每条线段又把原来一个区域划分成两个区域。因而增加的区域部分数是3，正好等于第三条直线的序号，。这个道理适用于任意多条直线的情形，所以递推公式（1）是正确的。,.,5,例假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生下一对小兔。如果养了初生的一对小兔，问满一年时共可得多少对兔子？,我们先退到开始的简单情况来推算，从中归纳出递推关系。第一个月：只有1对小兔；第二个月：一对小兔长成一对大兔，但尚不会生殖，仍只有一对兔子；第三个月：这对大兔生了一对小兔，这时共2对兔子；第四个月：大兔又生了一对小兔，而上月出生的小兔正在长大，这时共3对兔子；第五个月：这时已有两对大兔可以生殖（原来的大兔和第三个月出生的小兔），于是生了两对小兔，这时共有5对兔子.如下图：,.,6,.,7,把推算的结果列成一张表:,由表中可见满一年时可得144对兔子,.,8,如果要算的时间长，这种方法就有困难了，现在我们来找递推关系用Un表示第n个月时的兔子对数，则：Un：1，1，2，3，5，8，13，21，34，容易发现递推公式是：Un=Un-1+Un-2.现在说明这个递推公式是正确的。因为第n个月时的兔子对分两类，一类是第n-1个月时的兔子对数Un-1，另一类是当月新生的兔子对，而这些小兔对数恰好是第n-2个月时的兔子对数Un-2,.,9,数列Un称为斐波那契数列（Fibonacci，11701250，是意大利数学家）,由于数列Un具有许多重要的奇特性质，因而受到数学家们的极大关注，并把数列Un取名为斐波那契数列,.,10,例传说在印度的佛教圣地贝拿勒斯圣庙里安放着一个黄铜板，板上插着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64片中心有孔的金片,每天都有一个值班僧侣按下面规则移动金片：把金片从第一根宝石针移到其余的宝石针上。要求一次只能移动一片，而且小片永远要放在大片的上面.当时传说当64片金片都按上面的规则从第一根宝石针移到另一根宝石针上时，世界将在一声霹雳中毁灭,所以有人戏称这个问题叫“世界末日”问题（也称为“Hanoi塔”问题）。当然，移金片和世界毁灭并无联系，这只是一个传说而已，但说明这是一个需要移动很多很多次才能办到的事情。解这个问题的方法在算法分析中也常用到.究竟按上述规则移动完这64片金片需要移动多少次呢?,.,11,设有n片金片，把从第一片金片至第k片金片按题目要求由第一根宝石针移到另一根宝石针共需ak次先对4片金片的简单情形，用下列的几组图来表示移动过程中的各种状态，并计数，归纳出递归关系式,.,12,.,13,.,14,我们可以这样来想：为了移动第n片到第根宝石针上，我们必须先把它上面的n-1片按题目的规则采用某种程序移到第根宝石针上，这需要移动an-1次，然后才能把最下面第n片（最大的），移到第根宝石针上。最后再经过an-1次才能把第根宝石针上的n-1片金片按上面规则采用同样程序移到第根宝石针上。因此把n片金片按题中的规则全部移到另一根宝石针上共应移：an=2an-1+1（次）（）这就是递推公式。,.,15,为了求得n=64时a64的值，我们当然不能一次次地由a1=1,a2=3,a3=7,直到算出a64现在我们设法把递推公式（）变形为可以直接计算a64的形式a64是一个非常大的数（a64=264-1），如果按照每移动一片需一秒钟算，把64片金片从一根宝石针移到另一根宝石针上大约需要5800亿年！推导如下：,.,16,an=2an-1+1=2(2an-2+1)+1=an-2+2+1=22(2an-3+1)+2+1=23an-3+22+21+1=2n-1a1+2n-2+2n-3+2+1=1+2+22+2n-2+2n-1=2n-1a64=264-1.,.,17,例九连环游戏,“九连环”是中国先人创造的智力游戏.大人玩,小孩玩,也不知道玩了多少代.它是中国文化的精粹之一，2000年在北京举办的世界数学家大会期间,这个古老的游戏引起了与会数学家们的浓厚兴趣.,.,18,首先我们要了解九连环的构造：九连环的设计原理是数学上的拓扑学，它主要有九个圆环及框架组成，每个圆环都连有一个直杆，各直杆在后一个圆环内穿过，九个直杆的另一端用平板或者圆环相对固定，圆环在框架上可以解下或者套上，玩九连环就是要把这九个环全部从框架上解下来或者全部套在框架上（如下图）。,.,19,.,20,九连环的玩法比较复杂，但是不管怎么玩，无论解下环还是套上环都要遵循一定的规则：每次只能解下或者套上一个环；第一个环任何情况下,可自由上下(图);如果某一个环在上,而它前面所有的环都在下,那么这个环的后一个可上也可下(图)Sn=1/62n+2-3+(-1)n-1步,.,21,.,22,我把游戏规则改为以下三条：每次可以解下或者套上一个或者两个环；第一个环可自由上下以及前两个环可一起自由上下；从第二个环开始，如果某一个环在上,而它前面所有的环都在下,那么这个环的后一个可上也可下。实际上在玩九连环的过程中，我发现只有前两个环可以一起自由上下，其它的环每次只能上下一个,另外还要知道解下个环和套上个环需要的步数是一样的。遵循这样的规则，我们给出解下全部的个环需要的步数。,.,23,设解下全部的个环需要的步数为Sn，那么要解下第一个环只需要一步，即S1，要解下前两个环也只需要一步，即S2，而当时，要全部解下这个环，就需要先解下第n个环，而要解下第个环就只能保留其前面的第个环，也就是要先把前面的个环全部解下，这需要Sn2步，这时再需要一步就可以把第个环解下，这时为了把第个环解下，还需要把前面的个环全部套上又需要Sn2步，这时问题就变成了个环的情形，要全部解下这个环还需要Sn1.,.,24,于是我们有,，,.,25,有一个农夫带一条狗、一只鸡和一筐米过河如果没有农夫看管，则狗要吃鸡，鸡要吃米但是船很小，只够农夫带一样东西过河问农夫该如何解此难题？左岸右岸,二、其它游戏的数学解法,.,26,分析：以四维向量（人，狗，鸡，米）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点）,取1表示在右岸，则我们有10个允许状态向量：A1（1，1，1，1）-（0，0，0，0）B1A2（1，1，1，0）-（0，0，0，1）B2A3（1，1，0，1）-（0，0，1，0）B3A4（1，0，1，1）-（0，1，0，0）B4A5（1，0，1，0）-（0，1，0，1）B5,.,27,初始状态是：（0，0，0，0）,最终终态是:（1，1，1，1）,非法中间状态有:（0，0，1，1）,（0，1，1，0）,（0，1，1，1）,（1，1，0，0）,（1，0，0，1）,（1，0，0，0）.转移向量有四个:（1，0，1，0）,（1，1，0，0）,（1，0，0，1）,（1，0，0，0）每一次过河就是一个状态向量与转移向量的加法,且规定:0+0=0,0+1=1+0=1,1+1=0.如:（1，1，1，1）+（1，0，1，0）=（0，1，0，1）,.,28,每一次转移只考虑从允许状态到允许状态.本问题就转化为:找出一个从初始状态（1，1，1，1）经过奇数次运算的到最终状态（0，0，0，0）的转移过程.方法如下:第一次过河：,.,29,第二次过河：,.,30,第三次过河：,.,31,第一种方案：A1（1，1，1，1）（0，0，0，0）B1A2（1，1，1，0）（0，0，0，1）B2A3（1，1，0，1）（0，0，1，0）B3A4（1，0，1，1）（0，1，0，0）B4A5（1，0，1，0）（0，1，0，1）B5,.,32,第二种方案：A1（1，1，1，1）（0，0，0，0）B1A2（1，1，1，0）（0，0，0，1）B2A3（1，1，0，1）（0，0，1，0）B3A4（1，0，1，1）（0，1，0，0）B4A5（1，0，1，0）（0，1，0，1）B5,.,33,三个老道士与三个和尚分别在一条河的两岸，都要到河的对岸去河中只有一条小船，可容两人。只有一个道士和一个和尚会划船而且无论在船上或在岸上，道士的数量都不能超过和尚的数量如何过河？两对夫妻要过河，河中只有一条小船，可容两人两个丈夫都不愿让自己的妻子和另一个男人在一起，除非自己也在场。如何过河？,二、其它游戏的数学解法,.,34,有三对夫妇过河，妻子不准在老公不在的情况下与其他的男人相处，只有一条船，一次最多只准坐两个人，问这三对夫妇怎样才能都过河？三对骗子夫妇过河：三对夫妇过河,男的都是骗子,河中只有一艘船,船最多只能坐二人,如果妻子离开丈夫,就会被其他骗子骗走,他们应该如何安全过河?,二、其它游戏的数学解法,.,35,用向量（H，W）表示左岸的男子数为H，女子数为W则根据题意可取的状态向量有以下个：（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）转移向量为：,.,36,第一次过河为：,.,37,.,38,.,39,习题十四1请你根据下列各个数之间的关系，在括号里填上恰当的数：（1）1，5，9，13，17，（）（2）0.625,1.25,2.5,5,（）（3）（4）198，297，396，495，（），（）,.,40,2将自然数1，2，3，按图排列，在“2”处转第一个弯，“3”处转第二个弯，“5”处转第三个弯，。问哪个数处转第二十个弯？,一般规律：,答案：111,.,41,3上一段12级楼梯，规定每一步只能上一级或两级，问要登上第12级楼梯共有多少种不同走法？4n个连续自然数按规律排成右表:03478111256910根据规律,从2002到2004,箭头的方向依次应为(A)(B)(C)(D),.,42,5观察:1234+1=25,2345+1=121,3456+1=361,(1)请写出一个具有普遍性的结论,