《杨辉三角与递推算法》练习
1、 义务植树(tree)
【问题描述】 3月12日植树节到了，小明的班主任带着全班同学到白云山义务植树。好不容易到了白云山，找到预先安排好的地方，班主任把工具分发下去，拿出一张图纸(如图1)展示给大家看，并说明要求：
我们班所有同学植的树要成一个等腰三角形，等腰三角形的两条腰上按顺序都是植1棵树，其他位置植树棵数等于它的左上角和右上角所植树的和。
小明负责本小组植树棵数的计算，例如第i行第j列这个位置应植多少棵树。小明认真看了一下图纸，傻眼了，这该怎么计算啊？ 【输入格式】
输入文件只有1行：i和j两个数(1<=i,j<=101，j<=i)，中间隔一个空格，表示植树位置为第i行第j个位置(从左往右数第j个)。 【输出格式】
输出文件只有一个数：所求位置上应植数的棵数。 【输入输出样例】 tree.in tree.out 5 3 2、 走楼梯(stairs)
【问题描述】有一段楼梯有n级台阶，规定每一步只能跨一级或两级，要登上第n级台阶有几种不同的走法? 【输入格式】
输入文件仅1行，1个正整数n（n<=1000）。 【输出格式】
输出文件仅1行，即走n级楼梯不同走法的数量。 【输入输出样例】 stairs.in 4
3、猴子吃桃(monkey)
【猴子吃桃】猴子摘了一堆桃，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。 问最初有多少个桃子？ 【输入格式】
输入文件仅1行，1个正整数n，表示猴子吃了n天的桃子（n<=50）。 【输出格式】
输出文件仅1行，即第1天时，那一堆桃子的数量。
stairs.out 5 6 【输入输出样例】 monkey.in 4 4、 汉诺单塔问题(hanoi)
【问题描述】hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：
monkey.out 5
(1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，需要最少移动多少次？ 【输入格式】输入1个正整数n，表示在A柱上放有n个圆盘。
【输出格式】输出仅1行，包含一个正整数，为完成上述任务所需的最少移动次数An。 【输入输出样例】 hanoi.in 3 5、Hanoi双塔问题（hanois）
【问题描述】给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘足不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求： (1)每次只能移动一个圆盘；
(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入格式】输入1个正整数n，表示在A柱上放有2n个圆盘。
【输出格式】输出仅1行，包含一个正整数，为完成上述任务所需的最少移动次数An。 【输入输出样例】 hanois.in 2 hanois.out 6 hanoi.out 7
【限制】对于50％的数据，1<=n<=25，对于100％的数据，l<=n<=200 【提示】设法建立An与An-1的递推关系式。