程序设计中常用的计算思维方式

程序设计中常用的计算思维方式

算法思维

逻辑思维

第1章 正确认识和处理整体与部分的关系

概述：

“整体”与“部分”是一对虽然对立、但并非僵化不变的概念..在一定条件下;“部分”可以看作“整体” ;“整体”又可以看作是另一个“整体”的“部分” ;两者相互依存和影响..“整体”与“部分”又可以相互转化的..“整体”的问题可以分割成“部分”来处理;“部分”的问题也可以通过“整体”来解决..

1.1 整体实现的关键是准确地应用必要条件

A、选择有助于简化问题、变难为易的必要条件

这里面就是说我们要在坚持“简化问题、变难为易”的原则下;尽力寻找“精确”的必要条件;以缩小求解范围;提高出解速度..当碰到一道难题时;总是尝试从最简单的特殊情况入手;找出有助于简化问题、变难为易的必要条件;逐渐深入;最终分析归纳出一般规律..

B、合成必要条件;从整体结构上优化

在搜索和动态规划中;必要条件有期很好的应用价值..一般地;对于深度优先搜索和广度优先搜索;如何限制搜索范围、减少搜索量最有效的手段是“剪枝” ..然而由于问题的错综复杂;所以我们要找最高效的优化条件;来提高程序的效率..所以我们可以尝试从多个侧面分析寻找必要条件;把问题分解;根据各部分的本质联系;将各方面的必要条件综合起来使用..

C、必要条件与原有模型比较、更新算法

上面所说的两种优化程序的策略其实是都是在“缩小求解范围” ;改进在有算法的基础上进行的;属于局部优化..然而精确选择揭示问题本质的必要条件;与原有的模型比较;

小结：必要条件是逻辑推到的理论依据;也是思考过程的一种取向..解题时;若能寻找出精确的必要条件;一方面能帮助我们揭示问题的本质;设计出正确的算法；另一种方面又能“缩小求解范围”;提高算法效率..因此;准确地应用必要条件是整体实现的关键..所以我们要在坚持“具体问题具体分析”的原则;不拘一格;灵活处理；在分析问题时;要勤于思考;善于发现..

1.2 整体思考的一个重要角度是“守恒”

A、从具体问题中抽象出守恒量

守恒量需要通过联想和化归思维将其抽象出来;从问题本身的结构中抽象出守恒量..

B、根据问题的本质构造守恒量

有时候;如果能为每一个元素标一个权值;就可以揭示问题“守恒”规律..在总价值不变的前提下;或许能将整个问题转化成一个简单的、或者是经典的问题..比如构造成Fibonacci数列等..

C、在交互式问题中构造变化中的不变量

考虑可能出现的各种情况和最优策略;找变化中的不变量;运用“守恒”法寻找解题的突破口

小结：守恒是问题分析问题的一种思维方式一种整体意识和解题方法;通过联想和化归思维将其抽象出来..

1.3 提高整体实现效率的基本途径是“充分利用有效信息”和“压缩冗余信息”

A.计算过程中充分利用有效信息：

在记忆化搜索和动态规划中充分利用信息;特别指出在动态规划中改变状态的表示含义对优化问题是个很好的策略..还有在数值计算中充分利用信息..

B.通过“压缩法”消除冗余的图形和数据信息

在图论的问题中;通过采用“缩点法” ;将具有等价意义的一类顶点压缩成一个顶点;来简化问题；还有就是压缩冗余信息..

1.4 改善整体性能状态的基础是处理好细节问题

细节是算法整体的关键部分;对整体起到“牵一发而动全身”的作用;是算法整体性能状态的基础..在程序设计中;细节的处理十分重要;应该对其取“举轻若重”的态度..许多事例证明：有时细节决定成败..

按照对算法的影响的性质和程度;可把细节分为如下几种情况：

1、影响正确性的细节问题..在解题过程中虽然已经找到解决方法;却不能通过全部测试数据;往往就是这类 的细节处理不当所致..

2、严重影响时间复杂度的细节..这类细节相当隐蔽;往往不为人所注意..但是这种细节影响时间复杂度的 阶;处理得好与不好往往会使程序的时间效率有质的区别..

3、轻微影响复杂度的细节..这类细节问题对时间复杂度没有根本性影响;仅仅对时间复杂度的系数有影响..

1.4.1 必须解决导致错误结果的细节问题

虽然已经找到正确的解法;但在程序实现的过程中;由于疏于细节而导致“功亏一篑”的事比比皆是;这种细节问题对整体的危害性最大..

1、

常见的错误类型

类型1：语法错误

类型2：书写错误

类型3：输入输出格式的错误

类型4：数据范围的错误

类型5：变量未初始化的错误

类型6：中间运算越界

类型7：局部变量与全局变量同名造成概念混乱

类型8：if – Then – Else 语句混乱..

类型 9: 实数比较出错..在比较两个实数是否相等时;如果直接用等号;往往会造成错误..这是浮点去得存在精度误差所造成的..

解决办法是使用两数差的绝对值与一个相对极小量进行比较;例如;如果absa-b<1e-8;则可认为 a == b..

2、

在程序运行的过程中跟踪错误

动态查错是指通过跟踪程序的执行过程;核对输出结果来发现错误..动态查错的技巧可分两大部分：测试用例的设计和测试的方法..

1.4.2 争取降低得法时间复杂度的阶

提高程序的时间效率的最明显的标志;是降低算法时间复杂度的阶数;而时间复杂度的阶数;并不是非得更新算法不可..有时;只要在程序的某些细节上做一些调整和修改;同样可以得到“牵一发而动全身”的效果..

1.4.3 注意降低算法时间复杂度的系数

这类细节对算法的整体影响虽然不算太大;但往往在关键的时候;时间复杂度系数

的大小对算法的效率也有比较明显的影响..因此;应该尽可能地优化细节处理;精益求精;使算法的时间复杂度的系数降低到一个比较理想的程度..

第2章 构造性思维

“构造法”解题;就是构造数学模型或方法解决问题;解题的思维方式就是所谓构造性思维..

“构造法”解题的思路或步骤：

1、

审题：了解题目的来龙去脉;弄清哪些量是已知的输入;需要求什么输出;数据规模如何;等等..这是解决问题的前提..

2、

建模：建立一个能够简洁地表达出原型本质的模型..

3、

分析和解决模型：分析模型的正确性..如果模型正确;则设计算法解决模型;解决模型的过程是否顺利;取决于所建模型的正确性和可解性如何..如果模型错误或不可解;则重新审题..

4、

编程实现..

2.1 模型的基本概念

当面对一个新问题时;通常的想法是通过分析;不断的转化和转换;得到本质相同的熟悉的、或抽象的、简单的一个问题;这就是化归思想..把初始的问题或对象称为原型;把化归后的相对定型的模拟化或理想化的对象称为模型..

2.1.1 模型的一般特点与功能

与实际问题相比;模型有以下几个性质和特点：

1、

等价性：模型和原型必须是本质相同的..

2、

抽象性：模型是实际问题的一种抽象;它去除了实际问题中与问题的求解无关的部分;简明地体现了问题的本质..

3、

高效性：模型中各个量之间的关系更为清晰;容易从中找到规律;从而提高求解的效率..由于这一点是由模型的抽象性决定的;因此模型的抽象化程度对模型效率的高低有重要的影响..

4、

可推广性：模型可以推广到具有相同性质的一类问题中..换句话说;解决了一个模型就解决了一类实际问题..

一般的;模型具有三大功能：

1、

解释功能：用模型说明事物发生的原因..

2、

判断功能：用模型判断认识的可靠性..

3、

预见功能：利用模型的知识、规律和未来的发展;为人们的行为提供指导或参考..

2.1.2 模型的一般分类

在ACM/ICPC竞赛中;常用的模型有图论模型、数学模型和规划整数规划和动态规划模型..

1、图论模型

通过图论化;本来复杂、凌乱的数据关系可变得简洁、明了;问题求解的思路因此而变得相对清晰..在许多情况下;可直接套用经典算法..

通常;数据之间的离散关系错综复杂可以考虑图论模型化..

建立图论模型必须注意：模型和原型的本质越接近越好..

2、组合数学模型

各种各样的计数问题都可考虑建立组合数学模型;最常用的组合数学模型是递归关系..虽然不探讨问题的数学规律而直接利用递归的回溯法计数;从理论上讲是可行的;但先求解组合数学的递归模型再计数可大大降低时间复杂度..

3、规划模型

规划模型是数学模型的一类;因其常见;故单独列出..它主要包括整数规划及动态规划模型..整数规划是所有变量均取整数的规划问题;这类问题的算法是阶乘级的..动态规划的决策、状态变量也是取整数的;但它的算法复杂度却是多项工级的..

带约束的多变量的求解问题;特别是约束条件中有满足某个函数的最大小值;可考虑建立规划模型..建立规划模型时;动态规划是首先;如果选择整数规划;则要注意算法的优化..

2.1.3 模型与信息原型间的关系

模型与信息原型间存在“多对一”或“一对多”的关系..

2.2 建模的一般方法

建立数学模型没有固定的套路可言;方法比较多样化..建模方法可分为机理分析法和统计分析法两大类；从思维方式的角度;建模方法又可分为直接构造法、分类构造法和归纳构造法三种形式..

建模的本质是挖掘数据间的关系和数据的变化规律;而“序”是隐藏在数据之间的一种常见的、却难以发现的关系..在建模时;如果能够在繁杂的数据中找到有价值的序;并加以合理应用;往往可使问题获得简化;便于问题的解决..

1建模的机理分析方法：直接建模、套用常用模型方法、有针对性的修改常用模型、综合创造..

2建模的统计分析方法：通过某种方法测试得到问题的部分解..再利用数理统计知识分析和处理数据;从而得到数学模型..统计分析法是采用逆向思维方式建模的..

2.3 建模的一般思维方式

构造数学模型;设计求解模型的一般方法;统称构造法．从思维方式的角度讲;常用构造法：直接构造法;分类构造法和归纳构造法．

2.3.1 直接构造法

直接对目标对象进行考察的构造方法称之为直接构造法．

过程： ①观察目标对象；

②发现一般规律；

③加以概括总结;并运用至构造中．探索是直接构造的灵魂

直接构造法需要解题者大胆猜想解题方法;并结合目标反复尝试;调整方案和数学推理证明．在构造多个方案的过程中;要注意从成立的方案中总结出结论;从不成立的方案中反思出正确的构造方法．

对于某些题目;很难直接给出一种＂必行＂的构造方法;这时就需要为它＂量身定做＂多个构造方法;这些构造相辅相成：某种构造成立可以导出结论的成立；不成立的构造方法也可以为其他的构造方法创造条件;如图所示：

构造A不成立

构造B不成立 构造D成立

构造C不成立

例如：区间染色问题P103

2.3.2 分类构造法

分类构造是分类的思想与构造法相结合的产物;简单说;就是在分类的基础上进行构造．

分类的思想：按照剩余系分类奇偶分类;按照数据大小分类;按照题目中涉及的定义概念分类;按照参数的变化分类等等．

题例：棋盘遍历问题P105

构造的分类标准与问题不同侧面的性质和选择的构造方法息息相关．

2.3.3 归纳构造法

这里主要指数学归纳法;归纳构造利用了归纳的思想;是构造法的一个经典的实现形式;在竞赛中;采用得比较普遍的仍然是一般归纳法＋构造法的形式．如图所示：

构造 i=1 的情况

利用归纳法;推广到

假设 i=1 已经构造 i=n 的情况

出来;构造 i=j+1

题例：赛程安排问题1P107 赛程安排问题2P108

2.4在建模过程中注意应用序关系

建模的本质是挖掘数据间的关系和数据的变化规律;而数据之间的＂序＂正是数据间关系和数据变化规律的一种表现形式;具有普遍性和隐蔽性的特征．在建模时;如果能够在繁杂的数据中找到有价值的序;并加以合理的应用;往往可使问题获得简化;便于问题的解决;本节结合实例;从以下三个方面讨论了序的作用：

①在交互式的试题中寻找合适的序;根据序的特性来进行交互．

②利用典型的序关系例如树和图的遍历简化问题．

③通过蕴涵在题意中的序关系来建立简洁;高效的解题模型．

不同的题目隐藏着不同的、可供挖掘的序..序的应用远远不止本节所述的这么简单..有些序不是什么典型的序关系;而是隐藏得很深..挖掘和构造序关系;需要有厚实的知识积累以及对数据间微妙关系的敏感..如果能够好好地利用序;那么序就像一双慧眼;使我们在眼花缭乱的数据关系中看清问题的实质;真正建立简洁;高效的解题模型..

2.5模型选择

由于探索信息原型的角度多种多样;因此可能产生多个数学模型..当一个信息原型对应多个正确的数学模型时;需要我们做抉择;并反复不断地将整个模型加以完善..一般遵循的原则是“边分析;边选择;兼顾四个标准时间复杂度、空间复杂度、编程复杂度和思维复杂度”..四个标准中应以时间复杂度为首要;因为竞赛对算法的运行时间有明确限制..

题例：最佳旅行路线问题 P124

第3章 目标转化的思想

目标转化的形式有两种：

1.“降维” ——缩小目标..

2.“升维” ——放大目标..其中维是指一个问题中元素的自由度;即该元素的坐标数;如数轴上的点的维数是1..

缩小目标的降维思想：

1.高维降为低维..

2.一般降为特殊.. 从极端情况入手..精简法..

3.抽象降为具体..

4.整体降为局部..如排列组合问题时;先从特殊元素;特殊位置这一局部出发..也

叫着分解法..

5.简化数据关系如二分图--->有向图、图--->树、树--->序列、二分图最佳匹配--->二分图的最大匹配..

6.在原数据结构的基础上简化数据关系..

放大目标的升维思想：

1.让步假设..：先通过条件放松、给以适当假设猜想等途径将问题求解的范围扩大;然后对简化了的新问题求解;最后;“剪掉”扩大部分;还原问题的解..

2.倍增思想..用途1;在变化规则相同的情况下加速状态转移..2;加速区间操作..：根据已经得到的信息;将考虑的范围扩大一倍;从面加速操作;即在变化规则相同的情况下加速状态转移;或者加速区间的操作..

3.割补法..

4.补集转化..

最后有几点很重要：敢于猜想;善于类比;寻找 相似点和突破口；勇于拓展;在已解决的旧问题上发现新问题..

第4章 分类处分治思想

分类是提示概念外延概念所反映事物的范围的逻辑方法;也是求解问题的一种基本思想方法..

分治是特殊的分类;通常与递归联系在一起..它的特点是划分后的子问题又是规模更小的原问题..

分类和分治的解题步骤一般为：

1.确定对象..

2.合理分类..

3.逐类讨论..

4.归纳结论..

常用的分类或分治法有：二分法、三分法、有限多分法..二分是最常用的分类或分治方法..它的要点如下：

1.选取一个标准;按照是否符合这个标准将所需讨论的问题分成两类..

2.在前次分类的基础上;选取另一标准将已分出的类再分成两类..

3.不断重复前一个过程;直至涌够再分为止..

二分思想居四种情况下应用形式：

1.应用于一般有序序列的二分法..

如：在给定的序列中“二分查找”;在交互式问题中应用“二分插入”..

2.应用于退化了的有序序列的“二分枚举”..

如：用二分枚举求可行方案;用二分枚举求最优性问题..

3.应用研究于无序序列的“二分搜索”..

如：在“二分搜索”的基础上构造可行解;在“二分搜索”的基础上构造最优解..

4.应用研究于多维情况的“多重二分”..

第5章 逆向思维

逆向思维的两种形式：

a：执果索因型逆向思维 b：由反及正型逆向思维

一：执果索因型逆向思维

如果满足条件A可得到结论B;那么由A推出B叫执因索果;反过来;由B推A的过程叫执果索因逆向思维..

方法执果索因型有两种实施方案：

a：设置结果参数;逆向搜索搜索分顺序搜索和二分搜索;这种方法通常用于这些问题：求最大最小问题此类问题具有单调性;使用参数搜索排除无效条件;将问题的不确定条件变为确定条件..

b：从目标状态出发逆向规划顺序规划一般采用自底向上的多重循环方式;逆向规划采用自顶向下记忆化递归方式

这两种方案中;参数搜索是解决最优性问题的一种常见方法;其本质就是对问题加入结果参数;

先通过贪心、动态规划或图论的一些方法判别这个参数代表的结果是否可行；反向规划在动态规划中;

从目标状态向初始化状态倒推..采用此两种方法时要注意时间复杂度..

二：由反及正逆向思维

实现逆向思维常有两种方法：

a：割补法先补后割中的“补”是设计一个包含解的正反面的“整体”;“割” 是在整体中淘汰解的反面;从而抵达解的正面;分为以下几种割补法：

1：计算几何中的割补法直接割补和利用叉积割补计算任意多边形面积;计算任意多边形的重心;判断点与多边形的位置关系..

2：计数问题中的割补法欲求解一定范围内满足条件的元素个数;不妨扩大求解范围;使用加法原理和乘法原理;抑或在统计中分别求解;再将多余部分删去;例如;使用容斥原理

1.加法原理和乘法原理可先使用乘法原理分别求出可能解的全集和不符合约束条件的解元素;然后将不符合约束条件的解元素从可能解的全集中减去;剩余的

解既是真正解

2.容斥原理：在统计问题中应用补集转化解决统计问题有一些常用解法;如离散化、极大化、二分、事件表...但是解决具有特殊性的统计问题应采用补集转化

以上两种思想作为一种非常规的解题方法;它们和一些常规的解题方法之间的关系是辩证的;大多数

问题还是适宜用常规方法的;所以灵活掌握常规方法和非常规方法;并结合具体问题选择合适的方法;

才能正确的解决统计问题..

第6章 猜想与实验

6.1相似联想

相似联想也称为类比联想;指由某一问题的条件和线索;就其形态和性质引起与其相似的已有知识和解题经验的联想;是借助于对某一事物的认识;通过比较它与另一事物的相似特征达到对后者的推测理解;因此它是一类对象的认识过渡到另一类对象的认识的思维方法..

相似联想的本质是类比;类比是得到猜想的重要方法..类比的基本方式有两种： 1与熟悉的问题类比;2与特殊的问题类比..与熟悉的问题进行类比的基本步骤是：1分析：分析问题的特征;抽象出出模型..

2联想：与熟悉的;拥有类似特征和模型的问题类比..

3比较：确定类比对象后将两者比较;分析异同..

4猜想：根据已知问题猜想新问题的解决方法..

与特殊问题的类比的一般步骤：

1观察：观察题目条件的特征..

2特殊化：将一些条件的位置;数量;状态等特殊化..

3分析特殊问题..

4类比..将特殊问题与原问题比较..

猜想：根据特殊化问题与原问题的联系和不同;以特殊问题的解决方案为蓝本;猜想原问题的解法..

6.2 归纳联想

6.2.1 指 通过对特例的分析来引出普通结论的一种推理形式

一般步骤

1 列举 将一些特殊的 简单的 小规模的数据列举出来 可以手推 或编写一些小的程序

2 观察 观察数据的规律

3 猜想 根据部分数据猜想一般结论

4 证明 通常用推理方法或数学归纳法证明猜想的正确性

6.2.2 归纳联想的实际应用 —— 注意观察 大胆的猜想

小结：体现 从特殊到一般 从简单到复杂 从小规模到大规模的化归思想要注意发散思维 充分想象 往任何可能的地方去想去靠

6.3从数与形的结合上联想：

联想的一般形式：a、“以形助数”；b、“以数助形”；

6.3.1 在数值计算中联想“以形助数”“以形助数”联想的一般步骤：

a、观察；观察题目条件的特征..

b、图形化;；联想问题的几何背景;将一些条件的位置、数量、状态等图示化..

c、类比；将图形化的问题与原问题作比较;用几何图形辅助思考..

d、迁移；根据图形化的问题与原问题的联系和不同;直接得出结论或转化问题..

e、猜想与实验；猜想转化为问题的解法;并验证其正确性..

6.3.2 在几何计算中联想“以数助形”“以数助形” 联想的一般步骤：

a、观察；观察图形的本质特征..

b、展开；“以数助形”的联想;即通过联想将图形转化成数字矩阵或抽象为数方程..

c、类比；将几何图形与数字矩阵或函数方程做比较;用数值的规律辅助是靠..

d、迁移；根据转化后的数值问题与几何图形的联系和不同;直接得出结论..

e、猜想与实验；猜想数值问题的解法;并验证其正确性..

6.4“回到起点”重新联想

“回到起点”重新联想的一半步骤：

a、明确“退”的方向；即确定当前算法是错误的或是非最有的;而最初的算法又不失其重要性..

b、“回到起点”；即回到初步分析处;展开丰富联想和严谨的理性思考;重新定义问题..寻找突破口..

c、猜想与实验；即在分析新旧问题异同点的基础上猜想改进方法;并验证新解法的正确性..