Processing math: 100%
NOIP学习小站
西安交通大学附属中学航天学校

递推算法(3)——经典例题

本文通过例题来进一步帮助读者学习掌握递推算法。

一、位数问题

问题:在所有的 n 位数中,有多少个数中有偶数个数字 3?注意:如果一个数字没有出现 3,那么就有 0 个 3,也算有偶数个 3。由于结果很大,只需要输出答案对 12345 取余的值(1 \le n \le 1000)。

分析:很显然,这里不能使用暴力求解。因为 n 位数可以由 n-1 位数在最高位添加一个数字得来,可以尝试使用递推算法。

  • 如果 i-1 位数有偶数个 3,那么在最高位可以添加 0~2、4~9 这 9 个数字,得到仍然是偶数个 3 的 i 位数(要排除 i==n 时不能在最高位添加 0 的情况);
  • 如果 i-1 位数有奇数个 3,那么在最高位添加上数字 3,得到是偶数个 3 的 i 位数。

可以用 e_i 表示 i 位数中有偶数个 3 的数字的个数,用 o_i 表示 i 位数中有奇数个 3 的数字的个数,那么有递推公式:

e_i=9e_{i-1}+o_{i-1}o_i=9o_{i-1}+e_{i-1}(i==n 时系数 9 要修正为 8)
初始值:e_1=9(1 位数中有 9 个数出现了 0 个 3),o_1=1

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int e[1010] = {0,9},o[1010] = {0,1};
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++){
int x = 9;
if(i==n) x--; //最高位不能添加0,能添加的数的个数-1
e[i] = (x*e[i-1]+o[i-1])%12345;
o[i] = (x*o[i-1]+e[i-1])%12345;
}
cout<<e[n]<<endl;
return 0;
}
#include<iostream> using namespace std; int e[1010] = {0,9},o[1010] = {0,1}; int main() { int n; cin>>n; for(int i=2;i<=n;i++){ int x = 9; if(i==n) x--; //最高位不能添加0,能添加的数的个数-1 e[i] = (x*e[i-1]+o[i-1])%12345; o[i] = (x*o[i-1]+e[i-1])%12345; } cout<<e[n]<<endl; return 0; }
#include<iostream>
using namespace std;
int e[1010] = {0,9},o[1010] = {0,1};
int main()
{
	int n;
	cin>>n;
    for(int i=2;i<=n;i++){
    	int x = 9;
    	if(i==n) x--;   //最高位不能添加0,能添加的数的个数-1
    	e[i] = (x*e[i-1]+o[i-1])%12345;
    	o[i] = (x*o[i-1]+e[i-1])%12345;
	}
	cout<<e[n]<<endl;
    return 0;
}

二、马拦过河卒

问题:P1002 过河卒

分析:可以先不考虑马的问题,过河卒可以向下,或者向右走,那么要走到坐标点 (x,y),可以从坐标点 (x-1,y) 向下走一步,也可以从坐标点 (x,y-1) 向右走一步(注意图中坐标系)。如果将从坐标点 (0,0) 到坐标点 (x,y) 的走法数量记为 F(x,y),可知递推公式:

F(x,y)=F(x-1,y)+F(x,y-1),初始值:F(x,0)=F(0,y)=1

再来考虑有马的情况。有了马之后,那么马的控制点(包括马所在的那一点)过河卒不能走上去,可以直接将这些点特殊处理,走到这些点的路径数量设置为 0 即可。实际处理时,可以用二维数组来记录到每个坐标点的路径数量,并且将控制点的路径数量设置为一个特殊值 -1,这样可以减少一个标记控制点的数组:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
const int MAX = 25;
long long f[MAX][MAX];
int dirs[9][2] = {
{0,0},
{1,2},
{1,-2},
{-1,2},
{-1,-2},
{2,1},
{2,-1},
{-2,1},
{-2,-1}
};
int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
//通过坐标变化数组dirs快速计算马的所有控制点
for(int i=0;i<9;i++){
int nx = x+dirs[i][0];
int ny = y+dirs[i][1];
//控制点,标记为特殊值-1
if(nx>=0 && nx<=n && ny>=0 && ny<=m) f[nx][ny]=-1;
}
f[0][0]++; //(0,0)如果是控制点变成0,否则是1
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(f[i][j]==-1) continue; //控制点,不处理
if(i && f[i-1][j]>0) f[i][j] += f[i-1][j]; //上边不是控制点
if(j && f[i][j-1]>0) f[i][j] += f[i][j-1]; //左边不是控制点
}
}
cout<<(f[n][m]==-1?0:f[n][m]);
return 0;
}
#include<iostream> using namespace std; const int MAX = 25; long long f[MAX][MAX]; int dirs[9][2] = { {0,0}, {1,2}, {1,-2}, {-1,2}, {-1,-2}, {2,1}, {2,-1}, {-2,1}, {-2,-1} }; int main() { int n,m,x,y; cin>>n>>m>>x>>y; //通过坐标变化数组dirs快速计算马的所有控制点 for(int i=0;i<9;i++){ int nx = x+dirs[i][0]; int ny = y+dirs[i][1]; //控制点,标记为特殊值-1 if(nx>=0 && nx<=n && ny>=0 && ny<=m) f[nx][ny]=-1; } f[0][0]++; //(0,0)如果是控制点变成0,否则是1 for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(f[i][j]==-1) continue; //控制点,不处理 if(i && f[i-1][j]>0) f[i][j] += f[i-1][j]; //上边不是控制点 if(j && f[i][j-1]>0) f[i][j] += f[i][j-1]; //左边不是控制点 } } cout<<(f[n][m]==-1?0:f[n][m]); return 0; }
#include<iostream>
using namespace std;
const int MAX = 25;
long long f[MAX][MAX];
int dirs[9][2] = {
	{0,0},
	{1,2},
	{1,-2},
	{-1,2},
	{-1,-2},
	{2,1},
	{2,-1},
	{-2,1},
	{-2,-1}
};
int main()
{
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	//通过坐标变化数组dirs快速计算马的所有控制点
	for(int i=0;i<9;i++){
		int nx = x+dirs[i][0];
		int ny = y+dirs[i][1];
		//控制点,标记为特殊值-1 
		if(nx>=0 && nx<=n && ny>=0 && ny<=m) f[nx][ny]=-1;
	}
	f[0][0]++;		//(0,0)如果是控制点变成0,否则是1 
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(f[i][j]==-1) continue;	//控制点,不处理 
			if(i && f[i-1][j]>0) f[i][j] += f[i-1][j]; //上边不是控制点 
			if(j && f[i][j-1]>0) f[i][j] += f[i][j-1]; //左边不是控制点 
		}
	}
	cout<<(f[n][m]==-1?0:f[n][m]);
	return 0;
}

三、蜜蜂路线

问题:P2437 蜜蜂路线

分析:先来看从编号 1 的蜂房爬到编号 i 的蜂房,可知只能从 i-1 或者 i-2 爬到 i,那么从编号 1 的蜂房爬到编号 i 的蜂房的路线数量是从编号 1 的蜂房爬到编号 i-1 的蜂房和从编号 1 的蜂房爬到编号 i-2 的蜂房的路线数量的和。可以得出递推公式:

f_i=f_{i-1}+f_{i-2},初始值:f_1=f_2=1

其实从 m 爬到 n,和从 1 爬到 n-m+1 的效果是一样的。所以要计算的是 f_{n-m+1},考虑到数据规模,需要用到高精度:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int f[1010][220]={
{0},
{1,1}, //f[1]为高精度数1
{1,1} //f[2]为高精度数1
};
//高精度加法:a+b → c
void add(int a[],int b[],int c[]){
int x = c[0] = 0;
for(int i=1;i<=a[0]||i<=b[0];i++){
c[0]++;
c[i] = a[i]+b[i]+x;
if(c[i]>=10) c[i]-=10,x=1;
else x=0;
}
if(x) c[++c[0]] = x;
}
int main()
{
int m,n,t;
cin>>m>>n;
t = n-m+1;
for(int i=3;i<=t;i++){
add(f[i-1],f[i-2],f[i]);
}
for(int i=f[t][0];i>0;i--) cout<<f[t][i];
return 0;
}
#include<iostream> using namespace std; int f[1010][220]={ {0}, {1,1}, //f[1]为高精度数1 {1,1} //f[2]为高精度数1 }; //高精度加法:a+b → c void add(int a[],int b[],int c[]){ int x = c[0] = 0; for(int i=1;i<=a[0]||i<=b[0];i++){ c[0]++; c[i] = a[i]+b[i]+x; if(c[i]>=10) c[i]-=10,x=1; else x=0; } if(x) c[++c[0]] = x; } int main() { int m,n,t; cin>>m>>n; t = n-m+1; for(int i=3;i<=t;i++){ add(f[i-1],f[i-2],f[i]); } for(int i=f[t][0];i>0;i--) cout<<f[t][i]; return 0; }
#include<iostream>
using namespace std;
int f[1010][220]={
	{0},
	{1,1},    //f[1]为高精度数1
	{1,1}     //f[2]为高精度数1
};
//高精度加法:a+b → c
void add(int a[],int b[],int c[]){
	int x = c[0] = 0;
	for(int i=1;i<=a[0]||i<=b[0];i++){
		c[0]++;
		c[i] = a[i]+b[i]+x;
		if(c[i]>=10) c[i]-=10,x=1;
		else x=0;
	}
	if(x) c[++c[0]] = x;
}
int main()
{
	int m,n,t;
	cin>>m>>n;
	t = n-m+1;
	for(int i=3;i<=t;i++){
		add(f[i-1],f[i-2],f[i]);
	}
	for(int i=f[t][0];i>0;i--) cout<<f[t][i];
	return 0;
}

登录

注册