1109Hanoi双塔问题(利用一维数组存储结果）

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main()

{

long long n;

cin >> n;

//设计一个数组，将一个非常大的数，通过数组的形式存起来，

int arr[1005] = { 0 };

// 0 和 1 的情况单独拿出来，这是个人习惯

if (n == 0)

{

cout << "0";

return 0;

}

else if (n == 1)

{

cout << "2";

return 0;

}

//这里是 n 大于等于 2 的情况

//下面的思路就是，arr[0]的位置我们不管，将 arr[1]的值设为 1，这样是为了与 n 的值相呼应

// 好啦，我们开始分析题目，这时经典的汉罗塔问题，只不过这里有一点点不同

//不同点在于，它的最后的结果是 普通汉罗塔的两倍

//那我们就可以先求出普通汉罗塔在 n 时的值，最后再乘以 2 就搞定啦！

//普通汉罗塔的规律就是 后一个数 = 前一个数 * 2 + 1；

//可以看出是一个非常简单的递归求解的问题

//但是，这道题有一个非常恶心人的地方，这个 n 的值非常非常大，long long 也过不了！

//这时问题就转化为如何将一个非常非常大的数存起来并输出它

//这有很多办法，例如自定义函数，高精度算法，调用库函数等等，这些可以去看那些大佬的题解了

//而我使用的是利用数组存储

//第一步，先将arr[]上每个位置上的数都 乘以 2 ，数学上一个数乘以 2 等于它每个位数上的数乘以 2 再相加

//第二步，将arr[1]加+1；

//第三步，一个位数上的数如果大于 10 了，这时我们需要进一位，也就是arr[i]-=10  arr[i+1]+=1;

//这样我们就完成一次递归的操作啦！

//而这样的操作我们需要完成(n-1)次，所以我是从 j=2 开始到 j=n 结束的。

else

{

arr[1] = 1;

for (int j = 2; j <= n; j++)

{

for (int i = 1; i <= n; i++)

{

arr[i] *= 2;

}

arr[1] += 1;

for (int i = 1; i <= n; i++)

{

if (arr[i] >= 10)

{

arr[i] -= 10;

arr[i + 1] += 1;

}

}

}

}

//上面的步骤就是求得普通汉罗塔在 n 时的值，接下来我们需要对它进行 乘以 2 的操作，得到我们需要的值

for (int i = 1; i <= n; i++)

{

arr[i] *= 2;

}

for (int i = 1; i <= n; i++)

{

if (arr[i] >= 10)

{

arr[i] -= 10;

arr[i + 1] += 1;

}

}

//上面得到我们想要的之后，我们输出发现结果里面有很多 0 ，我们还需要将这些 0 去掉

//这很简单，找到第一个不是 0 的数的下标，记录一下，再从这个下标开始输出，就完成啦！

int j = 0;

for (int i = n+1 ; i > 0; i--)

{

if (arr[i] != 0)

{

j = i;

break;

}

}

for (int i = j; i > 0; i--)

{

cout << arr[i];

}

return 0;

}