【假一罚四】计算思维工程实践(C++版)徐雅静编著

徐雅静，女，博士，北京邮电大学人工智能学院副教授。2003年毕业后在北邮执教，一直从事计算机系列课程的教学工作，并不断探索计算机教学的规律和方法，坚持将教学与实践相结合，参与了一系列的教学和教学改革工作。本人从2004年开始教授C++程序设计、数据结构、程序设计实践等一系列计算机类课程，目前是《数据结构》课程的负责人。

第1章 计算思维的本质

1.1 计算机的发明

1.1.1 计算机的数学原理

1.1.2 计算机的工程知识

1.2 思维方式概述

1.2.1 数学思维

1.2.2 计算思维

1.2.3 AI思维

1.2.4 大数据思维

本章小结

第2章 计算思维解决数学问题

2.1 多项式运算

2.1.1 一元多项式求值

2.1.2 多项式相乘

2.1.3 多项式相除

2.2 求解一元多项式的根

2.2.1 算法实践——二分法

2.2.2 算法实践——弦割法

2.2.3 思维扩展

2.3 求解定积分

2.3.1 算法实践——牛顿法

2.3.2 算法实践——蒙特卡罗随机投点法

2.3.3 算法实践——蒙特卡罗平均值法

2.4 最大公约数问题

2.4.1 算法实践——质因数分解法

2.4.2 算法实践——辗转相除法

2.4.3 算法实践——更相减损法

2.4.4 算法实践——Stein算法

2.5 随机数的产生

2.5.1 算法实践——线性同余法

2.5.2 思维扩展

本章小结

第3章 计算思维解决数学技巧

3.1 寻找数组中的最大值和最小值

3.1.1 算法实践——独立求解

3.1.2 算法实践——快速求解

3.1.3 算法实践——快速求解

3.1.4 算法实践——分治法

3.2 计算最大值和次大值

3.2.1 算法实践——分步计算

3.2.2 算法实践——同步计算

3.3 数组循环移位

3.3.1 算法实践——循环右移N位

3.3.2 算法实践——三次翻转法

3.4 奇数偶数分离问题

3.4.1 算法实践——简单算法

3.4.2 算法实践——二分区算法

3.4.3 思维扩展——荷兰国旗问题

3.5 数制转换问题

3.5.1 算法实践——递归

3.5.2 算法实践——栈

3.6 删除重复元素问题

3.6.1 算法实践——简单算法

3.6.2 算法实践——最优算法

3.7 连续最大数值问题

本章小结

第4章 计算思维解决抽象问题

4.1 比赛名次问题

4.2 抢20游戏问题

4.3 莫尔斯码问题

4.3.1 编码思维

4.3.2 问题分析

4.3.3 算法实践——编码思维

4.4 微信红包算法

4.4.1 问题分析

4.4.2 算法实践

4.5 智力拼图问题

4.5.1 问题分析

4.5.2 算法设计——BFS算法

4.5.3 算法实现

4.6 基因序列相似度问题

4.6.1 问题分析

4.6.2 算法设计——动态规划

4.6.3 算法实现

4.7 地铁线路查询问题

4.7.1 问题分析

4.7.2 数据整理

4.7.3 数据结构设计

4.7.4 优化的Dijkstra算法实现

4.7.5 完整的类实现

本章小结

第5章 计算思维解决通用问题

5.1 总和最大区间问题

5.1.1 问题分析

5.1.2 算法实现——三重循环O（n3）

5.1.3 算法实现——二重循环O（n2）

5.1.4 算法实现——分治法O（nlogn）

5.1.5 算法实现——正反扫描法O（n）

5.1.6 算法实现——动态规划O（n）

5.1.7 算法变形——连续最大数值问题

5.2 矩阵问题

5.2.1 矩阵相乘

5.2.2 大规模矩阵相乘

5.3 矩阵应用——BMP图像处理

5.3.1 BMP文件结构分析

5.3.2 简单图像处理——平滑技术

本章小结

第6章 计算思维与智能控制

6.1 电梯调度分析

6.2 俄罗斯方块游戏分析

6.3 相关基础知识

6.3.1 控制台数据类型

6.3.2 常用系统函数

6.3.3 控制台相关的API及封装

6.3.4 多线程和互斥信号量

6.3.5 编程技巧

6.4 电梯调度控制——工程实践

6.4.1 设计思想

6.4.2 函数设计

6.4.3 函数实现

6.5 俄罗斯方块——工程实践

6.5.1 设计思想

6.5.2 类设计

6.5.3 类实现

本章小结

第7章 计算思维与文本处理

7.1 字符串的拷贝、比较和统计

7.1.1 字符串拷贝

7.1.2 字符串比较

7.1.3 字符串统计

7.2 字符串相似度问题

7.2.1 算法实践——编辑距离

7.2.2 算法实践——最小操作次数

7.2.3 算法实践——最长公共子序列

7.3 字符串匹配问题

7.3.1 算法实践——BF算法

7.3.2 算法实践——KMP算法

7.4 AC自动机

7.4.1 问题分析

7.4.2 工程实践

7.4.3 扩展思考

7.5 AC自动机的应用——中文分词

7.5.1 问题分析

7.5.2 工程实践

7.6 AC自动机的应用——搜索引擎之倒排索引

7.6.1 问题分析

7.6.2 工程实践

本章小结

参考文献

本教材围绕计算本质，将计算思维和数学思维、AI思维、大数据思维之间的关系进行了阐述，进而针对计算思维解决数学问题、计算思维解决数学技巧、计算思维解决抽象问题、计算思维解决通用问题、计算思维与智能控制和计算思维与文本处理等６个章节，精心设计实践案例，并从不同思维角度、按照不同效率原则对案例进行了逐步实现，从而为学生在课后进行编程实践提供更多、更好的素材。本教材内容按照由浅入深、由简单到复杂的方式进行组织，内容丰富，案例设计覆盖了简单数学问题和复杂的线路查询问题、智能控制以及文本分词和检索等应用，贴合生活和工程实践，章节内容层次合理、设计科学。