汉诺塔简略

问题：这是课堂上提到的一个简略版，就是简单地求一下移动n片铜片要移动多少下。

分析：找递推关系，T(8) = 2T(7) + 1

解释：移动8个铜片，需要先将上面的7个铜片移到B柱子上，然后把A最底下的铜片移动到C柱子上面，此时，那7个铜片还需要再移到C柱子上面，故T(7)要乘以2

根据递推公式，可以写出C语言测试程序：

#include <stdio.h>

int Hano(int n) {
    if (n == 0 || n < 0)
        return 0;
    if (n == 1)
        return 1;
    return 2 * Hano(n - 1) + 1;
}

int main() {
    int n; // 汉诺塔的铜片数目
    printf("请输入n的值：\n");
    fflush(stdout);
    scanf("%d", &n);
    printf("需要移动的次数为 %d \n", Hano(n));
    return 0;
}

测试结果：

汉诺塔简略

原文：https://www.cnblogs.com/fanlumaster/p/13631902.html