2_02

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

2.2 基本算法之递归和自调用函数(13)

逆波兰表达式，http://noi.openjudge.cn/ch0202/1696/[+]

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string s;

double f(){
  cin >> s;
  if(s=="+") 		return f()+f();
  else if(s=="-") return f()-f();
  else if(s=="*") return f()*f();
  else if(s=="/") return f()/f();
  else return atof(s.c_str()); 
}

int main(){
  
  printf("%f",f());

  return 0;
}

全排列，http://noi.openjudge.cn/ch0202/1750/[+]

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

string s;
int f[10],len;
char ch[10];

void abc(int d){
  for(int i=0;i<len;i++){
    if(f[i]==0){
      f[i]=1;
      ch[d]=s[i];
      if(d==len-1){
        for(int j=0;j<len;j++)
          cout << ch[j];
        cout << endl;
      }else abc(d+1);
      f[i]=0;
    }
  }
}

int main(){
  cin >>s;
  len = s.size();
  abc(0);
  return 0;
}

分解因数，http://noi.openjudge.cn/ch0202/1751/[+]

#include <iostream>
using namespace std;

int n,x;

int dfs(int a,int b){
  if(a==1) return 1;
  if(b==1) return 0;
  if(a%b==0) return dfs(a/b,b)+dfs(a,b-1);
  return dfs(a,b-1);
} 

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

  return 0;
}

菲波那契数列，http://noi.openjudge.cn/ch0202/1755/[+]

#include <iostream>
using namespace std;

int n,a;

int fb(int x){
  int f0=1,f1=1,f2;
  for(int i=3;i<=x;i++){
    f2=f1+f0;
    f0=f1;
    f1=f2;
  }
  return f2;
}

int main(){
  cin >> n;
  while(n--){
    cin >> a;
    if(a<3)
      cout << 1 << endl;
    else
      cout << fb(a) << endl;
  }
  return 0;
}

文件结构“图”，http://noi.openjudge.cn/ch0202/1777/[+]

#include <iostream>
#include <string>
#include <set>
#include <cstdio>
using namespace std;

string s;
int grp=1;

void ds(int l){
  set<string> f;
  cin >> s;
  if(s[0]=='#') return;
  if(l==1){
    cout << "DATA SET " << grp << ":" << endl;
    cout << "ROOT" << endl;
  }
  do{
    if(s[0]=='f'){
      f.insert(s);
    } 
    else if(s[0]=='d'){
      for(int i=0;i<l;i++) 
        cout << "|     ";
      cout << s << endl;
      ds(l+1);
    }else if(s[0]==']'){
      break;
    }
    cin >> s;
  }while(s[0]!='*' && s[0]!=']');

  for(set<string>::iterator it=f.begin();it!=f.end();it++){
    for(int i=1;i<l;i++) cout << "|     ";
    cout << *it << endl;	
  }
}

int main(){
  do{
    ds(1);
    grp++;
    cout << endl;
  }while(s[0]!='#');

  return 0;
}

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

#include <iostream>
using namespace std;
const int mod = 32767;

int n,x,a[1000005];

int pell(int n){
  if(a[n]) return a[n];
  if(n==1) return 1;
  if(n==2) return 2;
  return a[n]=((pell(n-1) *2)%mod+ pell(n-2)%mod)%mod;
}

int main(){
  cin >> n;

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

扩号匹配问题，http://noi.openjudge.cn/ch0202/2705/[+]

#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
using namespace std;

string s;

bool tob(int pos){
  if(s[pos]>='a' && s[pos]<='z' || s[pos]>='A'&&s[pos]<='Z')
    return true;
  return false;	
}

int main(){
  //freopen("2705.in","r",stdin);
  
  while(cin >>s){
    cout << s << endl;
    stack<int> stk;
    for(int i=0;i<s.size();i++){
      if(tob(i)) s[i]=' ';
      else if(s[i]=='(') stk.push(i);
      else if(s[i]==')')
        if(stk.empty()) s[i]='?';
        else{ s[stk.top()]=' '; s[i]=' '; stk.pop();
        }
    }
    while(!stk.empty()){
      s[stk.top()]='$';
      stk.pop();
    }
    cout << s << endl;
  }
  
  return 0;
}

爬楼梯，http://noi.openjudge.cn/ch0202/3089/[+]

#include <iostream>
using namespace std;

int f(int n){
  if(n==1) return 1;
  if(n==2) return 2;
  return f(n-1) + f(n-2);
}

int x;

int main(){
  
  while(cin>>x){
    cout << f(x) << endl;
  }	

  return 0;
}

汉诺塔问题，http://noi.openjudge.cn/ch0202/6261/[+]

#include <iostream>
using namespace std;

int n;
char a,b,c;

void move(int n,char a,char c,char b){
  if(n==0) return;
  move(n-1,a,b,c);
  cout << a << "->" << n << "->" << c << endl;
  move(n-1,b,c,a);
}

int main(){
  
  cin >> n >> a >> b >> c;
  move(n,a,b,c);

  return 0;
}

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

#include <iostream>
using namespace std;


int apple(int a,int b){
  if(b==1 || a==0) return 1;
  if(b>a) return apple(a,a);
  return apple(a-b,b) + apple(a,b-1);	
}

int g,n,m;

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

  return 0;
}

求最大公约数问题，http://noi.openjudge.cn/ch0202/7592/[+]

#include <iostream>
using namespace std;

int gcd(int a,int b){
  int r = a%b;
  while(r){
    a=b;
    b=r;
    r=a%b;
  }
  return b;
}

int main(){
  int x,y;
  
  cin >> x >> y;
  cout << gcd(x,y) << endl;

  return 0;
}

2的幂次方表示，http://noi.openjudge.cn/ch0202/8758/[+]

#include <iostream>
using namespace std;

void pw(int x){
  int p=1,cnt=0;
  while(p<=x){
    p=p*2;
    cnt++;
  }
  if(cnt-1==0)
    cout << "2(0)" ;
  else if(cnt-1==1)
    cout << "2";
  else if(cnt-1==2)
    cout << "2(2)";
  else{
    cout << "2(" ;
    pw(cnt-1);
    cout << ")";
  }
  if(x-p/2>0){
    cout << "+";
    pw(x-p/2);
  }	
}

int main(){
  int n;
  
  cin >> n;	
  pw(n);

  return 0;
}

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

#include <iostream>
using namespace std;

int n,a[301][301];

int main(){
  a[0][300] = 1;
  a[1][300] = 1;
  a[2][300] = 3;
  for(int i=3;i<=250;i++){ //第i步 
    for(int j=300;j>0;j--){ //从低位向高位求和 
      a[i][j]+=a[i-1][j]+2*a[i-2][j];
      int r = a[i][j]%10;
      a[i][j-1]+=a[i][j]/10;
      a[i][j]=r;
      for(int k=1;a[i][j-k]>=10;k++){ //逐次进位 
        a[i][j-k-1]+=a[i][j-k]/10;
        a[i][j-k]=a[i][j-k]%10;
      }
    }
  }
  
  while(cin >> n){
    int k=0;
    while(a[n][k]==0) k++;
    for(int j=k;j<=300;j++)
      cout<<a[n][j];
    cout<<endl;
  }
  
  return 0;
}

参考网址

http://noi.openjudge.cn