构造法的解题模式.ppt

探索构造法的解题模式 一、 什么是构造法 为了解决某个数学问题，我们通过联想和化归的思想，人为地构造辅助图形、模型、方程、函数……，以帮助解决原来的问题，这样的解题方法，可以看作是构造法解题。信息学竞赛中，它的应用十分广泛。构造恰当的模型或方法，能使问题的解决，变得非常简洁巧妙。 构造法 优点：简洁、高效、巧妙。 关键：（1） 抓住本质特征 进行新途径的重构再构 （2） 依托于个人头脑中所拥有的常规解题模型、模式的数量和迁移的水平 二、 构造法的应用与步骤： （1）构造法的应用： 1 分类构造，简化解题过程； 2 构造图象，结合已有知识，降低解题难度； 3 构造模型，明确情景 （2）构造法的解题步骤： 检验、修改 分类构造，简化解题过程 【例一】 跳棋问题 设有一个n×n方格的棋盘，布满棋子。跳棋规则如下 ： 1 每枚棋子跳动时，其相邻方格（即有公共边的方格）必须有一枚棋子作为垫子，方能起跳； 2 棋子只能沿水平或垂直方向起跳； 3 棋子经过垫子，跳入同一方向的方格，并把垫子取出棋盘。 ? 任务：将n×n方阵的棋盘扩展成m×m的方阵，试求最小的m，使得在m×m的棋盘中，棋子依规则跳动，最后棋盘只剩下一枚棋子， 并给出跳棋方案。 【解题分析】 本题若用盲目有哪些信誉好的足球投注网站法解决，显然很难出解。我们考虑用构造法。我们把n按除以3的余数进行分类讨论。 分类讨论 n=3k (k为正整数) n=3k+2(k为正整数) 我们先从较小的n开始，研究是否有规律可循。同时为了对较大的n能得到解法的规律，我们构造几种基本形状的跳法。 当n=2时，有三种基本跳法，分别定义为基本形状A、B、C。如图： 构造图象，充分展示各变量之间的关系 【例二】01串问题(NOI99) 给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何连续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何连续的长度为L1的子串，1的个数大于等于A1且小于B1。 构造模型，明确情景 【例三】求Fibonacci数列 * * 问题 假设 建模 分析 实现 我们把n×n的棋盘分成k×k个3×3的网格，并重复排列这种 3×3的网格，延伸至整个平面。每个3×3的网格按图示方式着色： 每次跳棋都是从一种颜色跳至另一色。设每次跳棋跳至1、2、3色的次数依次是a、b、c次。不妨设最终剩下的一枚棋子是1色 。 通过列方程组，易知无解。故该情况不成立。 1 2 3 2 3 1 3 1 2 A ,B两种基本跳法告诉我们：对于任意的连续的3个棋子，只要有另一个棋子辅助，就可以连续的消去3个棋子。有了这几种基本跳法，构造本题答案就不是难事了。 以n=8为例，我们将A,B,C 三种基本跳法用横形，竖 形，正方形长条表示。从 上到下，从左到右依次消 去即可。 n=3k+1(k为正整数) 类似处理，我们仍用基本跳法来构造解答。 以n=7为例，从上到下消去，从左到右，逐个消去，最后剩下右下角的 单独图形，再独立完成。 ? 观察上述过程可以发现，只需把原棋盘向四周扩展1行，变成(n+2)(n+2)即可。该方阵可以满足题目要求 小结： （1） 思维过程： 分析问 对问题 针对每一 合成整个 题性质 进行分类 类进行构造 问题的解 (2）关键： 敏锐地发现问题的分层性，果断的选择方法， 很好的 归纳总结。 【解题分析】 模式1 分析不等式 设hi为01子串s0..si(1=I=n)中1的个数，其中s0=0,h0=0。显然，由hi的定义可以得出不等式0=hi-1=hi,hi=hi-1+1, 移项即得： 0=hi-hi-1 -1=hi-1-hi L0-b0=hi-hi-l0 当I=L0时，根据条件，Si-L0+1…Si中0的个数(L0-(hi-hi-L0))在a0～b0之间，即a0=L0-(hi-hi