第三章 递推算法

第三章 递推算法

【上机练习】

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，M【输入格式】 输入M，N的值。 【输出格式】 爬行有多少种路线。 【输入样例】 1 14 【输出样例】 377

6、极值问题(acme) 【问题描述】

已知m、n为整数，且满足下列两个条件：

① m、n∈{１，２，…，k}，即1≤m，n≤k ②（n2－m*n－m2）2＝1

你的任务是：编程输入正整数k（1≤k≤109），求一组满足上述两个条件的m、n，并且使m2＋n2的值最大。例如，从键盘输入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