递归算法

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

1. 前n项和

给定n(n>=1)，用递归的方法计算1+2+3+...+(n-1)+n。

2. 斐波那契数列

满足 F1=F2=1,Fn=F_n−1+F_n−2F_1 = F_2 = 1, F_n = F\_{n-1} + F\_{n-2} 的数列称为斐波那契数列(Fibonacci)，它的前若干项是1,1,2,3,5,8,13,21,34,....求词数列第n项(n>=3)。

3. 最大公约数

给定两个正整数a,b求它们的最大公约数gcd(a,b)。

4. 逆波兰式求解

逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。

  1. 输入：输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
  2. 输出：输出为一行，表达式的值。可直接用printf("%f\n", v)输出表达式的值v。
  3. 样例输入：* + 11.0 12.0 + 24.0 35.0
  4. 样例输出：1357.000000
  5. 提示：可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。此题可使用函数递归调用的方法求解。

5. 递归二分

设有n个数已经按从大到小的顺序排列，现在输入x，判断它是否在这n个数中，如果存在则输出“YES”，否则输出“NO”。

6. Hanoi 汉诺塔问题

有n个圆盘，依半径大小（半径都不同），自下而上套在a柱上，每次只允许移动最上面一个盘子到另外的柱子上去（除a柱外，还有b柱和c柱，开始时这两个柱子上无盘子），但绝不允许发生柱子上出现大盘子在上小盘子在下的情况。现要求设计将a柱子上n个盘子搬移到c柱去的方法。

7. 集合的划分

设S是一个具有n个元素的集合，S=a1,a2,...,anS=\\{a_1,a_2,...,a_n\\}，现将S划分成k个满足下列条件的子集合S1,S2,...,SKS_1,S_2,...,S_K，且满足：

  1. Si≠∅S_i \neq \emptyset
  2. Si⋂Sj=∅(1≤i,j≤k,i≠j)S_i \bigcap S_j = \emptyset (1 \leq i,j \leq k , i \neq j )
  3. S1⋃S2⋃S3⋃⋯⋃Sk=SS_1 \bigcup S_2 \bigcup S_3 \bigcup \cdots \bigcup S_k = S

则称S1,S2,S3,⋯ ,SkS_1,S_2,S_3,\cdots,S_k 是集合S的一个划分。他相当于把S集合中的n个元素 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 放入k个(0<k<=n<30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 放入k个无标号盒子中去的划分数S(n,k)。

8. 数的技术(Noip 2001)

我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n(n<=1000)，然后对此自然数按照如下方法进行处理：

  1. 不做任何处理
  2. 在它的左边加上一个自然数，但该自然数不能超过原数的一半
  3. 加上数后，继续按此规则进行处理，直到不能再加自然数为止

递归方法

记忆化搜索

递推方法一

h(i)=h(1)+h(2)+⋯+h(i/2)h(i)=h(1)+h(2)+ \cdots +h(i/2)

递推方法二

已知h(i)=h(1)+h(2)+⋯+h(i/2)h(i)=h(1)+h(2)+ \cdots +h(i/2)，
令s(x)=h(1)+h(2)+⋯+h(x)s(x)=h(1)+h(2)+ \cdots +h(x) ，
则h(x)=s(x)−s(x−1)h(x)=s(x)-s(x-1)，h(i)=1+s(i/2)h(i)=1+s(i/2)。

递推方法三

由h(1)=1,h(2)=2,h(3)=2,h(4)=4,h(5)=4,h(6)=6,h(7)=6,h(8)=10,h(9)=10,...,可知：

  1. h(i)=h(i-1)，当i为奇数时
  2. h(i)=h(i-1)+h(i/2)，当i为偶数时

Exercise

  1. 逆波兰表达式，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;
}
  2. 全排列，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;
}
  3. 分解因数，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;
}
  4. 菲波那契数列，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;
}
  5. 文件结构“图”，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;
}
  6. 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;
}
  7. 扩号匹配问题，http://noi.openjudge.cn/ch0202/2705/
    8. 

  8. 爬楼梯，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;
}

    9. 

  9. 汉诺塔问题，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;
}

    10. 

  10. 放苹果，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;
}

    11. 

  11. 求最大公约数问题，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;
}

    12. 

  12. 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;
}

    13. 

  13. PKU2506Tiling，http://noi.openjudge.cn/ch0202/9273/
    14. 



      

      



      ≡