11.1 递推方程的定义及实例

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【本节内容】递推方程的定义;汉诺塔、斐波那契数列及串计数模型。建立递推式时,要同时说明下标范围和初值。

【定义11.1.1】给定序列 ,将 与某些下标小于n的项联系起来的等式,称为该序列的递推方程。递推式描述项之间的关系,初值决定具体序列。例如,同为 ,初值不同,一般就得到不同的序列。

【例11.1.1】汉诺塔。三根柱A、B、C,A上有n个大小不同的圆盘,小盘在上。每次只能移动一个顶端圆盘,且大盘不能压在小盘上,要求把全部圆盘移到C,可借助B。

ABC321
图11.1.1 三个圆盘的汉诺塔初始状态;A上由下到上为大、中、小盘

用Hanoi(X,Y,m)表示将m个盘从X移到Y,第三根柱Z充当辅助柱。算法为:若m=0,直接结束;若m≥1,先执行Hanoi(X,Z,m−1),再将X上的最大盘移到Y,最后执行Hanoi(Z,Y,m−1)。特别地,m=1只移动一次。

设该算法的移动次数为 ,则

由11.2节的方法或直接迭代可得 。这不只是该算法的次数,也是三柱规则下的最少次数:最大盘从A移出前,其余n−1盘必须移到另一柱;最大盘到C后,其余盘还要重新叠到它上面,分别至少需要T(n−1)次。因此任何合法解都达到不了更小的次数,而上述算法恰好实现这个下界。

64个盘的移动次数为 。按一年365.25天折算,每秒一次约需5845亿年;即使每秒一亿次,也约需5845年。这说明指数增长不能仅靠提高固定倍数的运算速度消除。这里计算的是移动次数;实际机器的操作耗时还取决于实现。(例完)

【例11.1.2】本书采用下标从0开始的斐波那契序列

前几项为1,1,2,3,5,8,13,21。设 、,则

注意它与另一常用约定 有一位偏移,即 ,不能混用两个下标。(例完)

【蜜蜂祖先模型】采用“雄蜂只有母亲,雌蜂有父母各一”的理想化谱系规则。图中每个结点表示一个祖先位置,M为雄、F为雌。第0代为所考察的雄蜂,第1代有1个祖先位置,第2代2个,第3代3个,第4代5个。

MFMFMFFMFFMFg0: 1g1: 1g2: 2g3: 3g4: 5
图11.1.2 雄蜂的祖先位置树;M只有F母亲,F具有M父亲和F母亲

若第n代共有 个位置,则它的雌性位置数等于上一代全部位置数,雄性位置数等于上一代雌性位置数,因而 ;以 起算有 。这是按代统计的位置数,并非“所有年代祖先的总数”,也不保证所有位置对应不同个体;谱系中若出现共同祖先,实际不同个体数会更少。代0到代n的位置总数为 。

【二进制串计数】设 是长度n、没有相邻两个0的二进制串数。n≥2时按末位分类:末位1的串可由任意合法n−1位串接1得到;末位0时倒数第二位必须1,删除末尾10,得到任意合法n−2位串。这两类互斥且穷尽,于是

长度0的空串也算一种。长度2的合法串为01、10、11,故C₂=3。该序列与f共享递推式,却不共享初值。显式公式可揭示其指数增长;若要逐一输出所有合法串,输出规模本身就随n呈指数增长,不能把“快速算出个数”误当成“快速列出全部对象”。