河内塔


难度级别 易得奖学金
经常问 事实集 风筝 空气质量
分而治之 数学 递归 学校编程

河内塔是一个具有以下条件的数学问题:

  • 有三座塔
  • 可能有n个环
  • 戒指大小不一
  • 一次只能移动一个磁盘
  • 任何磁盘只能移动到更大磁盘的顶部
  • 只能删除顶部磁盘

说明

让我们看看当我们有两个磁盘时如何解决此问题

河内塔解释

我们将顶部(小)磁盘移至下一个塔,然后将第二个磁盘移至第三塔,然后最终将第一个磁盘也移至第三塔。 (3招)

假设:最初对磁盘进行了排序

同样,当我们使用3个磁盘时。 我们将需要7个步骤才能将所有步骤转移到第三环。

  • 磁盘1从1移到3河内塔
  • 现在,磁盘2从1移到了2河内塔
  • 磁盘1从3移到2河内塔
  • 磁盘3从1移到3河内塔
  • 现在,磁盘1从2移到了1
  • 磁盘2从2移到3
  • 磁盘1从1移到3

因此,我们将n-1个磁盘移到第二个塔上,最后一个磁盘移到第三个塔上,将n-1个磁盘移到第一个塔上,从而完成了转移。

现在让我们来看一个 递归 执行相同。

河内塔的JAVA程序

public class hanoi
{
  public static void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  public static void main(String args[])
  {
    int n=3;
    hanoi(n,'A','B','C');
  }
}

河内塔的C ++程序

#include<iostream>
using namespace std;
  void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  int main()
  {
    int n=4;
    hanoi(n,'A','B','C');
  }
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 3From rod: A To Rod: B
Moving disk 1From rod:C To Rod:A
Moving disk 2From rod:C To Rod:B
Moving disk 1From rod: A To Rod: B
Moving disk 4From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 2From rod: B To Rod: A
Moving disk 1From rod:C To Rod:A
Moving disk 3From rod:B To Rod:C
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C

河内塔的结论

因此,我们得出以下结论:

15移动4盘

31移动5盘

因此,我们得出的结论是 对于n个磁盘 我们需要做 (2 ^ n)-1个动作.

2 disks=(2*2)-1=2 moves

3 disks=(2^3)-1=7 moves

4 disks=(2^4)-1=15 moves

等等。

河内塔的复杂度分析

时间复杂度

递归方程:  T(n)= 2T(n-1)+1

T(n)= O(2 ^ {(n + 1)}-1),或者你可以说 O(2 ^ n) 这是指数的

空间复杂度

T(n)= T(n-1)+ k
T(0)= k
T(1)= 2k
T(2)= 3k
T(3)= 4k
因此,空间复杂度为O(n)。

參考資料