东北师范大学信息学选论第三章一、二节

《东北师范大学信息学选论第三章一、二节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章构造法构造法:就是根据题设条件或结论所具有的特征、性质，构造出满足条件或结论的数学模型，借助于该数学模型解决问题的方法．在现实世界中，有大量事物存在着许多相似或相近的规律，存在着本质相同的东西。正因为如此，在求解非标准题的过程中就有可能形成一些常用的方法思路（策略），按照这些方法思路分析和求解试题，一般可使解题过程变得容易一些。这些方法思路统称为构造法。由于构造法比较综合地反映了选手的智慧、知识基础和创造性思维的能力，因此是联赛的考核重点。从数学方法的分类来看，构造的数学模型属于初等模型或优化模型。一般地，数学模型具有三大功能：1解

2、释功能:利用数学模型说明事物发生的原因。2判断功能：利用数学模型判断原来的知识和认识的可靠性。3预见功能：利用数学模型揭示事物的发展规律，为人们的行为提供指导或参考。构造法解题的思路或步骤可以归纳为：构造法解题的类型一般有：1.数学建模：通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形、一个物理原理、一个化学方程式等等。2.直接构造问题解答：这是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。无论是直接构造问题解答还是数学建模，都

3、要通过算法来实现。如何设计一个有较低编程复杂度和时空复杂度且结构清晰的算法，十分重要。通常考虑的因素有：(1)选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好、冗余的信息会影响算法的效率。(2)模型的建立不是一个一蹴而就的过程，而是要经过反复地检验、修改，在实践中不断完善。(3)数学模型通常有严格的格式，但程序编写形式可不拘一格。构造与建模是一个复杂的抽象过程。我们要善于描视问题的本质，寻找突破口，进而选择适当的模型。构造的模型可以帮助我们认识问题，不同的模型从不同的角度反映问题，可以引发不同的思路，起到发散思维的作

4、用。但认识问题的最终目的是解决问题，模型的固有性质可帮我们建立算法，其优劣可以通过时空复杂度等指标来衡量，但最终还是以程序的运行结果为标准。所以模型不是一成不变的，同样要通过各种技术不断优化。模型的产生虽然是人脑思维的产物，但它仍然是客观事物在人脑中的反映。所以要培养良好的建模能力，还必须依靠在平时的学习中积累丰富的知识和经验。⑴对应策略：将问题a对应另一个便于思考或有求解方法的问题b，化繁为简，变未知为已知。对应经典问题对应简单问题对应数学问题在建模过程中经常使用的策略有⑵分治策略：将问题的规模逐渐减少，可明显降低解决问题的复杂程度。算

5、法设计的这种策略称之为分治策略，即对问题分而治之。递推的分治策略递归的分治策略⑶归纳策略：归纳策略则是通过列举试题本身的特殊情况，经过深入分析，最后概括出事物内在的一般规律，并得到一种高度抽象的解题模型。递推式递归式制定目标贪心方案在自然界或日常生活中，许多现象具有不确定的性质，很难建立数据模型，一般采用模拟策略⑷模拟策略：模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟题没有固定的模式，一般形式有两种：随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的

6、随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。模拟的解题方法一般有三种类型直叙式模拟筛选法模拟构造法模拟第一节、对应策略将问题a对应于另一个便于思

7、考或已有求解方法的问题b，化繁为简，变未知为已知。对应经典问题对应简单问题对应数学问题一一对应技术是一种重要的策略。它的核心是求同，通过举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，推导出事物间的联系，从而全面、深入地认识和分析事物。“世界上没有完全不同的东西”，相似点的普遍存在为我们使用对应策略解题提供了基础。但是对应并不等于等价，两个问题间的表面相似并不等于本质的联系。对应策略不仅要分析问题间的共同点，还要分析问题间的不同点，是一种异中求同的思维方法．一、对应经典问题经典问题及其算法的知识积累是解题的基础，竞赛的许多试题最

8、终都可以转化为经典问题，因此必须尽可能多地掌握经典问题及其算法的知识。解题时，心中经常回忆已经解决的经典问题和有关解法，往往会收到意想不到的效果。当然这些试题并不直接以经典问题的原貌出现。我们