《归纳与递推》配套练习题.pdf

1 归纳与递推配套练习题 一、简答题 1、请用递推方法求出甲、乙、丙、丁、戊五个人站成一排照相，共有多少 种不同站法？ 2、在平面上有 5 个三角形，最多把平面分割成多少部分？ 3、将自然数 1，2，3，按图排列，在“ 2”处转第一个弯，“ 3”处转 第二个弯，“ 5”处转第三个弯，。问哪个数处转第十二个弯？ 4、用“ 1×2”纸牌（如下左图）若干张，放在一个图形上，要求“不空、 不超、不重叠”，满足这种条件的叫做一种“完全覆盖”。例如，用“1× 2”纸牌覆盖“ 2×2”图形（如下右图），有两种方法。 2 问用“ 1×2”纸牌，覆盖“ 2×8”图形（如下图）有多少种覆盖方法？ 5、10 级台阶，每次可以上1 级或者 2 级，那么有多少种不同的走法？ 6、平面上 5 条直线最多能把圆的内部分成几部分？ 平面上 24 条直线最多能把圆的内部分成几部分？ 7、 3 8、传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插着 三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64 片中心有孔 的金片。每天都有一个值班僧侣按下面规则移动金片：把金片从第一根宝 石针移到其余的某根宝石针上。要求一次只能移动一片，而且小片永远要 放在大片的上面。 当时传说当 64 片金片都按上面的规则从第一根宝石针移 到另一根宝石针上时，世界将在一声霹雳中毁灭。所以有人戏称这个问题 叫“世界末日”问题（也称为“ Hanoi 塔”问题），当然，移金片和世界毁 灭并无联系，这只是一个传说而已，但说明这是一个需要移动很多很多次 才能办到的事情。 那么究竟按上述规则移动完成64 片金片需要移动多少次 呢？ 答案部分 一、简答题 1、 【正确答案】： 120 【答案解析】：一个人站法：1 种； 4 二个人站法： 1×22（种）； 三个人站法： 1×2×36（种）； 四个人站法： 1×2×3×424（种）； 五个人站法： 1×2×3×4×5120（种）。 【答疑编号 10235603】 2、 【正确答案】： 38 【答案解析】： 2（1×33）（ 3×33）（ 5×33）2612 1838 【答疑编号 10235606】 3、 【正确答案】： 45 【答案解析】： 12×（123456）45 【答疑编号 10235605】 4、 【正确答案】： 34 【答案解析】：设用“ 1×2”纸牌，覆盖“ 2×n”图形有 an种方法。根据 anan 2an1。