组合数学讲义 3章 递推关系(3)

组合数学讲义

（四） 例

例3.1.1 （Hanoi塔问题）这是组合学中著名的问题。n个圆盘按从小到大的顺序一次套在柱A上，如图3.1.1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A、B、C三根柱子可供使用。用an表示将n个盘从柱A移到柱C上所需搬动圆盘的最少次数，试建立数列{an}的递推关系。

A B C

图3.1.1 Hanoi塔问题

（解）特例：a1＝1，a2＝3，对于任何n≥3。 一般情形：：

第一步，将套在柱A的上部的n－1个盘按要求移到柱B上，共搬动了an 1次；

第二步，将柱A上的最大一个盘移到柱C上，只要搬动一次；

第三步，再从柱B将n－1个盘按要求移到柱C上，也要用an 1次。

an 2an 1 1,

由加法法则：

(3.1.3)

a1 1

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库组合数学讲义 3章 递推关系(3)在线全文阅读。