河內塔


難度級別 容易獎學金
經常問 事實集 風箏 空氣質量
分而治之 數學 遞歸 學校編程

河內塔是一個具有以下條件的數學問題:

  • 有三座塔
  • 可能有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)。

參考