题目描述
在一无限大的二维平面中，我们做如下假设：
1、每次只能移动一格；
2、不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、走过的格子立即塌陷无法再走第二次。
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
输入
首先给出一个正整数C，表示有C组测试数据。
接下来的C行，每行包含一个整数n（n<=20），表示要走n步。
输出
请编程输出走n步的不同方案总数；
每组的输出占一行。

我们通过分析可以得到，这题也是属于递归调用。既然是递归算法，那就是两个步骤，第一步 确定终止条件，并看看特殊情况，第二部找出递推关系式。
本题的终止条件肯定是n=1时候，有左中右三种方法，而n=2时候，是在1的基础上继续走，和n=3 n=4 等等是一样的，因此该题并没有什么特殊条件可以直接退出递归条件。
第二步就是找出递归表达式。本题看上去是简单的，结论也是简单的，但是思考的过程并不简单。
一开始我们可以有三种走法，向左向右向上，进行分类讨论，若是向左或向右走的话，那么仅有2种走法，就是继续向左或向右走，或者是向上。 而若是向上走的话，那么它就可以继续有三种走法，向左向右向上，这里我们似乎要分类讨论，但其实不用。
在研究走n步的条件下，我们可以很明显的看出，一直向上走走到n-1步时候，才会发生可以走三步的抉择（因为一直向上，所以左右必定没棋子走过，可以走），其他任何情况都只会在走n-1步后发生走两步的抉择，要么向上，要么走左或者向右。
所以特殊情况可以走3 步 也就是 2+1，而普通情况只要考虑两种走法。因此本题的递推公式也很容易的可以合并成
f(n)=2*f(n-1)+1
代码如下

#include<iostream>
using namespace std;
int fun(int n)
{
    if(n==1) return 3;
    else
    return 2*fun(n-1)+1; 

}
int main()
{
    int C;
    cout<<"请输入需要的数据总量"<<endl;
    cin>>C;
    
    for(int i=0;i<C;i++)
    {
        int n;
        cout<<"请输入步长n,还剩"<<C-i<<"次输入"<<endl;
        while(cin>>n,n>20)
        {
            cout<<"请重新输入n"<<endl;
        }
        cout<<fun(n)<<endl;
            
    } 
}