欢迎来到算法的世界！
你好！今天我们将深入探讨计算机科学中最重要的部分之一：算法（Algorithms）。别被这个名词吓倒了——算法其实就是为了解决问题或完成任务而设计的一系列步骤指令。无论是你跟着食谱烤蛋糕，还是告诉朋友怎么去你家，你在日常生活中其实已经在使用算法了！
在本章中，我们将学习如何设计这些指令，让计算机能够理解它们，学习如何找出错误，以及如何让我们的解决方案运行得尽可能快。
1.1 构建基础：分解与抽象
在编写算法之前，我们需要像计算机科学家一样思考。我们通过计算思维（Computational Thinking）来做到这一点。其中两个最重要的工具是分解（Decomposition）和抽象（Abstraction）。
分解
分解是指将复杂的问题拆解成较小、较易处理的部分。
例子： 如果你想制作一款电子游戏，你不会只是“编写游戏”。你会把它拆解为：1. 角色移动、2. 计分系统、3. 图像显示，以及 4. 音效。解决四个小问题比解决一个大问题要容易得多！
抽象
抽象是指移除不必要的细节，将焦点放在重要的部分上。
例子： 看看伦敦地铁图。它不会显示每一条街道或建筑物，它只显示车站和路线。通过抽象化那些额外的细节，地图变得更容易使用。
子程序
子程序（Subprogram）是一小段用来执行特定任务的程序代码，可以在需要时随时“调用”它。
子程序的好处：
• 你不需要重复编写相同的程序代码。
• 它使程序更容易阅读和测试。
• 不同的人可以同时编写不同的子程序。
快速回顾：分解 = 拆解问题。抽象 = 简化信息。子程序 = 可重用的代码块。
1.2 算法的表示方式
在我们我们将算法输入计算机之前，主要有两种“绘制”或“编写”算法的方法：流程图（Flowcharts）和伪代码（Pseudocode）。
流程图
流程图使用不同的形状来显示程序执行的路径。以下是你必须知道的形状：
• 椭圆形（终止符）： 用于“开始”和“结束”。
• 平行四边形： 用于输入（例如：询问姓名）和输出（例如：显示结果）。
• 矩形： 用于处理（例如：像 \(x = y + 2\) 这样的运算）。
• 菱形： 用于决策（例如：“分数是否大于 50？”）。这个形状总是有两个箭头伸出：一个用于“是/真（Yes/True）”，另一个用于“否/假（No/False）”。
伪代码
伪代码是一种编写指令的方式，它看起来像程序语言，但使用的是平实的英文。它没有严格的“文法”规则，所以你不必担心漏掉分号！
例子：
OUTPUT "请问你的年龄是多少？"
INPUT userAge
IF userAge >= 18 THEN OUTPUT "你可以投票！"
1.3 程序设计结构
世界上每一个算法都是由三种基本结构构建而成的：
1. 顺序（Sequence）： 按特定的顺序，一个接一个地完成指令。
2. 选择（Selection）： 使用 IF、THEN 和 ELSE 进行选择。
3. 迭代（重复，Iteration）： 多次循环执行指令。有两种类型：
• 计数控制： 当你知道确切重复次数时使用（例如：FOR 循环）。
• 条件控制： 当你希望重复执行直到某个条件改变时使用（例如：WHILE 循环）。
关键总结： 每个程序都只是步骤（顺序）、选择（选择）和循环（迭代）的组合。
1.4 运算符与数据
为了进行运算和决策，我们使用运算符（Operators）。可以把这些想象成你算法中的“动词”。
算术运算符
这些用于数学运算：
• 加法： \(+\)
• 减法： \(-\)
• 乘法： \(*\)
• 除法： \(/\)
• 整除（DIV）： 告诉你一个数字能被另一个数字除几次，并忽略余数（例如：\(7 \text{ DIV } 2 = 3\)）。
• 取模（MOD）： 只告诉你余数（例如：\(7 \text{ MOD } 2 = 1\)）。
• 指数： \(^\)（例如：\(2 ^ 3 = 8\)）。
关系与逻辑运算符
这些帮助计算机进行决策：
• 关系： ==（等于）、!=（不等于）、<（小于）、>（大于）。
• 逻辑： AND（两者必须同时为真）、OR（至少一个为真）、NOT（反转结果）。
常见错误： 不要混淆 = 和 ==。在许多程序语言中，单个 = 用于设定数值（赋值），而 == 则是询问“它们相等吗？”（比较）。
1.5 寻找与修正错误
即使是最优秀的程序员也会犯错！你需要知道以下三种错误类型：
1. 语法错误（Syntax Error）： 程序代码中的“文法”错误（例如：将 PRINT 拼写为 PRUNT）。程序将无法启动。
2. 逻辑错误（Logic Error）： 程序可以执行，但给出的答案是错误的。例如，你想将两个数字相加，却不小心输入了减号。
3. 运行时错误（Runtime Error）： 程序在执行过程中发生的错误，导致崩溃（例如：要求计算机除以零）。
追踪表
追踪表（Trace Table）是一种用来追踪变量数值的工具，当你逐行执行算法时，它可以帮助你找出逻辑错误。
如何使用： 为每个变量建立一个栏位，并为输出建立一个栏位。每次程序代码改变数值时，就更新对应的栏位。
1.6 标准算法：搜索与排序
你需要理解这四个经典算法是如何运作的。想象一下你有一叠乱序的试卷，你需要找到某位学生的试卷，或者按字母顺序排列它们。
搜索算法
1. 线性搜索（Linear Search）： 你从头到尾一个一个地查看列表中的每个项目。它适用于任何列表，但对于大型数据集来说速度很慢。
2. 二分搜索（Binary Search）： 快得多！你直接跳到列表的中间。如果你要找的项目比中间值小，就丢弃右半部分；如果更大，就丢弃左半部分。重复此过程直到找到为止。
重要事项： 二分搜索仅适用于已经排序过的列表。
排序算法
1. 冒泡排序（Bubble Sort）： 你比较相邻的两个项目，如果顺序不对就交换它们。你不断地在列表中“循环扫描”，直到不需要再进行任何交换为止。
2. 合并排序（Merge Sort）： 一种“分而治之”的算法。你将列表拆分为单个项目，然后将它们按正确顺序合并起来。这对于大型列表来说非常快！
记忆小撇步： “线性（Linear）”就像一条线（line）；“二分（Binary）”就像二分法（bi-secting，切成两半）。
1.7 算法效率
我们如何知道一个算法是否“好”？我们基于以下两点评估其效率：
• 时间： 需要多少次比较或扫描？
• 空间： 使用了多少内存？
例子： 二分搜索比线性搜索更有效率，因为它通常只需更少的步骤就能找到答案。
关键总结： 不仅要找到解决方案，更要找到最快且最简洁的解决方案！