A deformation problem of Hanoi Tower

Title Description

Sugar and shake m Playing a game , It is stipulated that whoever loses will be invited to a big meal ： Shaking, m Give me sugar a b c Three stations , And in a Put the number of columns on n The disk of , The size of the disc increases from top to bottom , What we have to do now is to a Move all the disks of the column to c column , Keep the small disk on the during the movement , The market is under , And it is limited that the disc can only move to the adjacent column , namely a The disk on the column can only move to b,b The disk on the column can only move to a perhaps c,c Empathy . Now please design a program , Calculate the minimum number of steps to move , Help sugar win a big meal ！

Input description ：

Each line of output has an integer n(0<=n<26), Up to the end of the file .

Output description ：

For each set of data , Output one line , Output the minimum number of steps to move M.

Examples 1：

Input ：

1

Output ：

2

Their thinking ： recursive .

Take a few examples ：n=1 when , We need to move the disc from a The column moves to b column , Again from b The column moves to c column , You need to move two steps .n=2 when , Let's take the small disc from a The column moves to c column , according to n=1 The conclusion is that 2 Step ; At this time, turn the large disc from a The column moves to b column , They count +1; Then turn the small disc from c The column moves to a column , They count +2; then b The big disk of the column moves to c column , They count +1; Finally, remove the small disc from a The column moves to c column , They count +2, The total number of steps is 8 Step .n=3 when , And so on .

We can find out , Every time, I will n-1 A disk from a The column moves to c column ,b Columns are buffers ; And then n A disk from a Move to b, They count +1; then n-1 A disk from c Move to a,b Columns are buffers ; And then n A disk from b Move to a, They count +1; The final will be n-1 A disk from a Move to c, Complete the move . And this n-1 The number of steps a disc moves also satisfies this law , So you can write the following code ：

#include<iostream>
using namespace std;
int sum=0;
void move(int from,int buffer,int to,int n){
	if(n>0){
		move(from,buffer,to,n-1);// from a Move to c,b For buffer 
		sum++;
		move(to,buffer,from,n-1);// from c Move to a,b For buffer 
		sum++;
		move(from,buffer,to,n-1);// from a Move to c,b For buffer 
	}
}
int main(){
	int n;
	while(cin>>n){
		sum=0;// Move steps 
		move(1,2,3,n);// Represent the a column 、b column 、c Number of columns and discs 
		cout<<sum<<endl;
	}
	return 0;
}

Of course ,from、buffer and to Just to help understand , It doesn't matter if you don't write it into recursion , After all, the point is right n Do recursion .

In addition to the recursive approach , You can also find rules directly . The code is as follows ：

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n,i;
    while(cin>>n){
        int sum=0;
        for(i=0;i<n;i++){
            sum+=pow(3,i);
        }
        cout<<sum*2<<endl;
    }
    return 0;
}

No secret , I started by looking for rules , Instead, it took a long time to understand the recursive method ......（ My strange brain circuit ......）