一、经典算法题

1、使用 Python 生成斐波那契数列的简单方法

（1）循环实现（推荐）

def fibonacci(n):
    fib = []       # 存储数列的列表
    a, b = 0, 1    # 初始化前两个数
    for _ in range(n):
        fib.append(a)
        a, b = b, a + b  # 更新 a 和 b 的值
    return fib

# 示例用法
n = int(input("请输入要生成的项数: "))
print(f"前{n}项斐波那契数列:", fibonacci(n))

代码解释：

• a 和 b 初始化为斐波那契数列的前两个数 0 和 1
• 循环 n 次，每次将当前数 a 添加到列表
• 更新 a 和 b：新 a 变为原来的 b，新 b 变为两者之和
• 最终返回包含前 n 项的列表

 

（2）递归实现（仅教学用途，效率低）

def fib_recursive(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        fib = fib_recursive(n-1)
        fib.append(fib[-1] + fib[-2])
        return fib

示例输出（输入 10）：

前10项斐波那契数列: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

关键点说明：

• 推荐循环方法：时间复杂度 O(n)，效率高

• 递归方法缺点：时间复杂度 O(2ⁿ)，重复计算多，实际开发中不建议使用

• 起始定义：通常认为 F(0)=0，F(1)=1，如需不同起始值可调整初始 a 和 b

尝试修改初始值 a, b = 1, 1 可以生成以 [1, 1, 2, 3...] 开头的数列。

 

2、 质数判断：通过遍历2到√n的范围判断是否有因子

（1）基础循环判断（推荐）

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:  # 2是唯一偶质数
        return True
    if n % 2 == 0:  # 排除其他偶数
        return False
    
    sqrt_n = math.isqrt(n)  # 计算 √n 的整数部分（Python 3.8+）
    for i in range(3, sqrt_n + 1, 2):  # 只检查奇数因子
        if n % i == 0:
            return False
    return True

# 示例用法
num = int(input("请输入要判断的数字: "))
print(f"{num} 是质数吗？", is_prime(num))

代码解释：

1. 特殊值处理：

• n <= 1：直接返回 False
• n == 2：唯一偶质数，直接返回 True
• n 是偶数：除 2 外都不是质数，直接返回 False

1. 核心逻辑：

• 计算 √n 的整数部分（使用 math.isqrt 更高效，Python 3.8+ 支持）
• 只遍历 3 到 √n 的奇数（步长为 2），减少循环次数
• 发现能整除的因子立即返回 False

1. 时间复杂度：O(√n)，效率远高于遍历到 n-1

 

（2）简写版（牺牲部分可读性）

import math

def is_prime_short(n):
    return n > 1 and all(n % i != 0 for i in range(2, math.isqrt(n)+1))

示例输出：

print(is_prime(7))   # 输出 True（7是质数）
print(is_prime(9))   # 输出 False（9 = 3×3）
print(is_prime(1))   # 输出 False
print(is_prime(2))   # 输出 True

关键优化点：

1. 范围缩小到 √n：如果 n 有大于 √n 的因子，必然对应一个小于 √n 的因子

2. 排除偶数：除 2 外，所有偶数都不是质数，直接跳过检查

3. 步长优化：检查奇数时跳过偶数因子（步长设为 2）

如果需要兼容旧版 Python（无 math.isqrt），可替换为：

sqrt_n = int(n ** 0.5)  # 用平方根取整代替

 

3、 百钱买百鸡

百钱买百鸡问题是中国古代经典的数学问题，描述如下：
用 100文钱 买 100只鸡，其中：

• 公鸡 5文/只

• 母鸡 3文/只

• 小鸡 1文/3只

问共有多少种购买组合？

解法分析

1. 数学方程
   设公鸡、母鸡、小鸡的数量分别为 xx, yy, zz，则满足：

   {x+y+z=100（总数100只）5x+3y+z3=100（总花费100文）{x+y+z=100（总数100只）5x+3y+3z​=100（总花费100文）​

   整理得：

   7x+4y=1007x+4y=100

   z=100−x−yz=100−x−y，且 zz 必须是 3的倍数（因为小鸡按3只购买）。

2. 遍历优化

   • 公鸡最多买 ⌊100/5⌋=20⌊100/5⌋=20 只，但根据方程 7x≤1007x≤100，实际 x≤14x≤14。

   • 母鸡数量 y=100−7x4y=4100−7x​ 必须为 非负整数。

for x in range(0, 15):  # 公鸡范围：0 ≤ x ≤14
    y = (100 - 7 * x) / 4
    if y >= 0 and y == int(y):  # y为非负整数
        y = int(y)
        z = 100 - x - y
        if z >= 0 and z % 3 == 0:  # z是3的倍数且非负
            print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只")

运行结果

公鸡: 0只, 母鸡: 25只, 小鸡: 75只
公鸡: 4只, 母鸡: 18只, 小鸡: 78只
公鸡: 8只, 母鸡: 11只, 小鸡: 81只
公鸡: 12只, 母鸡: 4只, 小鸡: 84只

关键点说明

1. 数学推导：通过消元将问题简化为单变量方程，减少循环次数。

2. 约束条件：确保 yy 为整数，且 zz 是3的倍数。

3. 效率优化：从 O(n3)O(n3) 的三重循环优化为 O(n)O(n) 的单层循环。

 

二、排序与查找

1、冒泡排序

（1）基础冒泡排序

def bubble_sort_basic(nums):
    n = len(nums)
    for i in range(n-1):  # 需要 n-1 轮遍历
        for j in range(n-1-i):  # 每轮比较范围逐渐缩小
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]  # 交换相邻元素
    return nums

代码解释：

• 外层循环：控制排序轮数（共需 n-1 轮）

• 内层循环：每轮比较相邻元素，将较大值向右“冒泡”

• 交换逻辑：若左元素 > 右元素，则交换位置

 

（2）优化冒泡排序（可提前终止）

def bubble_sort_optimized(nums):
    n = len(nums)
    for i in range(n-1):
        swapped = False  # 标记本轮是否发生交换
        for j in range(n-1-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True
        if not swapped:  # 如果本轮无交换，说明已排序完成
            break
    return nums

优化点：

• 提前终止：如果某一轮未发生交换，说明数组已有序，直接结束排序

• 减少无效循环：对部分有序数据效率显著提高

 

（3）示例

arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
print("排序后（基础版）:", bubble_sort_basic(arr.copy()))
print("排序后（优化版）:", bubble_sort_optimized(arr.copy()))

输出结果：

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后（基础版）: [11, 12, 22, 25, 34, 64, 90]
排序后（优化版）: [11, 12, 22, 25, 34, 64, 90]

关键特性说明：

1. 时间复杂度：

   • 最好情况（已排序）：优化版 O(n)，基础版仍 O(n²)

   • 最坏/平均情况：O(n²)

2. 空间复杂度：O(1)（原地排序）

3. 稳定性：是稳定排序（相等元素不改变相对位置）

4. 适用场景：教学演示、小规模数据排序

 

(4)可视化理解（以 [5, 3, 8, 1] 为例）：

第1轮遍历：
5 vs 3 → 交换 → [3,5,8,1]
5 vs 8 → 不交换
8 vs 1 → 交换 → [3,5,1,8]（最大元素8归位）

第2轮遍历：
3 vs 5 → 不交换
5 vs 1 → 交换 → [3,1,5,8]（次大元素5归位）

第3轮遍历：
3 vs 1 → 交换 → [1,3,5,8]（排序完成）

 

2、二分查找

（1）迭代实现

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1  # 初始化查找范围
    
    while low <= high:  # 注意循环终止条件
        mid = low + (high - low) // 2  # 防止整数溢出（Python无需担心，但此写法更通用）
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] < target:
            low = mid + 1  # 目标在右半部分
        else:
            high = mid - 1  # 目标在左半部分
    return -1  # 未找到

代码解释：

1. 初始化指针：low 和 high 分别指向数组首尾

2. 循环条件：low <= high 确保搜索区间有效

3. 中间值计算：用 mid = low + (high - low) // 2 避免整数溢出风险

4. 比较与调整：

• 找到目标直接返回索引
• 中间值 < 目标 → 缩小到右半区间 (low = mid + 1)
• 中间值 > 目标 → 缩小到左半区间 (high = mid - 1)

 

（2）递归实现

 

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1  # 初始时设置 high
    
    if low > high:  # 基线条件：区间无效
        return -1
    
    mid = (low + high) // 2  # 中间索引
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)  # 递归右半
    else:
        return binary_search_recursive(arr, target, low, mid - 1)  # 递归左半

 

示例

sorted_arr = [1, 3, 4, 6, 7, 9]
print(binary_search_iterative(sorted_arr, 6))  # 输出 3（索引）
print(binary_search_iterative(sorted_arr, 5))  # 输出 -1（未找到）
print(binary_search_recursive(sorted_arr, 9))  # 输出 5

关键特性说明：

1. 时间复杂度：O(log n)，每次将搜索范围减半

2. 空间复杂度：

   • 迭代版本：O(1)（原地操作）

   • 递归版本：O(log n)（递归调用栈深度）

3. 前提条件：数组必须 有序（升序或降序需与代码逻辑匹配）

4. 重复元素：默认返回任意匹配项的索引，若需找最左/最右位置需修改逻辑

 

（3）常见变种需求

查找目标值的第一个出现位置

def find_first_occurrence(arr, target):
    low, high, result = 0, len(arr)-1, -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid    # 记录位置
            high = mid - 1  # 继续向左找更早的匹配
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

注意事项

1. 输入验证：实际使用时应先检查数组是否有序

2. 降序处理：若数组为降序排列，需反转比较逻辑（将 < 改为 >）

3. 元素不存在：返回 -1 是常见做法，也可根据需求返回 None 或抛出异常

 

三、递归与动态规划

1、猴子吃桃问题

问题描述

猴子每天吃掉剩余桃子的一半加一个，第 nn 天时只剩 1 个桃子。求最初有多少桃子？

（1）循环实现

def peach_iterative(days):
    if days < 1:
        return 0  # 无效天数处理
    peach = 1     # 第 days 天剩下的桃子数
    for _ in range(days - 1):
        peach = (peach + 1) * 2  # 逆向推导前一天的桃子数
    return peach

# 示例用法
n = int(input("请输入天数: "))
print(f"初始桃子数（循环法）: {peach_iterative(n)}")

代码解释：

1. 初始化：从第 nn 天剩下的 1 个桃子开始

2. 逆向循环：执行 n−1n−1 次循环，每次计算前一天的桃子数

3. 递推公式：前一天桃子数 = (当前桃子数 + 1) * 2

 

（2）递归实现

def peach_recursive(days):
    if days == 1:
        return 1  # 第 days 天剩下 1 个
    else:
        return (peach_recursive(days - 1) + 1) * 2

# 示例输出
print(f"初始桃子数（递归法）: {peach_recursive(n)}")

递归终止条件：

• 当 days == 1 时返回 1（最后一天只剩 1 个桃子）

• 其他情况递归计算前一天的桃子数

 

关键验证（以 n=5n=5 为例）

第5天：1 个（初始条件）
第4天：(1 + 1) * 2 = 4
第3天：(4 + 1) * 2 = 10
第2天：(10 + 1) * 2 = 22
第1天：(22 + 1) * 2 = 46 → 初始桃子数

注意事项

1. 递归深度限制：Python 默认递归深度约 1000 层，n>1000n>1000 时会报错，建议使用循环方法

2. 无效输入处理：添加对 days < 1 的判断，返回 0 或抛出异常

3. 时间复杂度：两种方法均为 O(n)O(n)

 

公式推导（数学解法）

直接通过等比数列求和公式得出通项公式：

初始桃子数=3×2n−1−2初始桃子数=3×2n−1−2

Python 实现：

def peach_formula(days):
    return 3 * (2 ** (days - 1)) - 2

 

2、杨辉三角

（1）基础嵌套循环（逐行生成）

def yanghui_triangle(n):
    triangle = []  # 存储结果的二维列表
    for i in range(n):  # 生成第 i 行
        row = [1] * (i + 1)  # 初始化当前行（全为1）
        if i >= 2:  # 从第三行开始计算中间值
            for j in range(1, i):
                # 杨辉三角公式：当前值 = 上一行左值 + 上一行右值
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)  # 将当前行添加到结果
    return triangle

# 示例用法
n = int(input("请输入杨辉三角的行数: "))
result = yanghui_triangle(n)
for row in result:
    print(row)

代码解释：

1. 初始化行：每行初始化为 [1] * (i + 1)，首尾自然为 1

2. 中间值计算：仅当 i >= 2 时，从第 3 行开始计算中间项

3. 递推公式：row[j] = 上一行[j-1] + 上一行[j]

 

（2）优化对称性（减少一半计算）

def yanghui_optimized(n):
    triangle = []
    for i in range(n):
        row = [1] * (i + 1)
        mid = (i + 1) // 2  # 中点位置
        for j in range(1, mid + 1):
            val = triangle[i-1][j-1] + triangle[i-1][j]
            row[j] = val
            row[i - j] = val  # 利用对称性赋值
        triangle.append(row)
    return triangle

优化点：

• 对称性利用：只需计算前一半，后一半镜像复制，减少循环次数

• 时间复杂度：从 O(n²) 优化到 O(n²/2)

 

示例输出（输入 5）：

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]

关键特性说明：

1. 数学原理：每个数等于其左上方和右上方的数之和

2. 时间复杂度：O(n²)，空间复杂度 O(n²)

3. 应用场景：组合数学、二项式系数计算、教学演示

 

（3）可视化改进（对齐打印）

def print_triangle(triangle):
    max_width = len(' '.join(map(str, triangle[-1])))  # 最后一行宽度
    for row in triangle:
        line = ' '.join(map(str, row))
        print(line.center(max_width))

# 调用示例
print_triangle(yanghui_triangle(5))

输出效果：

       1       
      1 1      
     1 2 1     
    1 3 3 1    
   1 4 6 4 1   

 

（4）扩展应用

直接获取第 n 行第 k 列的值（组合数 C(n, k)）：

def combination(n, k):
    if k < 0 or k > n:
        return 0
    res = 1
    for i in range(1, k+1):
        res = res * (n - i + 1) // i
    return res