《算法设计与分析基础》练习题1.1及答案

解析部分并非为官方答案，如有错误，请在评论区指出，谢谢！

1.1.1

算法（Algorithm）一词源自阿尔·花剌子模名字的拉丁化形式。

– Algorithm（算法）来自他的名字：

al-Khwārizmī → 拉丁化 Algoritmi → 演变成 Algorithm

​- Algebra（代数）来自他的代表作 《代数学》

书名：Kitāb al-Jabr wa-l-Muqābala

其中 al-jabr → 演变成 Algebra

 – 算法 = 他的人名

– 代数 = 他的书名

1.1.2

纯算法本身在美国不能直接获专利；但算法+具体技术应用（解决技术问题、带来技术改进），可以申请并获得专利。结合“促进有用技术”的立法目的，算法不应被完全禁止专利，但必须严格限定在“技术应用”场景。

1.1.3

a

算法名称：DriveFromSchoolToHome
输入：
起点 = 学校正门停车场出口
终点 = 小区北门入口
车辆 = 正常可行驶机动车
输出：
车辆安全到达小区北门门禁处，行程结束

BEGIN
// 步骤1
从学校正门停车场出口缓慢驶出
沿出口专用车道直行 5 米
到达校门口非机动车道边缘
执行：停车观察左右来车

// 步骤2
IF 左右来车安全 = TRUE THEN
开启右转向灯
平稳驶入右侧机动车道
沿当前车道直行 100 米
到达第一个十字路口停止线前
END IF

// 步骤3
在停止线前停车等待
观察直行方向交通信号灯
WHILE 信号灯 ≠ 绿灯 DO
继续等待
END WHILE
保持直行通过十字路口
沿主路继续直行 300 米

// 步骤4
观察右侧道路指示牌
提前 50 米驶入右转专用车道
减速至 30km/h 以下

// 步骤5
观察右转信号灯/让行标志
IF 右转条件安全 = TRUE THEN
执行右转操作
进入次干道
沿当前车道直行 200 米
END IF

// 步骤6
到达小区北门前方 50 米处
开启右转向灯
减速至 20km/h
平稳驶入小区入口辅道

// 步骤7
沿辅道直行 10 米
到达小区北门门禁处
停车
输出：本次驾驶行程完成

END

b

算法名称：TomatoEgg
输入：
eggs = 3 // 鸡蛋数量
tomatoes = 2 // 番茄数量
salt = 4.0g // 总盐量
sugar = 0.5g // 提鲜糖
oil = 15mL // 食用油
scallion = 少许 // 葱花（可选）
输出：
一盘可食用的番茄炒蛋

BEGIN
// 预处理鸡蛋
bowl = empty
将 eggs 全部打入 bowl
salt1 = 2.0g
将 salt1 加入 bowl
用筷子 匀速同向搅拌 60秒
egg_liquid = 搅拌结果

// 预处理番茄
清洗 tomatoes
去蒂
每个番茄切为 6 等块
tomato_pieces = 所有番茄块

// 炒蛋
平底锅开火 中火
倒入 oil
等待 30秒 至油微热
倒入 egg_liquid
当底部凝固时：
从边缘向中心轻推蛋液
当蛋液凝固度 ≥ 80%：
划散成小块
盛出 → egg_cooked

// 炒番茄
锅中倒入 tomato_pieces
中火翻炒 1~2分钟 至出汁变软
salt2 = 2.0g
将 salt2、sugar 加入
翻炒均匀

// 混合出锅
将 egg_cooked 倒回锅中
混合翻炒 10秒
关火
撒 scallion（可选）

RETURN 番茄炒蛋
END

1.1.4

算法步骤

伪代码如下：

function floorSqrt(n):
if n < 0:
return "Error: n must be a positive integer"
l = 1
r = n
res = 0
while l <= r:
m = (l + r) // 2 # 整数除法
m_squared = m * m
if m_squared == n:
return m
elif m_squared < n:
res = m
l = m + 1
else:
r = m – 1
return res

1.1.5

算法设计（双指针法）

利用两个列表已排序的特性，使用双指针法高效求解：

最大比较次数分析

在最坏情况下，两个指针需要遍历完整个列表，直到其中一个指针到达末尾。

• 指针 i 最多移动 m 次。
• 指针 j 最多移动 n 次。
• 每次移动都对应一次比较操作。

因此，该算法的最大比较次数为：m+n−1​（当其中一个列表遍历到最后一个元素时，另一个列表恰好也遍历到最后一个元素，此时总次数为 m + n – 1）。

1.1.6

a.

gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,1513)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,5)=gcd(5,4)=gcd(4,1)=gcd(1,0)=1，共10步；

b.

由连续整数检测算法来解决gcd(31415,14142)需要14142步，则速度倍数为1414.2倍，约为1414倍；

1.1.7

要证明等式 gcd⁡(m,n)=gcd⁡(n,m mod n)对每一对正整数 (m,n)都成立，我们可以通过公约数的传递性和带余除法来分析：

步骤1：带余除法表示

对正整数 m和 n，根据带余除法，存在唯一的整数 q（商）和 r（余数），使得：

m=qn+r且0≤r<n

其中， r=m mod n（即 m除以 n的余数）。

步骤2：分析 gcd⁡(m,n)与 gcd⁡(n,r)的公约数关系

设 d=gcd⁡(m,n)，则 d同时整除 m 和 n ，即：

d∣m且d∣n

由于 r=m−qn（由 m=qn+r 变形），根据整除的线性性质（若 d∣a且 d∣b ，则 d∣(a−qb) ），可得：

d∣(m−qn)  ⟹  d∣r

因此， d同时整除 n 和 r，即 d 是 n和 r的公约数。根据最大公约数的定义， d≤gcd⁡(n,r)（因为 gcd⁡(n,r)是 n 和 r 的最大公约数）。

步骤3：反向分析 gcd⁡(n,r) 与 gcd⁡(m,n) 的公约数关系

设 d′=gcd⁡(n,r)，则 d′同时整除 n和 r，即：

d′∣n且d′∣r

由于 m=qn+r（带余除法的原式），根据整除的线性性质（若 d′∣a且 d′∣b，则 d′∣(qa+b) ），可得：

d′∣(qn+r)  ⟹  d′∣m

因此， d′ 同时整除 m 和 n ，即 d′ 是 m 和 n 的公约数。根据最大公约数的定义， d′≤gcd⁡(m,n)（因为 gcd⁡(m,n) 是 m 和 n 的最大公约数）。

步骤4：结合双向不等式，证明等式成立

由步骤2得 gcd⁡(m,n)≤gcd⁡(n,r) ，由步骤3得 gcd⁡(n,r)≤gcd⁡(m,n) 。根据不等式的传递性，两者必须相等：

gcd⁡(m,n)=gcd⁡(n,r)

而 r=m mod n，因此：

gcd⁡(m,n)=gcd⁡(n,m mod n)

特殊情况说明

当 n=0 时， m mod n 无定义（除数不能为0），但题目限定 m,n为正整数，因此 n≥1 ，无需考虑 n=0的情况。

综上，对任意正整数 (m,n) ，等式 gcd⁡(m,n)=gcd⁡(n,m mod n) 恒成立。

1.1.8

欧几里得算法会交换两数，使较大的数成为被除数。在处理过程中，这种情况最多发生一次。

1.1.9

a.

当 m 是 n 的倍数时，即 m=k×n（其中 k 为正整数），欧几里得算法只需一次除法即可得到最大公约数 n 。例如， m=10 ， n=5，则 10÷5=2余 0 ，只需一次除法。

因此，对于所有 m≥1， n≤10的输入，欧几里得算法最少要做 1次 除法。

b.

最多除法次数的情况通常发生在 m 和 n 是连续的斐波那契数时。斐波那契数列的相邻两项在使用欧几里得算法时会产生最多的除法步骤。

由于 n≤10，我们考虑不超过10的斐波那契数：1, 2, 3, 5, 8。

gcd(8,5)=gcd(5,3)=gcd(3,2)=gcd(2,1)=gcd(1,0)=1

gcd(5,3)=gcd(3,2)=gcd(2,1)=gcd(1,0)=1

gcd(3,2)=gcd(2,1)=gcd(1,0)=1

gcd(2,1)=gcd(1,0)=1

所以最多的除法步骤为4步。

1.1.10

a.减法版欧几里得算法伪代码

function gcd_subtraction(a, b):
// 输入: 两个正整数 a, b
// 输出: gcd(a, b)
while a ≠ b:
if a > b:
a = a – b
else:
b = b – a
return a

b.

在欧几里得游戏中，设 a>b ， gcd⁡(a,b)=d ，则 k=a/d 。

• 若 k为奇数，先手有必胜策略。
• 若 k为偶数，后手有必胜策略。
  因此，应根据 k的奇偶性决定行动顺序：
• k 为奇数时，选择先手。
• k 为偶数时，选择后手。

1.1.11

a. 扩展欧几里得算法（Python 实现）

算法核心原理

扩展欧几里得算法在普通欧几里得算法（辗转相除）的基础上，反向推导每一步的线性组合系数。设 a=b⋅q+r（0≤r<b），若已求得 bx′+ry′=gcd(b,r)，则代入 r=a−b⋅q 可得：bx′+(a−bq)y′=ay′+b(x′−qy′)=gcd(a,b)即系数递推关系：x=y′, y=x′−q⋅y′。

代码实现

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""
扩展欧几里得算法递归实现
:param a: 正整数
:param b: 正整数
:return: (gcd, x, y)，满足 a*x + b*y = gcd
"""
if b == 0:
# 基线条件：a*1 + 0*0 = a
return a, 1, 0
# 递归求解 b 和 a%b 的组合
gcd, x_prev, y_prev = extended_gcd(b, a % b)
# 系数递推
x = y_prev
y = x_prev – (a // b) * y_prev
return gcd, x, y

# 测试示例
if __name__ == "__main__":
m, n = 30, 18
d, x, y = extended_gcd(m, n)
print(f"gcd({m}, {n}) = {d}")
print(f"满足 {m}*x + {n}*y = {d} 的解：x={x}, y={y}")
# 验证：30*(-1) + 18*2 = -30 + 36 = 6 = gcd(30,18)

b. 丢番图方程 ax+by=c 求解（Python 实现）

解的存在性判定

丢番图方程 ax+by=c 有解的充要条件是：gcd(a,b)∣c（即 c 能被 a 和 b 的最大公约数整除）。

通解公式

若 (x0​,y0​) 是方程的一组特解，则方程的通解为：

其中 k 为任意整数。

代码实现（含解的判定、特解求解、通解生成）

def solve_diophantine(a: int, b: int, c: int) -> tuple[bool, tuple[int, int] | None, tuple[int, int] | None]:
"""
求解丢番图方程 ax + by = c
:param a: 系数
:param b: 系数
:param c: 常数项
:return: (是否有解, 特解(x0,y0), 通解参数(step_x, step_y))
通解：x = x0 + k*step_x，y = y0 – k*step_y（k为任意整数）
"""
# 步骤1：调用扩展欧几里得算法求gcd和基础解
gcd, x_gcd, y_gcd = extended_gcd(abs(a), abs(b))

# 步骤2：判定解的存在性
if c % gcd != 0:
return False, None, None

# 步骤3：求解特解（缩放基础解）
k = c // gcd # 缩放因子
x0 = x_gcd * k * (1 if a > 0 else -1)
y0 = y_gcd * k * (1 if b > 0 else -1)

# 步骤4：计算通解的步长
step_x = b // gcd
step_y = a // gcd

return True, (x0, y0), (step_x, step_y)

# 测试示例
if __name__ == "__main__":
# 示例1：有解情况 6x + 4y = 2
a1, b1, c1 = 6, 4, 2
has_sol1, sol1, step1 = solve_diophantine(a1, b1, c1)
if has_sol1:
x0, y0 = sol1
sx, sy = step1
print(f"方程 {a1}x + {b1}y = {c1} 有解")
print(f"特解：x0={x0}, y0={y0}")
print(f"通解：x = {x0} + k*{sx}, y = {y0} – k*{sy} (k为任意整数)")

print("-" * 30)

# 示例2：无解情况 6x + 4y = 1
a2, b2, c2 = 6, 4, 1
has_sol2, sol2, step2 = solve_diophantine(a2, b2, c2)
if not has_sol2:
print(f"方程 {a2}x + {b2}y = {c2} 无解（因gcd(6,4)=2不整除1）")

1.1.12

问题分析 💡

结论 ✅

• 最终打开的门：所有编号为完全平方数的门，即 12,22,32,…，且不大于 n。
• 最终关闭的门：所有编号不是完全平方数的门。
• 打开的门的数量：等于不大于 n 的完全平方数的个数，即 ⌊n​⌋。

例如，当 n=10 时，打开的门是编号为 1, 4, 9 的门，共 ⌊10​⌋=3 扇。

代码实现

def simulate_door_process(n):
"""
模拟n扇门的开关过程，输出每一步操作和最终状态

参数:
n: 门的总数（正整数）
"""
# 1. 初始化门的状态：False表示关闭，True表示打开，初始全关闭
doors = [False] * (n + 1) # 索引0不用，1~n对应第1~n扇门

# 2. 模拟每一轮操作（第k轮切换k的倍数号门）
print(f"开始模拟 {n} 扇门的开关过程：\\n")
for k in range(1, n + 1):
print(f"第 {k} 轮操作：切换 {k} 的倍数号门（{k}, {2*k}, …）")
# 切换k的倍数号门的状态（从k开始，步长k）
for door_num in range(k, n + 1, k):
doors[door_num] = not doors[door_num] # 状态翻转

# 3. 统计最终结果
open_doors = [i for i in range(1, n + 1) if doors[i]] # 最终打开的门编号
open_count = len(open_doors)

# 4. 输出最终状态
print("\\n" + "-" * 50)
print(f"最终状态：")
print(f"打开的门编号：{open_doors}")
print(f"打开的门数量：{open_count}（等于 floor(sqrt({n})) = {int(n**0.5)}）")
print(f"关闭的门数量：{n – open_count}")

# 示例：模拟10扇门的过程（可修改n为任意正整数，比如20、100）
if __name__ == "__main__":
n = 10 # 可自定义门的总数
simulate_door_process(n)