程序设计中常用的计算思维方式 第1 章 正确认识和处理整体与部分的关系 概述: “整体”与“部分”是一对虽然对立、但并非僵化不变的概念
在一定条件下,“部分”可以看作“整体” ,“整体”又可以看作是另一个“整体”的“部分” ,两者相互依存和影响
“整体”与“部分”又可以相互转化的
“整体”的问题可以分割成“部分”来处理,“部分”的问题也可以通过“整体”来解决
1 整体实现的关键是准确地应用必要条件 A、选择有助于简化问题、变难为易的必要条件 这里面就是说我们要在坚持“简化问题、变难为易”的原则下,尽力寻找“精确”的必要条件,以缩小求解范围,提高出解速度
当碰到一道难题时,总是尝试从最简单的特殊情况入手,找出有助于简化问题、变难为易的必要条件,逐渐深入,最终分析归纳出一般规律
B、合成必要条件,从整体结构上优化 在搜索和动态规划中,必要条件有期很好的应用价值
一般地,对于深度优先搜索和广度优先搜索,如何限制搜索范围、减少搜索量最有效的手段是“剪枝”
然而由于问题的错综复杂,所以我们要找最高效的优化条件,来提高程序的效率
所以我们可以尝试从多个侧面分析寻找必要条件,把问题分解,根据各部分的本质联系,将各方面的必要条件综合起来使用
C、必要条件与原有模型比较、更新算法 上面所说的两种优化程序的策略其实是都是在“缩小求解范围” ,改进在有算法的基础上进行的,属于局部优化
然而精确选择揭示问题本质的必要条件,与原有的模型比较, 小结:必要条件是逻辑推到的理论依据,也是思考过程的一种取向
解题时,若能寻找出精确的必要条件,一方面能帮助我们揭示问题的本质,设计出正确的算法;另一种方面又能“缩小求解范围” ,提高算法效率
因此,准确地应用必要条件是整体实现的关键
所以我们要在坚持“具体问题具体分析”的原则,不拘一格,灵活处理;在分析问题时,要勤于思考,善于发现