C 语言的河内塔
更高类别： [C语言] C语言索引
1. 概述
2. 最小移动次数
3. C 代码
a. GitHub
1.概述
⑴ 定义
河内塔是法国数学家卢卡斯于 1883 年提出的一个问题。它涉及确定移动 n 个圆盘所需的最小移动次数。
⑵ 图例
在印度贝拿勒斯的一座寺庙里，有一个巨大的圆顶，代表着世界的中心。圆顶内部的青铜板上刻有三颗钻石针。针高一肘，粗细不过星体。其中一根针饰有 64 个金色圆盘。最大的圆盘放置在底部，其余的圆盘越来越小地堆叠到顶部。这就是神圣的梵天塔。按照梵天的指示，僧侣们日夜爬上祭坛，按照规则将圆盘一张一张地移到另一根针上。据说，当这个任务完成后，塔就会倒塌，世界就会终结。
2.最少移动次数
⑴ 概述
例如，如果只有两个圆盘，你想将它们从 A 柱移动到 C 柱，则可以按如下方式移动它们：A → B、A → C、B → C。数学家为解决这个问题做了各种尝试，发现最小移动次数为 2n-1。
⑵ 递归关系
① 递归公式：an+1 = 2an + 1
② 帮助理解递归公式的图
<中心>
<中心>
<中心>
<img src="https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FPENBj%2FbtrLEwmHwSp%2Fto9iFkUPnO5HKWzODGHqIK%2Fimg.png" alt="绘图"样式=“宽度：400px;”/>
3。 C 代码
受保护_0
输入：2016.02.08 19:39
修改: 2022.09.08 13:24