2_03

辽宁师范大学 • 张大为@https://daweizh.github.io/noip/

2.3 基本算法之递归变递推(6)

菲波那契数列(2)，http://noi.openjudge.cn/ch0203/1760/[+]

#include <iostream>
using namespace std;

int mod = 1000;

int fb(int n){
  int first=1,second=1,ans=0;
  if(n==1 || n==2)
    ans = 1;
  for(int i=3;i<=n;i++){
    ans = (first%mod + second%mod)%mod;
    first =second;
    second = ans;
  }
  return ans;
}

int main(){
  int t,a;
  
  cin >> t;
  while(t--){
    cin >> a;
    cout << fb(a) << endl;
  }
  
  return 0;
}

Pell数列，http://noi.openjudge.cn/ch0203/1788/[+]

#include <iostream>
using namespace std;

long long n,x,mod=32767;

int pell(int p){
  int a=1,b=2,c=0;
  
  if(p==1) c=a; 
  if(p==2) c=b;
  for(int i=3;i<=p;i++){
    c = (2*b+a)%mod;
    a=b;
    b=c;
  }
  return c;
}

int main(){
  cin >> n;
  
  for(int i=0;i<n;i++){
    cin >> x;
    cout << pell(x) << endl;
  }
  
  return 0;
}

上台阶，http://noi.openjudge.cn/ch0203/3525/[+]

#include <iostream>
using namespace std;

int n;

int stg(int s){
  int a=1,b=2,c=4,d=0;
  if(s==1) d=a; 
  if(s==2) d=b; 
  if(s==3) d=c; 
  for(int i=4;i<=n;i++){
    d = a+b+c;
    a=b;
    b=c;
    c=d;
  }
  return d;
}

int main(){
  cin >> n;
  
  while(n!=0){
    cout << stg(n) << endl;
    cin >> n;
  }
  
  return 0;
}

流感传染，http://noi.openjudge.cn/ch0203/6262/[+]

#include <iostream>
using namespace std;
int n,d,ans=0;
char room[2][110][110];

void sct(int t){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(room[t%2][i][j]=='@'){
        if(i-1>=0&&room[(t+1)%2][i-1][j]=='.'){
          room[(t+1)%2][i-1][j]='@';
        }
        if(i+1<n&&room[(t+1)%2][i+1][j]=='.'){
          room[(t+1)%2][i+1][j]='@';
        }
        if(j-1>=0&&room[(t+1)%2][i][j-1]=='.'){
          room[(t+1)%2][i][j-1]='@';
        }
        if(j+1<n&&room[(t+1)%2][i][j+1]=='.'){
          room[(t+1)%2][i][j+1]='@';
        }
      }
    }
  }
}

int main(){
  
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> room[0][i];

  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      room[1][i][j]=room[0][i][j];
        
  cin >> d;
  for(int i=0;i<d-1;i++)
    sct(i);
    
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(room[(d-1)%2][i][j]=='@')
        ans++;
  
  cout << ans << endl;

  return 0;
}

放苹果，http://noi.openjudge.cn/ch0203/666/[+]

#include <iostream>
using namespace std;

int n,apple,disk;

int divide(int apl,int dsk){
    int mat[apl+1][dsk+1];
  for(int i=0; i<=apl; i++) {
      mat[i][0]=0;
      mat[i][1]=1;
  }
  for(int i=0; i<=dsk; i++) {
      mat[0][i]=1;
  }
  for (int i=1; i<=apl; i++) {
      for(int j=1; j<=dsk; j++) {
          if(i<j)
              mat[i][j]=mat[i][i];
          else
              mat[i][j]=mat[i][j-1]+mat[i-j][j];
      }
  }
  return mat[apl][dsk];       	
}

int main(){
  cin >> n;
  
  for(int i=0;i<n;i++){
    cin >> apple >> disk;
    cout << divide(apple,disk) << endl;		
  }	

  return 0;
}

PKU2506Tiling，http://noi.openjudge.cn/ch0203/9273/[+]

#include <iostream>
#include <cstring>
using namespace std;

int len[255],a[255][305],n,k;

int main(){
  memset(a,0,sizeof(a));
  memset(len,1,sizeof(len));
  a[0][1]=1;
  a[1][1]=1;
  
  //先求一遍 
  for(int i=2;i<=250;i++){
    for(int j=1;j<=300;j++){
      a[i][j]+=a[i-1][j]+a[i-2][j]*2; //对应位相加 
      if(a[i][j]>=10){				//处理进位 
        a[i][j+1]=a[i][j]/10;
        a[i][j]=a[i][j]%10;
      }
    }
    for(k=300;k>=1;k--){
      if(a[i][k]>0)
        break;
    }
    len[i]=k;
  }
  
  //再枚举先要找的
  while(cin >> n){
    if(n>1){
      for(int i=len[n];i>=1;i--)
        cout << a[n][i];
      cout << endl; 
    }else{
      cout << 1 << endl;
    }	
  }

  return 0;
}

参考网址

http://noi.openjudge.cn