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

《程序设计中常用的计算思维方式》由会员分享，可在线阅读，更多相关《程序设计中常用的计算思维方式（6页珍藏版）》请在文档大全上搜索。

1、程序设计中常用的计算思维方式第1章正确认识和处理整体与部分的关系概述：“整体”与“部分”是一对虽然对立、但并非僵化不变的概念。在一定条件下，“部分”可以看作“整体” ，“整体”又可以看作是另一个“整体”的“部分”，两者相互依存和影响。“整体”与“部分”又可以相互转化的。 “整体”的问题可以分割成“部分”来处理，“部分”的问题也可以通过“整体”来解决。1.1整体实现的关键是准确地应用必要条件A、选择有助于简化问题、变难为易的必要条件这里面就是说我们要在坚持“简化问题、变难为易”的原则下，尽力寻找“精确”的必要条件，以缩小求解范围，提 高出解速度。当碰到一道难题时，总是尝试从最简单的特殊情况入手，

2、找出有助于简化问题、变难为易的必要条件，逐渐 深入，最终分析归纳出一般规律。B、合成必要条件，从整体结构上优化在搜索和动态规划中，必要条件有期很好的应用价值。一般地，对于深度优先搜索和广度优先搜索，如何限制搜索范 围、减少搜索量最有效的手段是“剪枝”。然而由于问题的错综复杂，所以我们要找最高效的优化条件，来提高程序的效率。所以我们可以尝试从多个侧面分析寻找必要条件，把问题分解，根据各部分的本质联系，将各方面的必要条件综合起 来使用。C、必要条件与原有模型比较、更新算法上面所说的两种优化程序的策略其实是都是在“缩小求解范围”，改进在有算法的基础上进行的，属于局部优化。然而精确选择揭示问题本质的必

3、要条件，与原有的模型比较，小结：必要条件是逻辑推到的理论依据，也是思考过程的一种取向。解题时，若能寻找出精确的必要条件，一方面能帮助 我们揭示问题的本质，设计出正确的算法；另一种方面又能“缩小求解范围”，提高算法效率。因此，准确地应用必要条件是整体实现的关键。所以我们要在坚持“具体问题具体分析”的原则，不拘一格，灵活处理；在分析问题时，要勤于思 考，善于发现。1.2整体思考的一个重要角度是“守恒”A、从具体问题中抽象出守恒量守恒量需要通过联想和化归思维将其抽象出来，从问题本身的结构中抽象出守恒量。B、根据问题的本质构造守恒量有时候，如果能为每一个元素标一个权值，就可以揭示问题“守恒”规律。在总

4、价值不变的前提下，或许能将整个问 题转化成一个简单的、或者是经典的问题。比如构造成Fibonacci数列等。C、在交互式问题中构造变化中的不变量考虑可能出现的各种情况和最优策略，找变化中的不变量，运用“守恒”法寻找解题的突破口 小结：守恒是问题分析问题的一种思维方式一种整体意识和解题方法，通过联想和化归思维将其抽象出来。1.3提高整体实现效率的基本途径是“充分利用有效信息”和“压缩冗余信息”A. 计算过程中充分利用有效信息：在记忆化搜索和动态规划中充分利用信息，特别指出在动态规划中改变状态的表示含义对优化问题是个很好的策略。 还有在数值计算中充分利用信息。B. 通过“压缩法”消除冗余的图形和数

5、据信息在图论的问题中，通过采用“缩点法”，将具有等价意义的一类顶点压缩成一个顶点，来简化问题；还有就是压缩冗余信息。1.4改善整体性能状态的基础是处理好细节问题 细节是算法整体的关键部分，对整体起到“牵一发而动全身”的作用，是算法整体性能状态的基础。在程序设计中，细节 的处理十分重要，应该对其取“举轻若重”的态度。许多事例证明：有时细节决定成败。按照对算法的影响的性质和程度，可把细节分为如下几种情况：1、影响正确性的细节问题。在解题过程中虽然已经找到解决方法却不能通过全部测试数据，往往就是这类的细节处理不当所致。2、 严重影响时间复杂度的细节。这类细节相当隐蔽，往往不为人所注意。但是这种细节影

6、响时间复杂度的阶，处理得好 与不好往往会使程序的时间效率有质的区别。3、轻微影响复杂度的细节。这类细节问题对时间复杂度没有根本性影响，仅仅对时间复杂度的系数有影响。1.4.1必须解决导致错误结果的细节问题虽然已经找到正确的解法，但在程序实现的过程中，由于疏于细节而导致“功亏一篑”的事比比皆是，这种细节问题对整 体的危害性最大。1、常见的错误类型类型1 :语法错误类型2 :书写错误类型3:输入输出格式的错误类型4 :数据范围的错误类型5:变量未初始化的错误类型6:中间运算越界类型7:局部变量与全局变量同名造成概念混乱类型8: if -Then -Else语句混乱。类型9:实数比较出错。在比较两个

7、实数是否相等时，如果直接用等号，往往会造成错误。这是浮点去得存在精度误差所 造成的。解决办法是使用两数差的绝对值与一个相对极小量进行比较，例如，如果abs（a-b）1e-8，则可认为a = b。2、在程序运行的过程中跟踪错误动态查错是指通过跟踪程序的执行过程，核对输出结果来发现错误。动态查错的技巧可分两大部分：测试用例的设计和测 试的方法。1.4.2争取降低得法时间复杂度的阶提高程序的时间效率的最明显的标志，是降低算法时间复杂度的阶数，而时间复杂度的阶数，并不是非得更新算法不可。有时，只要在程序的某些细节上做一些调整和修改，同样可以得到“牵一发而动全身”的效果。1.4.3注意降低算法时间复杂度

8、的系数这类细节对算法的整体影响虽然不算太大，但往往在关键的时候，时间复杂度系数的大小对算法的效率也有比较明显的影响。因此，应该尽可能地优化细节处理，精益求精，使算法的时间复杂度的系数降低到一个比较理想的程度。第2章构造性思维“构造法”解题，就是构造数学模型或方法解决问题，解题的思维方式就是所谓构造性思维。“构造法”解题的思路或步骤：1、 审题：了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何，等等。这是解决问 题的前提。2、建模：建立一个能够简洁地表达出原型本质的模型。3、分析和解决模型：分析模型的正确性。如果模型正确，则设计算法解决模型，解决模型的过程是否顺利

9、，取决于所建 模型的正确性和可解性如何。如果模型错误或不可解，则重新审题。4、编程实现。2.1模型的基本概念当面对一个新问题时，通常的想法是通过分析，不断的转化和转换，得到本质相同的熟悉的、或抽象的、简单的一个问题，这就是化归思想。把初始的问题或对象称为原型，把化归后的相对定型的模拟化或理想化的对象称为模型。2.1.1模型的一般特点与功能与实际问题相比，模型有以下几个性质和特点：1、等价性：模型和原型必须是本质相同的。2、抽象性：模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。3、高效性：模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解

10、的效率。由于这一点是由模型的抽象 性决定的，因此模型的抽象化程度对模型效率的高低有重要的影响。4、可推广性：模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个模型就解决了一类实际问题。 一般的，模型具有三大功能：1、解释功能：用模型说明事物发生的原因。2、判断功能：用模型判断认识的可靠性。3、预见功能：利用模型的知识、规律和未来的发展，为人们的行为提供指导或参考。2.1.2模型的一般分类在ACM/ICPC竞赛中，常用的模型有图论模型、数学模型和规划（整数规划和动态规划）模型。1、图论模型通过图论化，本来复杂、凌乱的数据关系可变得简洁、明了，问题求解的思路因此而变得相对清晰。在许多情况

11、下，可直 接套用经典算法。通常，数据之间的离散关系错综复杂可以考虑图论模型化。建立图论模型必须注意：模型和原型的本质越接近越好。2、组合数学模型各种各样的计数问题都可考虑建立组合数学模型，最常用的组合数学模型是递归关系。虽然不探讨问题的数学规律而直接 利用递归的回溯法计数，从理论上讲是可行的，但先求解组合数学的递归模型再计数可大大降低时间复杂度。3、规划模型规划模型是数学模型的一类，因其常见，故单独列岀。它主要包括整数规划及动态规划模型。整数规划是所有变量均取整 数的规划问题，这类问题的算法是阶乘级的。动态规划的决策、状态变量也是取整数的，但它的算法复杂度却是多项工级 的。带约束的多变量的求解