有 64 个圆盘的河内塔需要多长时间才能递归求解?C++

Question

我正在查看河内程序的递归塔，其中函数被调用了 2^n-1 次。我的室友问我做一座64塔需要多长时间。老实说，我不知道答案，所以我希望有人能在这里帮助我，因为我对答案感兴趣，而不仅仅是等待它出来。

还有 Big-O 符号是什么？

这是我正在查看的代码：

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
{ 
    if (n == 1) 
    { 
        printf("n Move disk 1 from rod %c to rod %c", from_rod, to_rod); 
        return; 
    } 
    towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
    printf("n Move disk %d from rod %c to rod %c", n, from_rod, to_rod); 
    towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
} 
int main() 
{ 
    int n = 4; // Number of disks 
    towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods 
    return 0; 
}

从 GeeksforGeeks.org 那里获取代码

Answer 1

嗯，你知道一个高度n塔需要 2^{个 n-1} 调用，这些调用大约需要相同的时间。

因此，将其定时为一些不太大的n，并将其与您想要的n相关。

等待一座高度为 64 的塔被解决需要很长时间才能直接测量。

关于big-Oh，你知道步数，所以只需删除常量因素和增长缓慢的术语即可。

Answer 2

根据游戏的起源，直到我们生活的宇宙的尽头：https://en.wikipedia.org/wiki/Tower_of_Hanoi

这个谜题是由法国数学家爱德华·卢卡斯在 1883. 有一个关于喀什毗湿瓦纳特的印度寺庙的故事，里面有一个大房间，里面有三个破旧的柱子， 周围环绕着64个金色圆盘。婆罗门祭司，执行命令 一个古老的预言，一直在按照移动这些圆盘 从那时起，梵天就拥有不可改变的规则。谜题是 因此也被称为梵天之塔拼图。根据 传说，当拼图的最后一步完成时，世界将 结束。

Answer 3

">

这需要多长时间才能解决"不是一个有用的问题;它完全取决于编译和运行代码的系统的处理能力。

"河内塔递归实现的 Big-O 是什么"是绝对可以解决的。 当您进行计算时，您会发现它是 O(2^n(，其中 n 是您拥有的磁盘数。

你可以在这里找到一个非常好的关于计算ToH的大O的讨论：讨论/证明