# 河内塔

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