六行0ms汉诺塔

通项公式是2^（n-1），只要算出前面几项就易得这个公式。接下来就是证明这个公式 类似问题的证明法在网上有很多，不过通过二进制证明的思路应该还没有至少我只在3B1B那里看到 所以这里就把他的思路证明抄搬过来 解题的关键是在于二进制数数时的“节奏”，在十进制中数数的节奏是数1~9，然后在下一位十位用1表示，清空后面的数，在百位千位上也相似，在更大的位数上进一，清空后面的数。那么在二进制的节奏中，数完0,1那么就必须进一变成10（即一个二加上一个0,12+0,类似地，100表示为14+0*2+0）十进制中的数表示为10的幂，那么二进制中的数位也表示为二的幂，十进制中有十位，百位，千位那么二进制中就有二位，四位，八位。那么在二进制中数到三可理解为：在00中，后一位数到1，进二位，后一位再数1，扩大到255，则先让00000000中后七位数到127，进到128位，后7位再数到127。那么二进制数数的节奏与汉诺塔的关系的联系又在哪里呢？我们可以通过二进制这么表示汉诺塔中金片的移动：，三根柱子标为1,2,3,初始所有金片都在1上，将金片从小到大标为0~n-1，当标为0的金片移动时，用于表示金片移动的二进制数的最后一位加一，假设它移动到柱2，那么接下来就得移动金片1，使其在柱3，这时二进制数变为010，再移动金片0到金片1上，数字变为011，移动金片2到柱2上，数变为0100，将0,1金片移到3上，数变为0111，可以见得如果你想移动第m片到柱3，必须先将0~m-1片移动到柱2，于是二进制中第一位到第2^（m-1）位变为1，接下来移动第m片到柱3，2^m位加1，1~2^(m-1)位清零。，接下来是第(m-1)个移动到柱3，那么(m-2)就得移动到柱1......以此类推，那么我们就找到了递归的一个方法。移动完时，数字变为了第2^n位为1，其余为0，再根据位运算规则即可推出2^(n-1)这个公式