§22递推关系 假定η-1个盘子的转移算法已经确定。 对于一般n个圆盘的问题 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上
§2.2 递推关系 对于一般n个圆盘的问题， 假定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 A B C
§22递推关系 上述算法是递归的运用。n=2时已给出 算法;n=3时,第一步便利用算法把上面 两个盘移到B上,第二步再把第三个圆盘转 移到柱C上;最后把柱B上两个圆盘转移到 柱C上。N=4,5,…以此类推
§2.2 递推关系 上述算法是递归的运用。n=2时已给出 算法；n=3时，第一步便利用算法把上面 两个盘移到B上，第二步再把第三个圆盘转 移到柱C上；最后把柱B上两个圆盘转移到 柱C上。N=4，5，…以此类推
§22递推关系 算法分析:令hn)表示n个圆盘所需要 的转移盘次。根据算法先把前面η-1个盘子 转移到B上;然后把第n个盘子转到C上;最 后再一次将B上的n-1个盘子转移到C上 n=2时,算法是对的,因此,n=3是算 法是对的。以此类推。于是有
§2.2 递推关系 算法分析：令h(n)表示n个圆盘所需要 的转移盘次。根据算法先把前面n-1个盘子 转移到B上；然后把第n个盘子转到C上；最 后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算 法是对的。以此类推。于是有
§22递推关系 算法复杂度为 h(n)=2h(n-1)+1,h(1)=1(2-2-1) H(x)=h(1)x+h(2)x2+h(3)x3+…, HxX)是序列h(),h(2),h(3,…的母函数。 给定了序列,对应的母函数也确定了。反过来 也一样,求得了母函数,对应的序列也就可得 而知了。当然,利用递推关系(22-1)式也可以 依次求得h(2),h(3…,这样的连锁反应关系, 叫做递推关系
§2.2 递推关系 算法复杂度为： h(n) = 2h(n −1) +1, h(1) =1 (2 - 2-1) ( ) (1) (2) (3) , H x = h x + h x 2 + h x 3 + H(x)是序列 的母函数。 给定了序列，对应的母函数也确定了。反过来 也一样，求得了母函数，对应的序列也就可得 而知了。当然，利用递推关系(2-2-1)式也可以 依次求得 ，这样的连锁反应关系， 叫做递推关系。h(1), h(2), h(3), h(2), h(3),
§22递推关系 下面介绍如何从(2-2-1)式求得母函数 H(X)的一种形式算法。所谓形式算法说的 是假定这些幂级数在作四则运算时,一如 有限项的代数式一样 H(x)=h(1)x+h(2)x2+h(3)x2+…, +)-2xH(x) 2h(1)x-2h(2)x+ (1-2x)H(x)=h(1)x+[h(2)-2h(1)x2 +[h(3)-2h(2)]x3
§2.2 递推关系 下面介绍如何从(2-2-1)式求得母函数 H(x)的一种形式算法。所谓形式算法说的 是假定这些幂级数在作四则运算时，一如 有限项的代数式一样。 ( ) (1) (2) (3) , H x = h x + h x 2 + h x 3 + __________ +) − 2x H(x __________ ) = - 2h __________ (1)x − 2h(2) _______ x + , + − + − = + − 3 2 [ (3) 2 (2)] (1 2 ) ( ) (1) [ (2) 2 (1)] h h x x H x h x h h x