Following and writing algorithms

欢迎来到算法的编写与追踪！

你好，未来的程序员！本章至关重要，因为算法是计算机科学的灵魂。你可以把算法想象成一套完美且万无一失的指令集。无论你是要烤面包还是开发下一个超级 App，你都需要清晰的执行步骤。

在本节中，我们将学习如何阅读和理解这些指令，如何将它们转化为实际的编程语言，以及最重要的——如何手动检查它们是否按预期工作，这一技能被称为“手动追踪”（hand tracing）。即使写代码对你来说还有些挑战，掌握了这里的逻辑，编程将变得简单得多。让我们开始吧！

1. 理解算法 (3.3.3 内容)

在遵循指令之前，我们需要明确这些指令到底是什么。

什么是算法？

算法 (algorithm) 定义为完成某项任务所遵循的一系列步骤，并且这些步骤必须最终终止。

• 一系列步骤： 指令必须按逻辑排序。第 2 步必须在第 1 步之后执行。
• 完成任务： 它必须实现预期的目标（例如：对列表排序、计算税额、烘焙蛋糕）。
• 最终终止： 这一点至关重要！算法必须在有限时间内结束，绝不能陷入无限循环。

类比： 把算法想象成一份食谱。
如果你按部就班地照着食谱做，你应该能成功完成任务（烤好蛋糕），而且一旦蛋糕做好了，过程就会停止（它终止了）。如果食谱告诉你“一直搅拌，直到天荒地老”，那它就不是一个算法，因为它可能永远不会停止！

2. 使用伪代码表示算法 (3.3.3 内容)

算法通常使用伪代码 (pseudocode) 来表示。伪代码并不是一种真正的编程语言；它是对程序步骤的一种非正式的、高级的描述。

它可以帮助程序员在设计逻辑时，不必受制于 Python 或 Java 等语言具体的语法规则。

考试注意事项： 你需要熟悉如何使用伪代码来表达算法，并能够理解用伪代码编写的算法。但是，考试中不需要你自己编写伪代码。这意味着你的重点应放在准确阅读和解读伪代码上。

需要掌握的关键伪代码结构

要理解伪代码，你必须识别以下基本控制结构：

1. 顺序 (Sequence)： 按步骤依次执行。
示例：

INPUT Number1
INPUT Number2
Total = Number1 + Number2
OUTPUT Total


2. 选择 (Selection)： 根据条件选择不同的执行路径。
示例：

IF Score >= 50 THEN
OUTPUT "Pass"
ELSE
OUTPUT "Fail"
ENDIF


3. 迭代 (Iteration)： 重复执行一段代码。

• 确定性迭代 (FOR 循环)： 当你知道循环确切要执行多少次时使用。
  示例： FOR Count = 1 TO 10 DO ... ENDFOR
• 不确定性迭代 (WHILE 循环或 REPEAT UNTIL)： 当重复次数未知，循环直到满足特定条件时使用。
  示例： WHILE UserInput <> "Stop" DO ... ENDWHILE

你知道吗？ 许多编程语言在伪代码的编写规则上略有不同。关键在于，无论使用什么关键字，其背后的*逻辑*始终保持清晰。

3. 将伪代码转换为高级语言代码 (3.3.3 内容)

下一个重要技能是将伪代码中抽象的逻辑翻译成使用特定高级语言（如 Python、Java 或 C#）的具体指令。

这一步要求你理解所选编程语言的语法规则，并将伪代码结构映射到相应的代码结构中。

翻译步骤示例

让我们将一段计算数字 $N$ 的阶乘的伪代码转换为代码。

伪代码：

Factorial = 1
INPUT N
FOR Count = 1 TO N DO
    Factorial = Factorial * Count
ENDFOR
OUTPUT Factorial

转换（以 Python 为例）：

1. 初始化： 伪代码设定 `Factorial = 1`。在代码中，我们直接赋值。
2. 输入： 伪代码获取 `N`。在代码中，我们使用输入函数，并确保变量为整数。
3. 迭代： `FOR Count = 1 TO N` 循环。在代码中，这变为 `for` 循环（如 `for i in range(1, N+1):`）。
4. 计算： 核心计算 `Factorial = Factorial * Count` 几乎保持不变。
5. 输出： 显示结果。

最终代码结构（Python 示例）：

Factorial = 1
N = int(input("Enter number: ")) # 获取输入

for Count in range(1, N + 1):
    Factorial = Factorial * Count

print(Factorial)

挑战在于确保你所选语言的特定规则（例如 Python 的索引从 0 开始或 `range` 函数的工作方式）能正确体现伪代码的逻辑意图。

4. 算法的手动追踪 (3.3.3 内容)

手动追踪 (Hand tracing) 是指使用一组特定的输入数据，一步步模拟算法执行的过程。这对于在计算机运行代码之前发现逻辑错误（Bug）至关重要。

为了高效追踪算法，我们使用追踪表 (trace table)。

追踪表：你的侦探工具

追踪表可以记录算法在每一步执行时，相关变量的值及产生的输出。

追踪表的结构：

• 一列用于记录正在执行的算法的行号/步骤。
• 每一变量对应一列。
• 一列用于记录条件检查（例如 WHILE 条件是 True 还是 False）。
• 一列用于记录算法产生的输出。

鼓励一下： 如果起初觉得这很难，别担心，多练习就好！追踪就像学习读乐谱——你在训练大脑完美地跟随逻辑流。

手动追踪示例演练

以输入 N = 3 追踪以下伪代码。

1. Factorial = 1
2. INPUT N
3. FOR Count = 1 TO N DO
4.     Factorial = Factorial * Count
5. ENDFOR
6. OUTPUT Factorial

追踪表：

步骤	N	Count	Factorial	输出
1	-	-	1
2 (输入 3)	3	-	1
3 (开始循环, Count=1)	3	1	1
4 (1 * 1)	3	1	1
3 (下一次迭代, Count=2)	3	2	1
4 (1 * 2)	3	2	2
3 (下一次迭代, Count=3)	3	3	2
4 (2 * 3)	3	3	6
3 (循环结束, Count > N)	3	-	6
6	3	-	6	6

追踪的核心要点：

最终输出为 6（即 3 的阶乘：\(3 \times 2 \times 1\)）。通过细致地记录 Factorial 变量的每一次变化，我们验证了该算法对于输入 N=3 的执行完全符合预期。