noip讲义2-归纳法.ppt

归纳法 归纳法是由一系列有限的特殊事例得出一般规律的推理方法 例如 求前n个奇数的和 分析 如用S n 表示前n个奇数的和 则S 1 1 S 2 1 3 4 S 3 1 3 5 9 S 4 1 3 5 7 16 S 5 1 3 5 7 9 25 可以看出 当n取1 2 3 4 5时 S n n2 因此可以归纳出求前n个奇数的和的一般规律 即S n n2 上面的归纳法是不完全归纳法 因为由它得到的结论不一定对任意的n都成立 17世纪著名的德国数学家莱布尼兹曾证明 对于所有的正整数n 数n3 n能被3整除 数n5 n能被5整除 数n7 n能被7整除 因此他猜测 对所有的奇数k和任意的自然数n 数nk n能被k整除 29 2 510不能被9整除 要证明对所有的n都成立 就必须使用下面介绍的数学归纳法 1 证明当n取第一个值n0时结论正确 2 假设当n k时结论成立 证明当n k 1时结论也成立 证明 当n 时 左边 右边 此时等式成立 假设当n k时等式成立 即 k 1 k2 那么当n k 1时 k 1 2 k 1 1 k2 2 k 1 1 k2 2k 1 k 1 2 练习1 如图所示 线段AB上共有10个点 包括两个端点 那么这条线段上一共有多少条不同的线段 分析 先从AB之间只有一个点开始 再逐步增加AB之间的点数 找出点和线段之间的规律 AB之间只有1个点 线段有1 2 3条 AB之间只有2个点 线段有1 2 3 6条 AB之间只有3个点 线段有1 2 3 4 10条 AB之间只有4个点 线段有1 2 3 4 5 15条 不难发现 当AB之间有8个点时 线段有1 2 3 4 5 6 7 8 9 45条 若再进一步研究可得出这样得规律 线段数 教学中要训练学生用不完全归纳法解题 练习2 在一张四边形纸上共有10个点 如果把四边形的顶点算在一起 则一共有14个点 已知这些点中的任意三个点都不在同一直线上 按照下面规定把这张纸片剪成一些三角形 每个三角形的顶点都是这14个点中的3个 每个三角形内都不再有这些点 那么 这张四边形的纸最多可以剪出 个三角形 在10个点中任意取一点 与四边形的四个顶点构成4个三角形 再在剩下的9个点中任意取一点 它必定落在某一个三角形中 只能与三角形的三个顶点构成三个三角形 即增加2个三角形 以后各点情况都与此相同 除了第一点增加4个三角形外 其余各点都只增加2个三角形 所以共可以剪出4 10 1 2 22 个 三角形 4 2 n 1 练习3 将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目 例如 当n 1时 L1 2 进一步考虑 用n条直线 放在平面上 能确定的最大区域数目Ln是多少 n 1 L1 2 F 1 2 n 2 L2 4 F 2 F 1 2 n 3 L3 7 F 3 F 2 3 n 4 L4 11 F 4 F 3 4 n 5 L5 16 F 5 F 4 5 可得到递推公式 F n F n 1 n F n n n 1 n 2 2 F 1 练习4 将一张长方形的纸对折 可得到一条折痕 继续对折 对折时每次折痕与上次的折痕保持平行 连续对折三次后 可得到 条折痕 那么对折n次 可得到几条折痕 第一次对折1条折痕 第二次对折3条折痕 第三次对折7条折痕 第四次对折15条折痕 所以我们猜想第n次对折后的折痕条数是2n 1 练习5 如图 第一次把三角形剪去一个角后 图中最多有四个角 第二次再把新产生的角各剪一刀 如此下去 每一次都是把新产生的角各剪一刀 则第n次剪好后 图中最多有多少个角 可知后一次新产生的角的个数是前一次新产生的角的个数的 倍 再加上 就是后一次产生的角的总数 因此 剪n次后 图中最多有角 2 2n 练习6 下图中把大正方形各边平均分成了5份 此时有55个正方形 如果把正方形各边平均分成n份 那么得到的正方形总数为多少 52 42 32 22 12 55 n2 n 1 2 n 2 2 22 12 1 6n n 1 2n 1 练习7 如图所示 在正六边形A周围画出6个同样的正六边形 阴影部分 围成第1圈 在第1圈外面再画出12个同样的正六边形 围成第2圈 按这个方法继续画下去 当画完第10圈时 图中共有多少个与A相同的正六边形 第一圈有6个正六边形 第二圈有6 2个正六边形 第三圈有6 3个正六边形 第n圈有6 n个正六边形 所以图中共有1 6 1 2 3 4 5 6 7 8 9 10 331个正六边形 练习8 在n n的正方形钉子板上 n是钉子板每边上的钉子数 求连接任意两个钉子所得到的不同长度的线段种数 练习9 如图 平面内有公共端点的六条射线 从射线OA开始按逆时针方向依次在射线上写出数字1 2 3 4 5 6 7 问 2007在哪条射线上 练习10 如图 以等腰三角形AOB的斜边为直角边向外作第2个等腰直角三角形ABA1 再以等腰直角三角形ABA1的斜边为直角边向外作第3个等腰直角三角形A1BB1 如此作下去 若OA OB 1 则第n个等腰直角三角形的面积Sn 练习11 计算13 23 33 43 53 63 73 83 93 103的值 练习12 2000个学生排成一行 依次从左到右编上1 2000号 然后从左到右按一 二报数 报一的离开队伍 剩下的人继续按一 二报数 报一的人离开队伍 按这个规律如此下去 直至当队伍只剩下一人为止 问 最后留下的这个人原来的号码是多少 分析 我们通过前几次留在队伍中的学生的编号找出规律 第一次留下的学生编号是 2 4 6 8 10 都是2的倍数 即21的倍数第二次留下的学生编号是 4 8 12 16 20 都是4的倍数 即22的倍数第一次留下的学生编号是 8 16 24 32 40 都是8的倍数 即23的倍数 由于210 1024 2000 211 2048 这样可知 最后留下学生的号码一定是1024 练习13 999 999 999 999的乘积中有多少个数字是奇数 练习14 n n 1 1 41 练习15 如图1 是棱长为a的小正方体 图2 图3由这样的小正方体摆放而成 按照这样的方法继续摆放 自上而下分别叫第一层 第二层 第n层 第n层的小正方体的个数记为sn 写出当n 10时 s10 55 13610 如图 有边长为1的等边三角形卡片若干张 使用这些三角形卡片拼出边长分别是2 3 4 的等边三角形 如图所示 根据图形推断 每个等边三角形所用卡片总数sn与边长n之间的关系 49162536 练习16 Hanoi双塔问题 给定A B C三根足够长的细柱 在A柱上放有2n个中间有孔的圆盘 共有n个不同的尺寸 每个尺寸都有两个相同的圆盘 注意这两个圆盘是不加区分的 下图为n 3的情形 现要将这些圆盘移到C柱上 在移动过程中可放在B柱上暂存 要求 1 每次只能移动一个圆盘 2 A B C三根细柱上的圆盘都要保持上小下大的顺序 任务 设An为2n个圆盘完成上述任务所需的最少移动次数 对于输入的n 输出An 输入文件hanoi in为一个正整数n 表示在A柱上放有2n个圆盘 输出文件hanoi out仅一行 包含一个正整数 为完成上述任务所需的最少移动次数An 样例1 样例2 限制 对于50 的数据 1 n 25对于100 的数据 1 n 200 提示 设法建立An与An 1的递推关系式 解题思路 数学归纳 高精度Hanoi单塔的最少移动步数是2n 1 现在有2层 可以将2层看作1层 便回到了单塔的问题上 每移动想象中的 单个 盘子需要两步 故Hanoi双塔 Hanoi单塔 2可得公式 f n 2n 1 2高精度只要编个乘法就可以了 不要忘记最后 2 beginassign input hanoi in assign output hanoi out reset input rewrite output readln n ppp n 1 a 1 a 1 2i 100 whilea i 0doi i 1 forj idownto1dowrite a j close input close output end varn i j integer a array 1 100 of0 9 procedureppp k integer vari j w s integer begina 1 1 初值 w 0 fori 1tokdoforj 1to100dobegins a j 2 w a j smod10 w sdiv10 end end Cantor表 现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的 他是用下面这一张表来证明这一命题的 1 11 21 31 41 5 2 12 22 32 4 3 13 23 3 4 14 2 5 1我们以蛇形给上表的每一项编号 第1项是1 1 然后是1 2 2 1 3 1 2 2 输入 整数n 1 n 10000000 输出 表中的第N项样例 input n 7output 1 4 分析 不难看出 第K个斜行 方向 上每个分数的分子分母之和为K 1 而表的填充顺序正是依次填写每个斜行 因此先算出第N项所在的斜行K 显然K是满足N 1 2 3 K的最小数 显然当K为奇数时 分母为N 1 2 3 K 1 K为偶数时分子为N 1 2 3 K 1 varn k I j longint beginreadln n k 1 whilen kdobeginn n k k k 1 end 先确定在哪一斜行 再分奇偶讨论 ifkmod2 0thenwriteln n k 1 n elsewriteln k 1 n n end 计算正方形 长方形个数 设有一个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个 输入文件1 in 只有一行 两个整数N和M 输出文件1 out 只有一行 为两个整数 中间用空格隔开 分别表示所求的正方形的个数与长方形的个数 样例 输入23输出810 对于棋盘中的任意一个正方形而言 只要确定了左上角的位置和边长后 该正方形就完全确定了 因此只要穷举除最下面和最右边之外的每个格点 算出以它们作为正方形的左上角位置时边长不同的正方形个数 然后累加起来就可得到全部正方形的个数 同样地也可以类似地算出长方形个数 包括