Hanoi 问题 :
该递推方程表示 , 将
个盘子的移动次数
, 与
个盘子的移动次数
之间的关系 ;
解法参考 : 【组合数学】递推方程 ( 特特解示例 ) 一、特解示例 1 ( 汉诺塔 )
表示在最坏的情况下插入排序的次数 ;
前面的
个数已经排好了 , 其在最坏的情况下插入排序次数是
次 ,
第
个数字要插入到这
个数字中 , 最坏的情况是 要插入的数字要与所有的已排序好的
个数字进行比较 , 对比次数是
次 ,
因此递推方程可以写成 :
递推方程初值 :
, 如果只有一个数字 , 不用进行排序 , 对比次数是
;
最终解为 :
, 精确值为