递推习题汇总


1、数字三角形 【问题描述】 如下所示为一个数字三角形。 请编一个程序计算从顶到底的某处的一条路径, 使该路径 所经过的数字总和最大。只要求输出总和。 1、 一步可沿左斜线向下或右斜线向下走; 2、 三角形行数小于等于 100; 3、 三角形中的数字为 0,1,…,99; 测试数据通过键盘逐行输入,如上例数据应以如下所示格式输入: 【样例输入】 5 7 38 810 2744 45265 【样例输出】 30 2、骨牌 【问题描述】 有 2χ n 的一个长方形方格,用一个 1*2 的骨牌铺满方格。

编写一个程序,试对给出的任意一个 n(n>0) ,输出铺法总数。 【样例输入】 3 【样例输出】 3

3、棋盘格数(checkerboard) 【问题描述】 设有一个 N*M 方格的棋盘( l≤ N≤100,1≤M≤100) 。求出该棋盘中包含有多少个 正方形、多少个长方形(不包括正方形) 。 例如:当 N=2, M=3 时: 正方形的个数有 8 个:即边长为 1 的正方形有 6 个;边长为 2 的正方形有 2 个。 长方形的个数有 10 个:即 2*1 的长方形有 4 个:1*2 的长方形有 3 个:3*1 的长方形 有 2 个:3*2 的长方形有 1 个: 程序要求:输入:N,M 输出:正方形的个数与长方形的个数 【样例输入】 2 3

【样例输出】 8 10 4、昆虫繁殖(insects) 【问题描述】 科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。每对成虫过 x 个月产 y 对卵,每对卵要过两个月长成成虫。假设每个成虫不死,第一个月只有一对成虫, 且卵长成成虫后的第一个月不产卵(过 X 个月产卵),问过 Z 个月以后,共有成虫多少对? 0=<X<=20,1<=Y<=20,X=<Z<=50 【输入格式】 x,y,z 的数值 【输出格式】 过 Z 个月以后,共有成虫对数 【输入样例】 128 【输出样例】 37 5、位数问题(problem) 【问题描述】 在所有的 N 位数中,有多少个数中有偶数个数字 3?由于结果可能很大,你只需要输 出这个答案对 12345 取余的值。 【输入格式】 读入一个数 N 【输出格式】 输出有多少个数中有偶数个数字 3。 【输入样例】 2 【输出样例】 73 【数据规模】 1<=N<=1000 【样例说明】 在所有的 2 位数字,包含 0 个 3 的数有 72 个,包含 2 个 3 的数有 1 个,共 73 个

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

【输入样例】 2211 【输出样例】 2 【数据规模】 0<=m,n<=20 【样例说明】 B 点坐标为(2,2) ,C 点坐标为(1,1) ,共有 2 条路径

7、邮票问题(stamp) 【问题描述】 设有已知面额的邮票 m 种, 每种有 n 张, 用总数不超过 n 张的邮票, 能从面额 1 开始, 最多连续组成多少面额。 (1≤m≤100,1≤n≤100,1≤邮票面额≤255) 【输入格式】 第一行:m,n 的值,中间用一空格隔开。 第二行:A[1..m](面额) ,每个数中间用一空格隔开。 【输出格式】 连续面额数的最大值 【输入样例】 3 4 1 2 4 【输出样例】 14

8、平面分割(surface) (1998 合肥市竞赛复试第二题) 【问题描述】 同一平面内有 n(n≤500)条直线,已知其中 p(p≥2)条直线相交于同一点,则这 n 条直 线最多能将平面分割成多少个不同的区域? 【输入格式】

两个整数 n(n≤500)和 p(2≤p≤n) 。 【输出格式】 一个正整数,代表最多分割成的区域数目。 【输入样例】 12 5 【输出样例】 73

9、骨牌铺法(domino) 【问题描述】 有 1×n 的一个长方形,用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时 为 1×3 的方格。此时用 1×1、1×2 和 1×3 的骨牌铺满方格,共有四种铺法。如下图: 【输入样例】 3 【输出样例】 4

10、蜜蜂路线(bee) 【问题描述】 一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻 蜂房,现在问你:蜜蜂从蜂房 M 开始爬到蜂房 N,M<N,有多少种爬行路线? 【输入格式】 输入 M,N 的值。 【输出格式】 爬行有多少种路线。 【输入样例】 1 14 【输出样例】 377

11、数塔问题(tower) 【问题描述】 设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以 向左走或向右走,如图所示: 若要求从根结点开始,请找出一条路径,使路径之和最大,只要输出路径的和。

【输入格式】 第一行为 n(n<10),表示数塔的层数 从第 2 行至 n+1 行,每行有若干个数据,表示数塔中的数值。 【输出格式】 输出路径和最大的路径值。 【输入样例】 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 【输出样例】 86

12、极值问题(acme) 【问题描述】 已知 m、n 为整数,且满足下列两个条件: ① m、n∈{1,2,…,k},即 1≤m,n≤k ②(n2-m*n-m2)2=1 你的任务是:编程输入正整数 k(1≤k≤109) ,求一组满足上述两个条件的 m、n,并 2 2 且使 m +n 的值最大。例如,从键盘输入 k=1995,则输出:m=987 n=1597。 【输入样例】 1995 【输出样例】 m=987 n=1597

13、贮油点(oil) 【问题描述】 一辆重型卡车欲穿过 1000 公里的沙漠, 卡车耗汽油为 1 升/公里, 卡车总载油能力为 500 公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点,使 卡车能顺利穿过沙漠。 试问司机如怎样建立这些贮油点?每一贮油点应存储多少汽油, 才能 使卡车以消耗最少汽油的代价通过沙漠? 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。格式 如下: No. Distance(k.m.) Oil(litre) 1 × × ×× 2 × × ×× … …… ……

14、青蛙过河(Frog ) 【问题描述】 大小各不相同的一队青蛙站在河左岸的石墩(记为 A)上,要过到对岸的石墩(记为 D) 上去。河心有几片菏叶(分别记为 Y1…Ym)和几个石墩(分别记为 S1…Sn)。图示如下:
荷叶Yi 左岸石墩A 右岸石墩D

河心石墩 Sj

青蛙的站队和移动方法规则如下: 1. 每只青蛙只能站在荷叶、石墩,或者仅比它大一号的青蛙背上(统称为合法的落脚 点) ; 2. 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点; 3. 青蛙允许从左岸 A 直接跳到河心的石墩、荷叶和右岸的石墩 D 上,允许从河心的石 墩和荷叶跳到右岸的石墩 D 上; 4. 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动; 5. 青蛙在离开左岸石墩后,不能再返回左岸;到达右岸后,不能再跳回; 6. 假定石墩承重能力很大,允许无论多少只青蛙都可呆在上面。但是,由于石墩的面 积不大,至多只能有一只青蛙直接站在上面,而其他的青蛙只能依规则 1 落在比它 大一号的青蛙的背上。 7. 荷叶不仅面积不大,而且负重能力也有限,至多只能有一只青蛙站在上面。 8. 每一步只能移动一只青蛙,并且移动后需要满足站队规则; 9. 在一开始的时候,青蛙均站在 A 上,最大的一只青蛙直接站在石墩上,而其它的青 蛙依规则 6 站在比其大一号的青蛙的背上。 10. 青蛙希望最终能够全部移动到 D 上,并完成站队。 11. 设河心有 m 片荷叶和 n 个石墩,请求出这队青蛙至多有多少只,在满足站队和移动 规则的前提下,能从 A 过到 D。 【输入文件】 文件仅有两行,每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石 墩数 n(0<=n<=25) ,第二行为荷叶数 m(0<=m<=25) 。 【输出文件】 文件中仅包含一个数字和一个换行/回车符。 该数字为在河心有 n 个石墩和 m 片荷叶时, 最多能够过河的青蛙的只数。

15、2k 进制数 【问题描述】 设 r 是个 2k 进制数,并满足以下条件: (1)r 至少是个 2 位的 2k 进制数。

(2)作为 2k 进制数,除最后一位外,r 的每一位严格小于它右边相邻的那一位。 (3)将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w。 在这里,正整数 k(1≤k≤9)和 w(w≤30000)是事先给定的。 问:满足上述条件的不同的 r 共有多少个?


相关文档

递推习题
习题3 递推关系
递归与递推上机习题
常见递推数列通项公式求法及习题
题型最全的递推数列求通项公式的习题
常见递推数列通项公式的求法典型例题及习题
最全的递推数列求通项公式的习题1
题型最全的递推数列求通项公式的习题(1)
题型最全的递推数列求通项公式的习题1
2.1.2数列的递推公式练习题
电脑版