MENU

# 汉诺塔一系列问题(未完)

September 22, 2020 • Read: 61 • c/c++基本算法

1、表述

​ 最近在都是在hdu上刷到几个关于汉诺塔的问题,结合递推,总是有点糊涂,就打算记下来,慢慢理解。(本人由于脑子不够好使,可能需要看很多次)来吧,下面上正题。先进行比较简单的汉诺塔问题

首先给出这些题目的链接,有兴趣的同学可以做一下
hdu2064
hdu2077

2、汉诺塔一

//初见汉诺塔3
请输入图片描述

/*

假设将n层塔从A经B挪到C需要f[n]步。那么具体的移动过程可以这样看:将上面n-1层从A经B挪到C需要f[n-1]步,再将第n层从A挪到B,需要一步,再将上n-1层从C经B挪到A,需要f[n-1]步,再将第n层从B挪到C,需要一步,再将上n-1层从A经B挪到C,需要f[n-1]步,总计3*f[n-1] + 2步,其中 f[1] = 2;

*/

\#include <bits/stdc++.h>

using namespace std;

int main()

{

  int n,f(n);

  while(~scanf("%d",&n))

  {

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

   {

     if(i==1) 

     {

       f(1)=2;

       printf("%d\n",f(n));

       break;

     }

      f(n)=3*f(n-1)+2;

    }

  }

}

汉诺塔二

//又见汉诺塔4

请输入图片描述

1、本题是上一题的升级版。设上一题n个盘子的移动数目为F(n)

2、移动的过程如下:

(1)把n-2个盘子从A经过B移动到C -> F(n-2);

(2)把第n-1个盘子从A移动到B -> 1;

(3)把第n个盘子从A移动到B -> 1;

(4)把n-2个盘子从C经过B移动到A ->F(n-2);

(5)把第n个盘子从B移动到C -> 1;

(6)把第n-1个盘子从B移动到C -> 1;

(7)把n-2个盘子从A移动到C -> F(n-2)。

3、综上,本题n个盘子的移动数目f(n)=F(n-2)+4,又因为F(n-1)=3*F(n-2)+2(在二百题中已经得出结论),所以f(n)=F(n-1)+2

* /

#include <iostream>

#include <cstring>

    using namespace std;

typedef long long LL;

const int MAX = 21;

int main()
{

    LL a[MAX];

    memset(a, 0, sizeof(a));

    for (int i = 1; i < MAX; i++)
    {

         a[i] = 3 * a[i - 1] + 2;
    }

    int T;

    cin >> T;

    for (int i = 0; i < T; i++)
    {

         int n;

        cin >> n;

        LL ans = a[n - 1] + 2;

        cout << ans << endl;
    }

    return 0;
}