论文部分内容阅读
摘要本文我们将阐述递推关系的有关定义及其相关概念,将这些内容作分类分步介绍,并给出相关的一系列例题及其解法。
关键词递推 Fibonacci数列 梵塔之谜 染色
中图分类号:G633.6文献标识码:A
谈到递推关系, Fibonacci数列最具典型性。中世纪意大利数学家斐波那契在1202年提出了这样一个问题(统称兔子繁殖问题):“年初在围栏中放了一对小兔,每对新生的小兔从第二个月开始生一对小兔,求一年后,围栏里的兔子的对数。”通过分析不难得到每个月的兔子对数构成了1,1,2,3,5,8,13,……这样一个递推数列,用递推方法建立数列的通项,是数学中最有用的方法之一。我们来看几个常见的递推关系例子。
1 梵塔之谜
有3个竹桩,把n个大小互异的圆盘由大到小穿在第一个竹桩上,最大的在底部,现在打算一个一个地搬动,从第一竹桩全部转移到另一个竹桩上,并且要求任何时候都不允许把大圆盘放在较小圆盘的上面。问:至少搬动几次才能完成这个转移?设把A柱上的n片圆片全部转移到C柱所需的最少次数为an,试回答:(1)a1,a2,a3是多少?(2)an和an-1间有怎样的关系?(3)求an。
解:(1)显然A柱上只有一个圆片时,只需移动一次,就可以将圆片移到C柱。所以a1=1 。
当A柱上有两片圆片时,必须利用B柱作过渡,即先将第一片移到B柱,再将第二片移到C柱,最后将B柱上的小圆片移到C柱上。这样,A柱上的两片圆片就移到了C柱上,并且小片压在大片上。因此,a2=3 。
当A柱上有三片圆片时,应该怎样考虑呢?由于必须一片一片的移动,大的又不许压在小的上面,所以,想要移动A柱上最底下的一片圆片,也就是第三片圆片,就必须将第一、二片圆片先搬到某一根柱上(当然是搬到B柱上比较恰当; 注意,这需要用a2=3次),这样一来,就可以将第三片圆片从A柱上移到C柱上(这样又是1次)。最后,将B柱上的两片圆片通过A柱过渡到C柱上(这样又要a2=3次)。所以,一共要7次,即:a3=2a2+1。
(2)从第(1)小题的讨论中,不难知道an与an-1间的关系,应是an=2an-1+1是一个常系数线性非齐次递推关系,下面用升阶法求解这个递推关系。
(3)因为an=2an-1+1,an-1=2an-2+1。两式相减得:an-an-1=2(an-1-an-2),同理,有an-1-an-2=2(an-2-an-3),an-2 -an-3=2(an-3- an-4)……,a3-a2=2(a2-a1),迭代得 :an-an-1=2n-2(a2-a1).又因a1=1,a2=3 所以an-an-1=2n-1,累加得an-a1=2+22+…… +2n-1,即an=1+2+22+ …… +2n-1=2n-1
2 染色问题
设有n个顶点V1,V2,…VN和n条L1L2…LN边构成一个回形图,用七种颜色对每个点着色,使每两个有边相连的顶点着不同的颜色,问这种着色法共有多少种:
解:设着色法数为(与顶点数n有关),为研究问题方便起见,我们在回形图中去掉一条边,例如Vn和V1之间的边,则此图变为有两个端点的一条直线。
在直线图中,V1有七种颜色,V1一旦选定颜色后,V2只有六种着色法,V2选定后,V3仍有六种着色法,因为V3 与V1无边直接相连,可以着相同的颜色,如此下去,回形图的着色法共有种,直线图的所有着色法可分为两类:一类是V1 与Vn着不同的颜色;另一类是V1与Vn着相同的颜色。
前者就是G的着色数,后者相当于把V1,Vn合为一个点,构成n-1个点的回路着色法数,由此可知,(n=3、4、…)。不难得出,(种),可以用递推法求。,将代入得:(n=2、3、4、…),则即为着色数。
3 分形问题
有一个雪花序列,其产生规则是:将正三角形k0的每一边三等分,而以其居中的那一条线段为一底边向外作等边三角形,再擦去中间的那条边,便得到第一条雪花曲线K1;再将K1的每条边三等分,并重复上述作法,便得到第二条雪花曲线K2;……;把KN-1的每条边三等分,并以中间那条边向外作等边三角形,再擦去中间的那条边,便得到第n条雪花曲线KN(n=1,2,3,……)。①设K0的周长为L0,即正三角形周长,求第n条雪花曲线KN的周长LN;②设K0的面积为A0,即正三角形面积,求第n条雪花曲线KN围成的面积AN;③随着n的增大,LN和AN是否会各趋向于某一定值?
解:①雪花曲线序列中,后一雪花曲线的长为相邻前一个长的。设第n条雪花曲线的长为LN,则LN=()NL0,n=1,2,3,…
② KN比KN-1多3·4N-1(KN-1的边数)个面积为的正三角形。因而,AN=AN-1+3·4N-1·,AN=[8-3()N]。
③由于LN=()NL0是公比为>1的等比数列,所以LN趋向于无穷大;另一方面,AN= [8-3()N],而0<<1,所以AN将会趋向于定值A0。
注:(1)本题的结论十分有趣,无限长的曲线居然只能围成有限大的面积,出人意料。这是现代数学一个新的分支——“分形几何学”的一个简单例子。(2)美丽的雪花曲线是瑞典数学家H.vonKonch在1904年首次发现的,故又称之为Koch曲线。
关键词递推 Fibonacci数列 梵塔之谜 染色
中图分类号:G633.6文献标识码:A
谈到递推关系, Fibonacci数列最具典型性。中世纪意大利数学家斐波那契在1202年提出了这样一个问题(统称兔子繁殖问题):“年初在围栏中放了一对小兔,每对新生的小兔从第二个月开始生一对小兔,求一年后,围栏里的兔子的对数。”通过分析不难得到每个月的兔子对数构成了1,1,2,3,5,8,13,……这样一个递推数列,用递推方法建立数列的通项,是数学中最有用的方法之一。我们来看几个常见的递推关系例子。
1 梵塔之谜
有3个竹桩,把n个大小互异的圆盘由大到小穿在第一个竹桩上,最大的在底部,现在打算一个一个地搬动,从第一竹桩全部转移到另一个竹桩上,并且要求任何时候都不允许把大圆盘放在较小圆盘的上面。问:至少搬动几次才能完成这个转移?设把A柱上的n片圆片全部转移到C柱所需的最少次数为an,试回答:(1)a1,a2,a3是多少?(2)an和an-1间有怎样的关系?(3)求an。
解:(1)显然A柱上只有一个圆片时,只需移动一次,就可以将圆片移到C柱。所以a1=1 。
当A柱上有两片圆片时,必须利用B柱作过渡,即先将第一片移到B柱,再将第二片移到C柱,最后将B柱上的小圆片移到C柱上。这样,A柱上的两片圆片就移到了C柱上,并且小片压在大片上。因此,a2=3 。
当A柱上有三片圆片时,应该怎样考虑呢?由于必须一片一片的移动,大的又不许压在小的上面,所以,想要移动A柱上最底下的一片圆片,也就是第三片圆片,就必须将第一、二片圆片先搬到某一根柱上(当然是搬到B柱上比较恰当; 注意,这需要用a2=3次),这样一来,就可以将第三片圆片从A柱上移到C柱上(这样又是1次)。最后,将B柱上的两片圆片通过A柱过渡到C柱上(这样又要a2=3次)。所以,一共要7次,即:a3=2a2+1。
(2)从第(1)小题的讨论中,不难知道an与an-1间的关系,应是an=2an-1+1是一个常系数线性非齐次递推关系,下面用升阶法求解这个递推关系。
(3)因为an=2an-1+1,an-1=2an-2+1。两式相减得:an-an-1=2(an-1-an-2),同理,有an-1-an-2=2(an-2-an-3),an-2 -an-3=2(an-3- an-4)……,a3-a2=2(a2-a1),迭代得 :an-an-1=2n-2(a2-a1).又因a1=1,a2=3 所以an-an-1=2n-1,累加得an-a1=2+22+…… +2n-1,即an=1+2+22+ …… +2n-1=2n-1
2 染色问题
设有n个顶点V1,V2,…VN和n条L1L2…LN边构成一个回形图,用七种颜色对每个点着色,使每两个有边相连的顶点着不同的颜色,问这种着色法共有多少种:
解:设着色法数为(与顶点数n有关),为研究问题方便起见,我们在回形图中去掉一条边,例如Vn和V1之间的边,则此图变为有两个端点的一条直线。
在直线图中,V1有七种颜色,V1一旦选定颜色后,V2只有六种着色法,V2选定后,V3仍有六种着色法,因为V3 与V1无边直接相连,可以着相同的颜色,如此下去,回形图的着色法共有种,直线图的所有着色法可分为两类:一类是V1 与Vn着不同的颜色;另一类是V1与Vn着相同的颜色。
前者就是G的着色数,后者相当于把V1,Vn合为一个点,构成n-1个点的回路着色法数,由此可知,(n=3、4、…)。不难得出,(种),可以用递推法求。,将代入得:(n=2、3、4、…),则即为着色数。
3 分形问题
有一个雪花序列,其产生规则是:将正三角形k0的每一边三等分,而以其居中的那一条线段为一底边向外作等边三角形,再擦去中间的那条边,便得到第一条雪花曲线K1;再将K1的每条边三等分,并重复上述作法,便得到第二条雪花曲线K2;……;把KN-1的每条边三等分,并以中间那条边向外作等边三角形,再擦去中间的那条边,便得到第n条雪花曲线KN(n=1,2,3,……)。①设K0的周长为L0,即正三角形周长,求第n条雪花曲线KN的周长LN;②设K0的面积为A0,即正三角形面积,求第n条雪花曲线KN围成的面积AN;③随着n的增大,LN和AN是否会各趋向于某一定值?
解:①雪花曲线序列中,后一雪花曲线的长为相邻前一个长的。设第n条雪花曲线的长为LN,则LN=()NL0,n=1,2,3,…
② KN比KN-1多3·4N-1(KN-1的边数)个面积为的正三角形。因而,AN=AN-1+3·4N-1·,AN=[8-3()N]。
③由于LN=()NL0是公比为>1的等比数列,所以LN趋向于无穷大;另一方面,AN= [8-3()N],而0<<1,所以AN将会趋向于定值A0。
注:(1)本题的结论十分有趣,无限长的曲线居然只能围成有限大的面积,出人意料。这是现代数学一个新的分支——“分形几何学”的一个简单例子。(2)美丽的雪花曲线是瑞典数学家H.vonKonch在1904年首次发现的,故又称之为Koch曲线。