第二部分 基础算法 --> 第三章 递推算法
- 递推算法
- 1312【例3.4】昆虫繁殖
- 1313【例3.5】位数问题
- 1314【例3.6】过河卒(Noip2002)
- 1188 菲波那契数列(2)
- 1189 Pell数列
- 1190 上台阶
- 1191 流感传染
- 1192 放苹果
- 1193 吃糖果
- 1194 移动路线
- 1195 判断整除
- 1196 踩方格
- 1197 山区建小学
递推算法
1312【例3.4】昆虫繁殖
【题目描述】科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过x个月产卵)，问过z个月以后，共有成虫多少对？0≤x≤20,1≤y≤20,x≤z≤50。
【输入】x,y,z的数值。
【输出】过z个月以后，共有成虫对数。
【输入样例】1 2 8
【输出样例】37
【题解】
#include
const int N=51;
long long a[N], b[N];//成虫对数，卵对数
int main(){
int x,y,z; scanf("%d%d%d", &x, &y, &z);
for(int i=1; i<=z; i++) a[i]=1, b[i]=0;//成虫，卵数初始化
for(int i=x+1; i<=z+1; i++){
b[i] = y*a[i-x]; //卵数与成虫数量有关
a[i] = a[i-1] + b[i-2]; //成虫与上月成虫和前2月卵数有关
}
printf("%lld",a[z+1]);
return 0;
}
1313【例3.5】位数问题
【题目描述】在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。
【输入】读入一个数N(N≤1000)。
【输出】输出有多少个数中有偶数个数字3。
【输入样例】2
【输出样例】73
【题解】
1314【例3.6】过河卒(Noip2002)
【题目描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
【输入】给出n、m和C点的坐标。
【输出】从A点能够到达B点的路径的条数。
【输入样例】8 6 0 4
【输出样例】1617
【题解】
1188 菲波那契数列(2)
【题目描述】菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。
【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。
【输出】n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。
【输入样例】
4
5
2
19
1
【输出样例】
5
1
181
1
【题解】
1189 Pell数列
【题目描述】Pell数列a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an?1+an?2(n>2)。
给出一个正整数k，要求Pell数列的第k项模上32767是多少。
【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。
【输出】n行，每行输出对应一个输入。输出应是一个非负整数。
【输入样例】
2
1
8
【输出样例】
1
408
【题解】
点击查看代码
1190 上台阶
【题目描述】楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
【输入】输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。
【输出】每一行输出对应一行输入的结果，即为走法的数目。
【输入样例】
1
2
3
4
0
【输出样例】
1
2
4
7
【题解】
1191 流感传染
【题目描述】有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
【输入】
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100。
【输出】输出第m天，得流感的人数。
【输入样例】
5
....#
.#.@.
.#@..
#....
.....
4
【输出样例】
16
【题解】
1192 放苹果
1193 吃糖果
1194 移动路线
【题目描述】X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下图所示：
【输入】输入只有一行，包括两个整数m和n（0 < m+n ≤ 20），代表方格矩阵的行数和列数，m、n之间用空格隔开。
【输出】输出只有一行，为不同的移动路线的数目。
【输入样例】2 3
【输出样例】3
【题解】
1195 判断整除
【题目描述】一个给定的正整数序列，在每个数之前都插入+号或?号后计算它们的和。比如序列：1、2、4共有8种可能的序列：
(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、?3、?6、?9……都可以认为是3的倍数。
【输入】输入的第一行包含两个数：N(2
【输入样例】
3 2
1 2 4
【输出样例】
NO
1196 踩方格
【题目描述】有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
【输入】允许在方格上行走的步数n(n≤20)。
【输出】计算出的方案数量。
【输入样例】2
【输出样例】7
1197 山区建小学
【题目描述】政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0 【输入】 表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。 【输出】各村庄到最近学校的距离之和的最小值。 【输出样例】
第1行为m和n，其间用空格间隔
第2行为m?1 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如:10 3
2 4 6 5 2 4 3 1 3
【输入样例】10 2
3 1 3 1 1 1 1 1 3
18