第三章 递推算法.pdfVIP

第三章 递推算法 【上机练习】 1、走楼梯(stairs) 楼梯有 N 级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走 法？ 【输入样例】 3 【输出样例】 3 2、兔子繁殖(rabbit) 有一种兔子，出生后一个月就可以长大，然后再过一个月一对长大的兔子就可以生育一对小兔子且以 后每个月都能生育一对。现在，我们有一对刚出生的这种兔子，那么，n 个月过后，我们会有多少对兔子 呢？假设所有的兔子都不会死亡。 【输入格式】 输入文件仅一行，包含一个自然数n。 【输出格式】 输出文件仅一行，包含一个自然数，即n 个月后兔子的对数。 【输入样例】 5 【输出样例】 5 3、平面分割(surface) 同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n 条直线最多能将 平面分割成多少个不同的区域？ 【输入格式】 两个整数n（n≤500）和p（2≤p≤n）。 【输出格式】 一个正整数，代表最多分割成的区域数目。 【输入样例】 12 5 【输出样例】 73 4、骨牌铺法(domino) 有 1×n 的一个长方形，用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。 此时用1×1、1×2和1×3的骨牌铺满方格，共有四种铺法。如下图： 【输入样例】 3 【输出样例】 4 5、蜜蜂路线(bee) 【问题描述】 一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问 你：蜜蜂从蜂房M开始爬到蜂房N，MN，有多少种爬行路线？ 【输入格式】 输入M，N的值。 【输出格式】 爬行有多少种路线。 【输入样例】 1 14 【输出样例】 377 6、极值问题(acme) 【问题描述】 已知m、n为整数，且满足下列两个条件： ① m、n∈{１，２，…，k}，即1≤m，n≤k ②（n2 2 2 －m*n－m ） ＝1 你的任务是：编程输入正整数k（1≤k≤109 2 2 ），求一组满足上述两个条件的m、n，并且使m ＋n 的值最 大。例如，从键盘输入k=1995，则输出：m=987 n=1597。 【输入样例】 1995 【输出样例】 m=987 n=1597 7、火车站(Noip1998) 【问题描述】 火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前） 车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定的规律：上车的 人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n-1 站），都满足此规律。现给出的条件是：共有 N 个车站，始发站上车的人数为 a，最后一 站下车的人数是 m （全部下车）。试问从x 站开出时车上的人数是多少？若无解输出“No answer. ”（所有数据均在long 范围内） 【输入格式】a，n ，m 和 x 【输出格式】x 站开出时车上的人数 【输入样例】 1 6 7 3 【输出样例】 2