递推算法

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

1. 数塔问题

如下图是一个数字三角形，请编写一个程序计算从顶到底的某一条路径，使该路径所经过的数字总和最大。只要求输出总和。

    5
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

用下图实际存储：

5
38
810
2744
45265

1. 逆推法[+]

   #include <iostream>
   using namespace std;
   
   int n,a[101][101];
   
   int main(){
   	cin >> n;
   	for(int i=0;i<n;i++){
   		for(int j=0;j<=i;j++){
   			cin >> a[i][j];
   		}
   	}
   
   	for(int i=n-2;i>=0;i--){
   		for(int j=0;j<=i;j++){
   			a[i][j] = max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
   		}
   	}
   	
   	cout << a[0][0] << endl;
   
   	return 0;
   }
   

2. 顺推法[+]

   #include <iostream>
   using namespace std;
   
   int n,a[101][101],f[101][101];
   
   int main(){
   	cin >> n;
   	for(int i=1;i<=n;i++){
   		for(int j=1;j<=i;j++){
   			cin >> a[i][j];
   		}
   	}
   	
   	f[1][1]=a[1][1];
   	for(int i=2;i<=n;i++)
   		for(int j=1;j<=i;j++){
   			f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];			
   		}
   	
   	int mx = 0;
   	for(int i=1;i<=n;i++)
   		if(f[n][i]>mx)
   			mx = f[n][i];
   			
   	cout << mx << endl;
   
   	return 0;
   }
   

2. 斐波那契数列

满足 $F_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)。

• [+]

  #include <iostream>
  using namespace std;
  
  int f0=1,f1=1,f2,n;
  
  int main(){
  	cin >> n;
  
  	for(int i=3;i<=n;i++){
  		f2=f0+f1;
  		f0=f1;
  		f1=f2;
  	}
  	cout << f2 << endl;
  	
  	return 0;
  }
  

有一个$2 \times n$的长方形方格，用一个$1\times2$的骨牌铺满方格。编写一个程序，试对给出的任意一个n(n>0)，输出铺法总数。

1. $2 \times 1 = 1$ |
2. $2 \times 2 = 2$ |,=
3. $2 \times 3 = 3$ |=,=|,|||
4. $2 \times 4 = 5$ ||||,||=,|=|,==,=||

总结规律：$x_1 = 1,x_2 = 2,x_3 = 3,x_4 = 5,....,x_n = x_{n-1} + x_{n-2}$

3. 最大公约数

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

• [+]

  #include <iostream>
  using namespace std;
  
  int a,b;
  
  int main(){
  	cin >> a >> b;
  	
  	int r = a%b;
  	while(r){
  		a=b;
  		b=r;
  		r=a%b;
  	}
  	cout << b << endl;
  	
  	return 0;
  }
  

4. 昆虫繁殖

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月每个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵（过X个月产卵），问过Z个月以后，共有成虫多少对？0<=x<=20,1<=y<=20,x<=z<=50。

• 输入格式： x y z
• 输出格式： 过z个月以后，共有成虫对数
• 输入样例： 1 2 8
• 输出样例： 37
• 参考代码： [+]

  #include <iostream>
  using namespace std;
  
  int x,y,z,a[101],b[101];
  
  int main(){
  	cin >> x >> y >> z;
  	
  	for(int i=1;i<=x;i++){
  		a[i]=1;
  		b[i]=0;
  	}
  	for(int i=x+1;i<=z+1;i++){
  		b[i] = a[i-x] * y;
  		a[i] = a[i-1] + b[i-2];
  	}
  	cout << a[z+1] << endl;
  	
  	return 0;
  }
  

5. 位数问题

在所有的n位数中，有多少个数中有偶数个数字3？由于结果可能很大，你需要输出这个答案对12345取余的值。

• 输入格式：读入一个数n
• 输出格式：输出有多少个数中有偶数个数字3。
• 输入样例：2
• 输出样例：73
• 数据范围：1<=n<=1000
• 样例说明：所在所有的2位数中，包含0个3的数有72个，包含2个3的数有1个，共73个。
• 参考代码：[+]

  #include <iostream>
  using namespace std;
  
  int n,odd[101],even[101],x;
  
  int main(){
  	odd[1]=1;
  	x=even[1]=9;
  	cin >> n;
  	
  	for(int i=2;i<=n;i++){
  		if(i==n) x--; //去掉首位为0的情况 
  		odd[i] = odd[i-1]*x + even[i-1];
  		even[i] = odd[i-1] + even[i-1]*x;
  	}
  	cout << even[n] << endl; 
  
  	return 0;
  }
  

6. 打印杨辉三角

输入层数n，生成n层杨辉三角，如当n=10时的杨辉三角如下图：

                   1
                 1   1
               1   2   1
             1   3   3   1
           1   4   6   4   1
         1   5  10  10   5   1
       1   6  15  20  15   6   1
     1   7  21  35  35  21   7   1
   1   8  28  56  70  56  28   8   1
 1   9  36  84 126 126  84  36   9   1

Exercise

1. HUSTOJ-1323:杨辉三角形，http://www.hustoj.com/oj/problem.php?id=1323[+]

   #include <iostream>
   using namespace std;
   
   int n,a[2][100];
   
   int main(){
   	cin >> n;
   	if(n>=1)
   		cout << 1 << endl;
   	if(n>=2)
   		cout << "1 1" << endl;
   	a[0][1]=1;
   	a[0][2]=1;
   	for(int i=3;i<=n;i++){
   		a[i%2][1]=1;
   		a[i%2][i]=1;
   		for(int j=2;j<i;j++){
   			a[i%2][j] = a[(i-1)%2][j-1]+a[(i-1)%2][j];
   		}
   		cout << a[i%2][1];
   		for(int j=2;j<=i;j++)
   			cout << " " << a[i%2][j];
   		cout << endl;
   	}
   
   	return 0;
   }
   

2. OPENJUDGE-1760:菲波那契数列(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;
   }
   

3. OPENJUDGE-1788: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;
   }
   

4. OPENJUDGE-3525:上台阶，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;
   }
   

5. OPENJUDGE-6262:流感传染，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;
   }
   

6. OPENJUDGE-666:放苹果，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;
   }
   

   将这8组数分成2组
   第一组，可以发现最后一个数总是为0，其实可以理解成这一组数与m = 7,n = 2也是相等的
   7 0 0
   6 1 0
   5 2 0
   4 3 0
   第二组，如果将每一个数都减1,可以发现，这组数的个数与m = 4,n = 3相等
   5 1 1
   4 2 1
   3 3 1
   3 2 1
   递推公式：

   def apple_divide(m,n):
   if m == 0 or n == 1： 	#如果，碟子只有1个，无论苹果有多少个都只有一种放法
       return 1
   if n > m :   			#如果，碟子的个数大于苹果的个数
       return apple_divide(m,m)
   else :
       return apple_divide(m,n-1) + apple_divide(m-n,n)
   

7. OPENJUDGE-9273: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;
   }