第三章算法与程序实现

3.1 算法概念与特征

什么是算法？

算法（Algorithm）是解决特定问题的一系列明确、有限的步骤。就像做一道菜的食谱，算法告诉计算机"做什么"和"怎么做"。

生活算法

泡茶的算法：①烧开水 → ②准备茶叶和茶具 → ③水开后倒入茶壶 → ④等待3分钟 → ⑤倒入茶杯享用。这就是一个简单的生活算法！

算法的五大特征

有穷性：算法必须在有限步骤内结束，不能无限循环
确定性：每一步都有明确的定义，不会产生歧义
可行性：每一步都可以通过基本操作实现
输入：算法有零个或多个输入
输出：算法至少有一个输出

算法的评价标准

正确性：算法是否能正确解决问题
可读性：算法是否容易理解和维护
健壮性：算法对异常输入的处理能力
效率：时间复杂度和空间复杂度

3.2 流程图与伪代码

流程图符号

流程图是用图形符号表示算法的工具，直观易懂：

椭圆形：开始/结束
矩形：处理步骤
菱形：判断/决策
平行四边形：输入/输出
箭头：流程方向

互动实验：判断闰年的流程图

以下是用流程图表示的判断闰年算法，点击步骤查看详细说明：

开始

输入年份year

year%4==0?

year%100!=0
或
year%400==0?

输出结果

结束

伪代码

伪代码是介于自然语言和编程语言之间的描述方式，不需要严格遵守语法规则：

算法：判断闰年
输入：年份 year
输出：是否闰年

如果 year 除以 4 的余数等于 0 则
    如果 year 除以 100 的余数不等于 0 或 year 除以 400 的余数等于 0 则
        返回 "是闰年"
    否则
        返回 "不是闰年"
否则
    返回 "不是闰年"
                

3.3 程序设计语言发展史

从机器语言到高级语言

程序设计语言的发展经历了三个重要阶段，每一次飞跃都让编程变得更加高效和人性化：

第一代：机器语言（1940s）

特点：由0和1组成的二进制指令，计算机唯一能直接执行的语言。

0001 0010 0011   ; 加载数据到寄存器
0101 0110 0111   ; 执行加法运算
1001 1010 1011   ; 存储结果到内存
                        

优点：执行效率最高，直接操控硬件
缺点：难以记忆、编写困难、极易出错、可移植性差

第二代：汇编语言（1950s）

特点：用助记符代替二进制指令，如MOV、ADD、SUB等。

; 计算 A + B = C
MOV AX, [A]      ; 将A的值加载到寄存器AX
ADD AX, [B]      ; AX加上B的值
MOV [C], AX      ; 将结果存入C
                        

优点：比机器语言易读，保留了硬件操控能力
缺点：仍依赖具体硬件，需要汇编器翻译，开发效率低

第三代：高级语言（1957至今）

特点：接近自然语言和数学表达式，屏蔽了硬件细节。

# Python：计算 A + B = C
A = 10
B = 20
C = A + B
print("结果是:", C)  # 输出：结果是: 30
                        

优点：易学易用、可移植性强、开发效率高、便于维护
代表语言：Fortran、C、Java、Python、JavaScript等

为什么叫"高级"？

高级语言的"高级"是相对于机器语言和汇编语言而言的。它更接近人类思维习惯，程序员不需要了解计算机硬件细节，可以专注于解决问题本身。

三种语言的对比

对比维度	机器语言	汇编语言	高级语言
表现形式	二进制 0101	助记符 MOV/ADD	英语+数学式
可读性	极差	较差	好
执行效率	最高	高	中等
可移植性	无	差	强
开发效率	极低	低	高

3.4 程序设计基本知识

变量（Variable）

变量是程序中用于存储数据的容器，就像一个贴有标签的盒子，盒子里可以存放不同的值。

生活类比

变量就像书包：书包的名字是"变量名"（如myBag），书包里装的东西是"变量值"（如语文书、数学书）。你可以随时更换书包里的物品，但书包的名字不变。

变量的命名规则

只能包含字母、数字和下划线（_）
不能以数字开头
不能是Python关键字（如if、for、while等）
区分大小写（Name和name是不同的变量）

# 正确的变量命名
name = "张三"
age = 16
_height = 1.75
student_name = "李四"   # 推荐：下划线命名法

# 错误的变量命名
# 2name = "错误"       # 不能以数字开头
# my-name = "错误"     # 不能包含连字符
# class = "错误"       # 不能用关键字
                

数据类型

不同类型的数据在计算机中存储方式不同，Python常见数据类型：

字符串 str

用于存储文本

name = "张三"

整数 int

用于存储整数

age = 16

浮点数 float

用于存储小数

pi = 3.14159

布尔值 bool

用于存储真/假

is_ok = True

运算符及表达式

1. 算术运算符

运算符	名称	示例	结果
+	加法	5 + 3	8
-	减法	5 - 3	2
*	乘法	5 * 3	15
/	除法	5 / 2	2.5
//	整除	5 // 2	2
%	取余	5 % 2	1
**	幂运算	2 ** 3	8

2. 比较运算符

用于比较两个值，结果为布尔值（True或False）：

== 等于 5 == 5 → True

!= 不等于 5 != 3 → True

> 大于 5 > 3 → True

< 小于 5 < 3 → False

>= 大于等于 5 >= 5 → True

<= 小于等于 5 <= 3 → False

3. 逻辑运算符

用于组合多个条件：

`and` 与

两边都为True，结果才为True

True and True → True
True and False → False

`or` 或

只要一边为True，结果就为True

True or False → True
False or False → False

`not` 非

取反，True变False，False变True

not True → False
not False → True

表达式

表达式是由变量、常量和运算符组成的式子，计算后得到一个值。

# 算术表达式
result = 10 + 5 * 2      # 结果为 20（先乘后加）
result = (10 + 5) * 2    # 结果为 30（括号优先）

# 比较表达式
is_pass = score >= 60    # 结果为 True 或 False

# 逻辑表达式
is_good = score >= 80 and attendance >= 0.9
                

互动实验：变量与表达式计算器

输入变量值和表达式，实时计算结果：

a =

b =

c =

表达式计算结果：

3.5 算法三种基本结构

任何复杂的算法都可以由三种基本结构组合而成，这是结构化程序设计的核心思想。

1. 顺序结构

语句按照书写顺序依次执行，是最基本的结构。

步骤1：输入a的值

步骤2：输入b的值

步骤3：计算 sum = a + b

步骤4：输出sum

# 顺序结构示例：计算长方形面积
length = 5      # 长
width = 3       # 宽
area = length * width
print("长方形面积:", area)  # 输出：长方形面积: 15
                

2. 选择结构（分支结构）

根据条件判断，选择执行不同的语句块。

开始

条件判断：score >= 60？

True

输出"及格"

False

输出"不及格"

# 选择结构示例：判断成绩等级
score = 85

if score >= 90:
    print("优秀")
elif score >= 80:
    print("良好")      # 执行这一行
elif score >= 60:
    print("及格")
else:
    print("不及格")
                

3. 循环结构

重复执行某段代码，直到条件不满足为止。

初始化：i = 1

条件：i <= 5？

False（条件不满足）

结束循环

True（条件满足）

输出i的值

i = i + 1

回到条件判断，再次判断

# 循环结构示例：计算1到100的和
total = 0
for i in range(1, 101):    # i从1到100
    total = total + i       # 累加
print("1到100的和:", total)  # 输出：1到100的和: 5050

# while循环示例
i = 1
while i <= 5:
    print(i)    # 输出 1, 2, 3, 4, 5
    i = i + 1
                

互动实验：三种结构可视化

选择一种结构，输入参数，观察执行过程：

3.6 Python编程入门

为什么选择Python？

简单易学：语法接近自然语言，适合初学者
功能强大：拥有丰富的库，可用于数据分析、AI、Web开发等
社区活跃：全球最大的开发者社区之一
应用广泛：Google、YouTube、Instagram等都使用Python

Python基础语法

# 输入输出
print("Hello, World!")
name = input("请输入你的名字：")
print("你好，" + name + "！")

# 列表
fruits = ["苹果", "香蕉", "橙子"]
print(fruits[0])  # 输出：苹果

# 字典
student = {"name": "张三", "age": 16, "score": 85}
print(student["name"])  # 输出：张三
                

互动实验：Python在线运行

在下方输入Python代码，点击运行查看结果（支持基础语法）：

Python 3

3.7 经典算法解析

查找算法

在数据集合中找到目标元素

顺序查找 O(n) 二分查找 O(log n)

排序算法

将数据按特定顺序排列

冒泡排序 O(n²) 快速排序 O(n log n)

递归算法

函数调用自身的编程技巧

斐波那契阶乘计算

图算法

处理图结构数据的算法

最短路径最小生成树

冒泡排序原理

冒泡排序是一种简单的排序算法，重复地遍历要排序的列表，比较相邻的元素并交换顺序错误的元素。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 测试
numbers = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", numbers)
print("排序后:", bubble_sort(numbers))
                

互动实验：排序可视化

观察冒泡排序的过程，不同颜色表示不同状态：

未排序比较中已排序

前沿案例：算法在生活中的应用

导航算法

高德地图、百度地图使用Dijkstra算法或A*算法计算最短路径，结合实时交通数据，为你规划最优路线。

第三章 算法与程序实现