古代数学游戏.pptxVIP

古代数学游戏中的数学文化;　　客观世界的许多变化都呈现出前因后果的规 律，即某种现象的变化结果与紧靠它前面的一个或 多个结果密切相关，这种现象反映到数学上，就是 递推关系。 　　通过建立递推关系解决问题的方法，称之为递 推方法． 　　递推方法是人们从开始认识数量关系时就很自然地产生 的一种推理思想，这种方法是探索数学规律和解题思路的重 要方法之一，它对于几乎是所有的数学分支都有重要的作用.;　　例1 平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？;　　归纳出递推公式an＋１=an＋n. （１） 即画第n＋1条直线时，最多增加n部分。原因是这样的：第 一条直线最多把圆分成两部分，故a1=2。当画第二条直线 时，要想把圆内部分割的部分尽可能多，就应和第一条直线 在圆内相交，交点把第二条直线在圆内部分分成两条线段， 而每条线段又把原来的一个区域划分成两个区域，因而增加 的区域数是2，正好等于第二条直线的序号。同理，当画第 三条直线时，要想把圆内部分割的部分数尽可能多，它就应 和前两条直线在圆内各有一个交点。两个交点把第三条直线 在圆内部分成三条线段。而每条线段又把原来一个区域划分成 两个区域。因而增加的区域部分数是3，正好等于第三条直线 的序号，…。这个道理适用于任意多条直线的情形，所以递推 公式（1）是正确的。 ;　　例２假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生下一对小兔。如果养了初生的一对小兔，问满一年时共可得多少对兔子？ ;;;　　如果要算的时间长，这种方法就有困难 了，现在我们来找递推关系． 　　用｛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 ．;　　数列｛Un｝称为斐波那契数列（Fibonacci， 1170～1250，是意???利数学家）,由于数列｛Un｝ 具有许多重要的奇特性质，因而受到数学家们的极 大关注，并把数列｛Un｝取名为斐波那契数列 ．;　　例３ 传说在印度的佛教圣地贝拿勒斯圣庙里安放 着一个黄铜板，板上插着三根宝石针，在第一根宝石 针上，从下到上穿着由大到小的64片中心有孔的金片, 每天都有一个值班僧侣按下面规则移动金片： 把金片从第一根宝石针移到其余的宝石针上。要求 一次只能移动一片，而且小片永远要放在大片的上面. 当时传说当64片金片都按上面的规则从第一根宝石针 移到另一根宝石针上时，世界将在一声霹雳中毁灭,所 以有人戏称这个问题叫“世界末日”问题（也称为“Hanoi 塔”问题）。 　当然，移金片和世界毁灭并无联系，这只是一个传 说而已，但说明这是一个需要移动很多很多次才能办 到的事情。解这个问题的方法在算法分析中也常用到. 究竟按上述规则移动完这64片金片需要移动多少次呢?;　　设有n片金片，把从第一片金片至第k片金片 按题目要求由第一根宝石针移到另一根宝石针共需 ak次． 　　先对4片金片的简单情形，用下列的几组图来 表示移动过程中的各种状态，并计数，归纳出递归 关系式． ;　　我们可以这样来想：为了移动第n片到第Ⅲ 根宝石针上，我们必须先把它上面的n-1片按题 目的规则采用某种程序移到第Ⅱ根宝石针上，这 需要移动an-1次，然后才能把最下面第n片（最大 的），移到第Ⅲ根宝石针上。最后再经过an-1次 才能把第Ⅱ根宝石针上的n-1片金片按上面规则 采用同样程序移到第Ⅲ根宝石针上。因此把n片 金片按题中的规则全部移到另一根宝石针上共应 移： 　　　　an=2an-1+1（次） （＊） 这就是递推公式。;　　为了求得n=64时a64的值，我们当然不能一次 次地由a1=1,a2=3,a3=7,…直到算出a64． 　　现在我们设法把递推公式（＊）变形为可以 直接计算a64的形式． 　　a64是一个非常大的数（a64=264-1） ，如果按 照每移动一片需一秒钟算，把64片金片从一根宝 石针移到另一根宝石针上大约需要5800亿年！！ 　　推导如下：; ∵ 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-1 ∴ a64=264-1. ;例４