递推算法 - 信奥网|信息学奥赛

1推荐

1025浏览

信息学奥赛一本通T1314：递推算法过河卒

【题目描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A

0
轩爸发布于 2020-05-08 16:20

1推荐

1298浏览

信息学奥赛一本通T1313：递推算法位数问题

【题目描述】在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。【输入】输入包含一行，一个字符串，长度不超过1000。读入一个数N。【输出】输出有多少个数中有偶数个数字3。【输入样例】2【输出样例】73【源程序】

0
轩爸发布于 2020-05-08 16:20

0推荐

1004浏览

信息学奥赛一本通T1312：递推算法昆虫繁殖

【题目描述】科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。【输入】x,y,z的数值。【输出】过Z个月以后，共有成虫对数。【输入样例】1 2 8【输出样例】37【源程序】

0
轩爸发布于 2020-05-08 16:20

0推荐

1224浏览

信息学奥赛一本通T1197：递推算法山区建小学

【题目描述】政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为didi(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离

0
轩爸发布于 2020-04-26 16:20

1推荐

1352浏览

信息学奥赛一本通T1196：递推算法踩方格

【题目描述】有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b、走过的格子立即塌陷无法再走第二次；c、只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。【输入】允许在方格上行走的步数n(n≤20)。【输出】计算出的方案数量。【输入样例】2【输出样例】7

0
轩爸发布于 2020-04-26 16:20

1推荐

1414浏览

信息学奥赛一本通T1195：递推算法判断整除

【题目描述】一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：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)

0
轩爸发布于 2020-04-26 10:20

2推荐

1647浏览

信息学奥赛一本通T1194：递推算法移动路线

【题目描述】X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出

0
轩爸发布于 2020-04-26 10:20

0推荐

984浏览

信息学奥赛一本通T1192：递推算法放苹果

【题目描述】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。【输入】第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。【输出】对输入的每组数据M和N，用一行输出相应的K。【输入样例】1【输出样例】8【源程序】

0
轩爸发布于 2020-04-26 10:20

0推荐

707浏览

信息学奥赛一本通T1193：递推算法吃糖果

【题目描述】名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力，0<N<20)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1

0
轩爸发布于 2020-04-26 10:20

0推荐

1494浏览

信息学奥赛一本通T1191：递推算法流感传染

【题目描述】有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。【输入】第一行一个数字n，n不超过100，表示有n*n的宿舍房间。【输出】输出第m天，得流感的人数。【输入样例】5【输出样例】16【源程序】

0
轩爸发布于 2020-04-26 10:20

0推荐

2165浏览

信息学奥赛一本通T1190：递推算法上台阶

【题目描述】楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。【输入】输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。【输出】每一行输出对应一行输入的结果，即为走法的数目。【输入样例】1【输出样例】1【源程序】

0
轩爸发布于 2020-04-25 16:20

0推荐

1075浏览

信息学奥赛一本通T1189：递推算法 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【输

0
轩爸发布于 2020-04-25 16:20

0推荐

1190浏览

信息学奥赛一本通T1188：递推算法菲波那契数列

【题目描述】菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 ≤ a ≤ 1000000)。【输出】n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到

0
轩爸发布于 2020-04-25 16:20