当前位置：首页 > article >正文

五大基础算法——枚举算法

article 2025/3/18 3:44:51

枚举算法 是一种通过遍历所有可能的解来寻找问题答案的算法思想。它通常用于解决那些解空间有限且可以直接列举所有可能情况的问题。以下是枚举算法的核心概念、适用场景、实现方法及经典例题：

一、核心概念

解空间
- 所有可能的解的集合。
遍历
- 通过循环或递归逐一检查解空间中的每一个解。
剪枝
- 在遍历过程中，通过某些条件提前排除不可能的解，减少计算量。

二、适用场景

解空间有限
- 问题的解空间较小，可以直接枚举。
问题规模较小
- 问题规模不大，枚举的计算量在可接受范围内。
需要精确解
- 枚举可以找到问题的精确解，而不是近似解。

三、实现步骤

确定解空间
- 明确问题的解空间范围。
设计遍历方法
- 使用循环或递归遍历解空间。
检查解的有效性
- 对每一个解，检查是否满足问题的条件。
剪枝优化
- 在遍历过程中，通过条件提前排除不可能的解。

四、经典例题与代码

1. 百钱买百鸡问题

问题描述：用100元买100只鸡，公鸡5元一只，母鸡3元一只，小鸡1元三只，问有多少种买法。

def buyChickens():
    solutions = []
    for x in range(0, 21):  # 公鸡最多买20只
        for y in range(0, 34):  # 母鸡最多买33只
            z = 100 - x - y  # 小鸡的数量
            if 5 * x + 3 * y + z / 3 == 100:
                solutions.append((x, y, z))
    return solutions

# 示例
print(buyChickens())  # 输出所有可能的买法

2. 全排列问题

问题描述：给定一个数组，输出其所有可能的排列。

def permute(nums):
    result = []
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack(0)
    return result

# 示例
nums = [1, 2, 3]
print(permute(nums))  # 输出所有排列

3. 子集生成问题

问题描述：给定一个数组，输出其所有可能的子集。

def subsets(nums):
    result = []
    def backtrack(index, path):
        result.append(path)
        for i in range(index, len(nums)):
            backtrack(i + 1, path + [nums[i]])
    backtrack(0, [])
    return result

# 示例
nums = [1, 2, 3]
print(subsets(nums))  # 输出所有子集

4. 素数判断

问题描述：判断一个数是否为素数。

def isPrime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# 示例
print(isPrime(29))  # 输出 True