Python基础学习手册第15章:核心算法入门+案例实战讲解(下篇)

💡解题思路：

1. 初始条件：第 1 个数 a=1，第 2 个数 b=1
2. 递推公式：下一个数 = 前两个数的和
4. a , b = b ,  a+b (结合数学交换律看待这个赋值过程)
6. 循环计算，依次推出后续的数

a = 1b = 1# 输出前两个数print(a, b, end=" ")# 循环计算后面8个数，凑够10个for i in range(8):    # 递推：下一个数 = 前两个数的和    c = a + b    print(c, end=" ")    # 重新赋值，为下一次计算做准备    a, b = b, c  # 数学的交换律 

题目

求 n 的阶乘，n! = 1×2×3×…×n，比如 5! = 5×4×3×2×1 = 120。

💡解题思路：

1. 递归公式：n! = n × (n-1)! （大问题拆分成小问题）
2. 递归出口：当 n=1 时，1! = 1（最小问题有明确答案）
4. 🖥️代码
   # 定义函数def f(n):    # 递归出口：n=1时，阶乘是1    if n == 1:        return 1    # 递归调用：n! = n * (n-1)!    return n * f(n-1)# 调用函数，求5的阶乘print(f"5的阶乘是：{f(5)}")

题目

在一个班级的成绩列表里，查找有没有考 100 分的同学，如果有，输出他的位置；如果没有，输出 “没有满分同学”。

💡解题思路：

1. 从列表的第一个元素开始，
2. 一个个和 100 对比
3. 找到返回索引，找完所有元素没找到
4. 就返回提示
6. 🖥️代码

# 成绩列表s= [85, 92, 100, 78, 96, 100, 88]# 目标分数n = 100# 标记是否找到m = False# 线性搜索for x,y in enumerate(s):    if y == n:        print(f"找到满分同学，位置是第{x}个")        m = True# 没找到的情况if not m:    print("没有满分同学")

题目

在一个从小到大排好序的成绩列表里，快速查找有没有 88 分的同学

💡解题思路：

1. 二分查找也叫折半查找，每次取列表中间的数和目标对比：

   • 中间数 = 目标，直接找到
   • 中间数 > 目标，目标在左边，只找左半部分
   • 中间数 < 目标，目标在右边，只找右半部分每次排除一半的数据
   • 效率高于线性搜索
2. ⚠️注意点： 二分查找的前提：数据必须是有序的
4. 🖥️代码

# 排好序的成绩列表s = [60, 72, 78, 85, 88, 92, 96, 100]# 目标分数n = 88# 左右范围left = 0right = len(s) - 1m = False# 二分查找while left <= right:    # 确定中间位置    mid = (left + right) // 2    mid_s = s[mid]    # 找到目标    if mid_s == n:        print(f"找到88分，位置是第{mid}个")        m = True        break    # 中间数大于目标，找左边    elif mid_s> n:        right = mid - 1    # 中间数小于目标，找右边    else:        left = mid + 1# 没找到的情况if not m:    print("没有找到88分的同学")

⚠️ 新手指南（90% 的新手都踩过的坑）

1. 枚举算法
   枚举的范围要精准，范围太大会导致程序运行很慢，范围太小会漏掉正确答案
2. 模拟算法
   一定要 100% 贴合题目规则，漏掉任何一个条件都容易导致结果错误
3. 贪心算法
   不是所有问题都能用贪心，必须确认 “局部最优能得到全局最优”，否则会出错
4. 递推算法
   初始条件一定要找对，否则后续所有结果都会错
5. 递归算法
   必须写明确的递归出口，否则会无限循环，触发栈溢出报错
6. 二分查找
   必须用在有序数据上，无序数据不能用，否则会找不到正确结果