分治算法：汉诺塔问题思维导图

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

设输入的左中右三个杆分别为a，b，c。题目要将摞在a杆上的n层汉诺塔移动到b杆上，在这一过程会借助c杆。

n个圆盘从源#a上移动到目标柱上，经过过波柱C

递归问题：将x杆上的k层汉诺塔移动到y杆上，在这一过程中会借助z杆。

递归关系：要想将x杆上的k层汉诺塔移动到y杆，可以先将x杆上的k-1层汉诺塔移动到z杆，借助y杆。

递归出口：如果要移动的是0层汉诺塔，那么就不移动了。

由于输出数据较多，如果用cout输出可能会超时，要使用scanf与printf。

输出k层汉诺塔从x杆移动到y杆借助z杆的解法

将k-1层汉诺塔从x杆移动到z杆借助y杆

输出将k号圆盘从x移动到y

将k-1层汉诺塔从z杆移动到y杆借助x杆

可以发现规律，左上等于右下，右上等于左下把整个大矩阵分成最小的一块，也就是1个1，然后慢慢再合并成一个大矩阵

从八位选手的循环比赛表中可以看出，这是一个具有对称性的方阵，可以把方阵一分为四来看，那么左上角的 4×4 的方阵就是前四位选手的循环比赛表，而右上角的 4*4 的方阵就是后四位选手的循环比赛表，它们在本质上是一样的，都是4 个选手的循环比赛表，所不同的只是选手编号不同而已，将左上角中方阵的所有元素加上 4 就能得到右上角的方阵。下方的两个方阵表示前四位选手和后四位选手进行交义循环比赛的情况，同样具有对称性，将右上角方阵复制到左下角即得到1、2、3、4 四位选手和 5、6、7、8 四位选手的循环比赛表，根据对称性，右下角的方阵应与左上角的方阵相同。这样，八名选手的循环比赛表可以由四名选手的循环比赛表根据对称性生成出来.同样地，四名选手的循环比赛表可以由二名选手的循环比赛表根据对称性生成出来，而两名选手的循环比赛表可以说是已知的，这种程序设计方法叫做分治法，其基本思想是把一个规模为 n 的问题分成若干个规模较小的问题，使得从这些较小问题的解易于构造出整个问题的解。

根据样例可以发现4,5(n,n+1).9,10(2n+1,2n+2); 第二行的右边第一行的左边。第二 行的 左边第一行右边都是-1

当n>4时我们尽量让n递归到4。

每当n>4的时候就会多出来两行。