突破蝙蝠的包圍，yifenfei來到一處懸崖面前，懸崖彼岸就是前進的方向，好在現在的yifenfei已經學過御劍術，可御劍輕松飛過懸崖。

現在的問題是：懸崖中間飛著很多紅，黃，藍三種顏色的珠子，假設我們把懸崖看成一條長度為n的線段，線段上的每一單位長度空間都可能飛過紅，黃，藍三種珠子，而yifenfei必定會在該空間上碰到一種顏色的珠子。如果在連續3段單位空間碰到的珠子顏色都不一樣，則yifenfei就會墜落。

比如經過長度為3的懸崖，碰到的珠子先后為 “紅黃藍”，或者 “藍紅黃” 等類似情況就會墜落，而如果是 “紅黃紅” 或者 “紅黃黃”等情況則可以安全到達。

現在請問：yifenfei安然抵達彼岸的方法有多少種？

Input輸入數據首先給出一個整數C，表示測試組數。

然后是C組數據，每組包含一個正整數n (n<40)。

Output對應每組輸入數據，請輸出一個整數，表示yifenfei安然抵達彼岸的方法數。

每組輸出占一行。

Sample Input2
2
3Sample Output9
21

1.如果第n-1個珠子與第n-2個珠子相同的時候,第n顆珠子有的方式為 a[n] = a[n-2] * 3;

2.如果第n-1個珠子與第n-2個珠子不同的時候,第n顆珠子只能為其中的兩種顏色 :
a[n] = (a[n-1] - a[n-2]) * 2;

綜上:a[n] = a[n-2] * 3 + ((a[n-1] - a[n-2]) * 2) = a[n-1] * 2 + a[n-2] ;

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N=40; typedef long long LL; LL f[N]; void maketable(){f[1]=3;f[2]=9;for(int i=3;i<=N;i++)f[i]=f[i-2]+f[i-1]*2; } int main(){maketable();int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);printf("%lld\n",f[n]);}return 0; }

總結

以上是生活随笔為你收集整理的彼岸-递归-打表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。