遞歸--練習11--noi9273 PKU2506Tiling

遞歸--練習11--noi9273 PKU2506Tiling

一、心得

25 a[i]%=10;（高精度時）
 26 這裡錯了，花了好久改好 
 27 
 28 
 29 int* f(int n){
 30     if(dp[n][0]!=0) return dp[n];
 31     else if(0==n) return dp[0];
 32     else if(1==n) return dp[1];
 33     else{
 34         
 35         give(jia(f(n-1),chen(f(n-2),2)),dp[n]);
 36         return dp[n];
 37     }
 38 } 
 39 直接這樣寫的話f(n-1)那些的值一直被改變 ,指針需要去看看
 40 二維指針就是位址 
 41 
 42 整個測試有多組資料，請做到檔案底結束。
 43 while(scanf("%d",&n)!=EOF){      

二、題目

9273:PKU2506Tiling

總時間限制: 

2000ms 單個測試點時間限制: 

1000ms 記憶體限制: 

131072kB

描述

對于一個2行N列的走道。現在用1*2,2*2的磚去鋪滿。問有多少種不同的方式。

下圖是一個2行17列的走道的某種鋪法。

輸入

整個測試有多組資料，請做到檔案底結束。每行給出一個數字N，0 <= n <= 250

輸出

如題

樣例輸入

2
8
12
100
200      

樣例輸出

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251      

三、AC代碼

1 /*
  2 noi9273 PKU2506Tiling
  3 
  4 就是好好找子問題就好了
  5  
  6 找出遞推關系式即可：
  7 第一塊1*2橫放：
  8 f(n)=f(n-2)
  9 第一塊1*2豎放：
 10 f(n)=f(n-1) 
 11 第一塊2*2：
 12 f(n)=f(n-2)
 13 
 14 故f(n)=f(n-1)+2*f(n-2);
 15 邊界條件
 16 f(0)=1
 17 f(1)=1
 18 f(2)=3 
 19 
 20 高精度 (用個2維數組把每一個數的每一位都存下來即可)
 21 其實加和乘裡面隻需要有加，因為乘2完全可以看成想加 
 22 記憶化遞歸 
 23 
 24 
 25 a[i]%=10;
 26 這裡錯了，花了好久改好 
 27 
 28 
 29 int* f(int n){
 30     if(dp[n][0]!=0) return dp[n];
 31     else if(0==n) return dp[0];
 32     else if(1==n) return dp[1];
 33     else{
 34         
 35         give(jia(f(n-1),chen(f(n-2),2)),dp[n]);
 36         return dp[n];
 37     }
 38 } 
 39 直接這樣寫的話f(n-1)那些的值一直被改變 ,指針需要去看看
 40 二維指針就是位址 
 41 
 42 整個測試有多組資料，請做到檔案底結束。
 43 while(scanf("%d",&n)!=EOF){
 44 */
 45 #include <iostream>
 46 #define Max 300
 47 using namespace std;
 48 int dp[Max][Max];//用個2維數組把每一個數的每一位都存下來
 49 //列印結果 
 50 void print(int dp[]){
 51     for(int i=dp[0];i>=1;i--){
 52         cout<<dp[i];
 53     }
 54     cout<<endl;
 55 }
 56 //高精度乘單精度 
 57 int* chen(int a[],int b){
 58     //乘 
 59     for(int i=1;i<=a[0];i++){
 60         a[i]*=b;
 61     } 
 62     //處理進位
 63     for(int i=1;i<=a[0];i++){
 64         if(a[i]>=10){
 65             a[i]%=10;
 66             a[i+1]++;
 67         }
 68     }  
 69     //更正位數
 70     while(a[a[0]+1]>0) a[0]++; 
 71     return a;
 72 } 
 73 //高精度加法 
 74 int* jia(int a[],int b[]){
 75     if(a[0]<b[0]) a[0]=b[0];
 76     //加
 77     for(int i=1;i<=a[0];i++){
 78         a[i]+=b[i];
 79     } 
 80     //處理進位
 81     for(int i=1;i<=a[0];i++){
 82         if(a[i]>=10){
 83             a[i]%=10;
 84             a[i+1]++;
 85         }
 86     } 
 87     //更正位數
 88     while(a[a[0]+1]>0) a[0]++; 
 89     return a;
 90 
 91 }
 92 //指派，把ans數組的值全部給dp數組 
 93 void give(int ans[],int dp[]){
 94     for(int i=0;i<=ans[0];i++){
 95         dp[i]=ans[i];
 96     }
 97 } 
 98 int* f(int n){
 99     if(dp[n][0]!=0) return dp[n];
100     else if(0==n) return dp[0];
101     else if(1==n) return dp[1];
102     else{
103         int tmp_1[Max]={0};
104         int tmp_2[Max]={0};
105         give(f(n-1),tmp_1);
106         give(f(n-2),tmp_2);
107         give(jia(tmp_1,chen(tmp_2,2)),dp[n]);
108         return dp[n];
109     }
110 } 
111 
112 int main(){
113     dp[0][0]=1,dp[0][1]=1;//前面是位數，後面是數 
114     dp[1][0]=1,dp[1][1]=1;
115     int n=100;
116     while(scanf("%d",&n)!=EOF){
117         f(n);
118         print(dp[n]); 
119     }
120     return 0;
121 }      

 ​