題目描述
在一無(wú)限大的二維平面中，我們做如下假設(shè)：
1烹卒、每次只能移動(dòng)一格闷盔；
2、不能向后走（假設(shè)你的目的地是“向上”旅急，那么你可以向左走逢勾，可以向右走，也可以向上走藐吮，但是不可以向下走）溺拱；
3、走過(guò)的格子立即塌陷無(wú)法再走第二次谣辞。
求走n步不同的方案數(shù)（2種走法只要有一步不一樣迫摔，即被認(rèn)為是不同的方案）。
輸入
首先給出一個(gè)正整數(shù)C泥从，表示有C組測(cè)試數(shù)據(jù)句占。
接下來(lái)的C行，每行包含一個(gè)整數(shù)n（n<=20）躯嫉，表示要走n步纱烘。
輸出
請(qǐng)編程輸出走n步的不同方案總數(shù)；
每組的輸出占一行祈餐。
我們通過(guò)分析可以得到擂啥，這題也是屬于遞歸調(diào)用。既然是遞歸算法帆阳，那就是兩個(gè)步驟哺壶，第一步 確定終止條件，并看看特殊情況，第二部找出遞推關(guān)系式变骡。
本題的終止條件肯定是n=1時(shí)候离赫，有左中右三種方法，而n=2時(shí)候塌碌，是在1的基礎(chǔ)上繼續(xù)走渊胸，和n=3 n=4 等等是一樣的，因此該題并沒(méi)有什么特殊條件可以直接退出遞歸條件台妆。
第二步就是找出遞歸表達(dá)式翎猛。本題看上去是簡(jiǎn)單的，結(jié)論也是簡(jiǎn)單的接剩，但是思考的過(guò)程并不簡(jiǎn)單切厘。
一開(kāi)始我們可以有三種走法，向左向右向上懊缺，進(jìn)行分類討論疫稿，若是向左或向右走的話，那么僅有2種走法鹃两，就是繼續(xù)向左或向右走遗座，或者是向上。 而若是向上走的話俊扳，那么它就可以繼續(xù)有三種走法途蒋，向左向右向上，這里我們似乎要分類討論馋记，但其實(shí)不用号坡。
在研究走n步的條件下，我們可以很明顯的看出梯醒，一直向上走走到n-1步時(shí)候宽堆，才會(huì)發(fā)生可以走三步的抉擇（因?yàn)橐恢毕蛏希宰笥冶囟](méi)棋子走過(guò)冤馏，可以走）日麸，其他任何情況都只會(huì)在走n-1步后發(fā)生走兩步的抉擇，要么向上逮光，要么走左或者向右代箭。
所以特殊情況可以走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<<"請(qǐng)輸入需要的數(shù)據(jù)總量"<<endl;
cin>>C;
for(int i=0;i<C;i++)
{
int n;
cout<<"請(qǐng)輸入步長(zhǎng)n,還剩"<<C-i<<"次輸入"<<endl;
while(cin>>n,n>20)
{
cout<<"請(qǐng)重新輸入n"<<endl;
}
cout<<fun(n)<<endl;
}
}
