P1096 Hanoi 双塔问题【洛谷算法习题】

P1096 Hanoi 双塔问题网页链接P1096 Hanoi 双塔问题题目描述给定 A、B、C 三根足够长的细柱在 A 柱上放有2 n 2n2n个中间有孔的圆盘共有n nn个不同的尺寸每个尺寸都有两个相同的圆盘注意这两个圆盘是不加区分的下图为n 3 n3n3的情形。现要将这些圆盘移到 C 柱上在移动过程中可放在 B 柱上暂存。要求每次只能移动一个圆盘A、B、C 三根细柱上的圆盘都要保持上小下大的顺序。任务设A n A_nAn​为2 n 2n2n个圆盘完成上述任务所需的最少移动次数对于输入的n nn输出A n A_nAn​。输入格式一个正整数n nn表示在 A 柱上放有2 n 2n2n个圆盘。输出格式一个正整数, 为完成上述任务所需的最少移动次数A n A_nAn​。输入输出样例 #1输入 #11输出 #12输入输出样例 #2输入 #22输出 #26说明/提示限制对于50 % 50\%50%的数据1 ≤ n ≤ 25 1 \le n \le 251≤n≤25对于100 % 100\%100%的数据1 ≤ n ≤ 200 1 \le n \le 2001≤n≤200。提示设法建立A n A_nAn​与A n − 1 A_{n-1}An−1​的递推关系式。解题思路本题核心是递推公式推导高精度大数计算求解双塔汉诺塔最小移动次数。对比经典汉诺塔双塔每个尺寸有两个相同圆盘推导得递推关系A ( n ) 2 × A ( n − 1 ) 2 A(n) 2 \times A(n-1) 2A(n)2×A(n−1)2初始条件A ( 1 ) 2 A(1)2A(1)2化简通项公式为A ( n ) 2 n 1 − 2 A(n) 2^{n1} - 2A(n)2n1−2。由于n ≤ 200 n \le 200n≤2002 201 2^{201}2201是远超整型范围的超大数必须通过高精度运算计算结果。通过数学公式将递归问题转化为幂次计算大幅简化逻辑配合高精度处理大数时间复杂度极低完美适配题目数据范围保证结果准确无误。总结核心逻辑推导双塔汉诺塔的通项公式A ( n ) 2 n 1 − 2 A(n) 2^{n1} - 2A(n)2n1−2通过高精度运算求解超大数结果。关键操作根据递推关系得出数学通项处理大数幂次计算并完成减2操作。效率保障数学公式直接求解无递归冗余计算高精度运算适配n≤200的最大数据规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e610;constll p1e97;constll INF1e18;constll M5e310;intmain(){ll n;cinn;stringstream s;s.precision(0);sfixedpow(2.0L,n1);string as.str();a[a.length()-1]--;a[a.length()-1]--;coutaendl;return0;}