# 河內塔

• 有三座塔
• 可能有n個環
• 戒指大小不一
• 一次只能移動一個磁盤
• 任何磁盤只能移動到更大磁盤的頂部
• 只能刪除頂部磁盤

• 磁盤1從1移到3
• 現在，磁盤2從1移到了2
• 磁盤1從3移到2
• 磁盤3從1移到3
• 現在，磁盤1從2移到了1
• 磁盤2從2移到3
• 磁盤1從1移到3

## 河內塔的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盤

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

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

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

，或者你可以說  這是指數的

T（n）= T（n-1）+ k
T（0）= k
T（1）= 2k
T（2）= 3k
T（3）= 4k