计算思维训练——问题解决与算法设计

本书编者倡导“自主编程”，以问题解决为主 线，致力于提升读者的计算思维与编程技能，引导 读者科学地学习算法。全书共分为四章：第一章重 点阐述数据抽象的方法及如何选择合适的数据结构 ，并介绍线性数据结构的基本应用；第二章通过生 动的例子，详述了模拟、解析和贪心这三种策略， 展示了如何结合严密的算法逻辑与实际操作经验来 解决问题；第三章则以深入浅出的方式，讲解了“ 大化小”的思维方式，介绍了如何利用递推、分治 和动态规划等算法来简化和解决复杂问题；第四章 全面剖析了好算法的标准，并详细介绍了优化算法 时间复杂度和空间复杂度的常用技巧。 本书可以作为数据结构和算法入门的培训教材 ，也可以作为准备参加全国信息学奥林匹克竞赛的 学生赛前集训用书，还可以作为有一定编程语言基 础的算法爱好者的参考书籍。

第一章 “巧”存数据解决问题 第一节 最强大脑问题——用数组解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第二节 消消乐问题——用栈解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第三节 巧解QQ号问题——用队列解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第四节 法雷序列问题——用链表解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第二章 用经验解决问题 第一节 幻方构造问题——用模拟法解决问题 一、问题引入 二、问题探究 三、知识构建 四、迁移应用 五、拓展提升 第二节 数字方阵问题——用解析法解决问题 一、问题引入 二、问题探究 三、知识构建 四、迁移应用 五、拓展提升 第三节 股票买卖问题——用贪心算法解决问题 一、问题引入 二、问题探究 三、知识构建 四、迁移应用 五、拓展提升 第三章 用“大化小”思想解决问题 第一节 走楼梯问题——用递推算法解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第二节 逆序对问题——用分治算法解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第三节 捡金币问题——用动态规划算法解决问题 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第四章 “精益求精”地解决问题 第一节 抽大奖问题——算法评价的基本方法 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第二节 切水果问题——优化算法时间复杂度的方法 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 第三节 旅行包问题——优化算法空间复杂度的方法 一、问题引入 二、问题探究 三、知识建构 四、迁移应用 五、拓展提升 习题解析 参考文献