Question

解决一道数学题，谢谢啊

汉诺塔问题是指有3根杆子A、B、C。 B杆上有若干碟子，把所有碟子从B杆移到A杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面，把B杆上的4个碟子全部移到A杆上面,最少需要移动几次
告诉我每步应如何移动
谢谢啊！！！

Answer 1

假设移动n个碟子至少要用an步。则有a1=1，a2=3.
现在做如下处理：n个碟子全部在B上，要把最大的一个碟子移到A上，先要将B上的最大上面的n-1个移到C上，要a（n-1）步，然后把最大的碟子移到A上要一步，然后要把n-1 个碟子再移到B上，又要a（n-1）步。（为什么这样呢，这样就好像直接从B上的最下面抽出来放在A上一样）
即an=2a（n-1）+1，可得an+1=2[a（n-1）+1].其中a1+1=2
所以an+1=（a1+1）×2^（n-1）=2^n
即an=2^n-1
a1=2-1,a2=2^2-1满足要求.
当n=4时，a4=2^4-1=15