C++基本算法思想之穷举法

C++基本算法思想之穷举法攻略

穷举法概述

穷举法是一种基本的算法思想，也称为暴力搜索或枚举搜索，是一种对所有可能性进行逐一验证的算法。它通过枚举问题所有可能的解，来寻找问题的最优解。

穷举法的具体步骤

穷举法的具体步骤可以分为三部分：

1. 确定问题的解空间

问题的解空间是指问题的所有可能解构成的集合。在使用穷举法解决问题时，需要确定问题的解空间，以便于后续的操作。

例如，如果要通过穷举法求解一个数组中两个数之和等于目标值的问题，那么问题的解空间就是所有可能的两个数的组合。

2. 逐一枚举解空间中的所有解

在确定问题的解空间之后，需要逐一枚举解空间中的所有解，并验证其是否符合问题的要求。如果符合要求，则认为找到了一个解，否则继续枚举下一个解。

例如，如果要通过穷举法求解一个数组中两个数之和等于目标值的问题，那么就需要逐一枚举数组中所有可能的两个数的组合，并计算它们的和是否等于目标值，直到找到符合要求的解为止。

3. 判断所得解是否是最优解

在所有解枚举完之后，需要判断得到的解是否是最优解。如果是最优解，则返回该解，否则返回无解。

穷举法的应用举例

例 1：求1~100的所有偶数

在这个例子中，问题的解空间为 1~100 的所有整数，我们需要逐一枚举这个解空间，并判断每一个数是否为偶数。

#include <iostream>

int main()
{
    for(int i = 1; i <= 100; i++)
    {
        if(i % 2 == 0)
        {
            std::cout << i << std::endl;
        }
    }
    return 0;
}

输出结果为 2、4、6、……、98、100。

例 2：在一个数组中查找两个数之和等于目标值的数对

在这个例子中，问题的解空间为数组中所有可能的两个数的组合，我们需要逐一枚举这个解空间，并判断每一个数对的和是否等于目标值。

#include <iostream>
#include <vector>

std::vector<std::pair<int, int>> findPairs(std::vector<int>& nums, int target)
{
    std::vector<std::pair<int, int>> result;
    int n = nums.size();
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                result.push_back(std::make_pair(nums[i], nums[j]));
            }
        }
    }
    return result;
}

int main()
{
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<std::pair<int, int>> result = findPairs(nums, target);
    for(auto& p : result)
    {
        std::cout << p.first << " + " << p.second << " = " << target << std::endl;
    }
    return 0;
}

输出结果为 2 + 7 = 9。

结语

穷举法虽然比较简单，但它在解决某些问题时却是非常有效和实用的。在实际应用中，需要根据具体的问题特点选择合适的算法，以提高效率和准确性。