【数据结构与算法之穷举法】穷举法的基本思想-蒲公英云

【数据结构与算法之穷举法】穷举法的基本思想

清疚 2024-03-25 16:39 162阅读 0赞

【数据结构与算法之穷举法】穷举法的基本思想

文章目录

- - 【数据结构与算法之穷举法】穷举法的基本思想

穷举法，是使用最广泛、设计最简单、同时最耗时的算法，也称为暴力法、蛮力法。

【穷举法基本思想】在问题的解空间中穷举每一种可能的解，并对每一种可能的解进行判断，从中找出答案。

【使用穷举法的注意事项】

划定的解空间必须覆盖问题的全部解，否则这个解空间是不完备的；
解空间集合一定是离散集合。或者说集合中的元素数量必须是有限的、可列的

只要划定了正确的解空间，就可以按照一定的步骤搜索这个解空间，并将解空间中的可能解穷举出来。

举个栗子：题目两数之和

题目描述：给定一个整数数组array 和一个目标值target，请在该数组中找出和为目标值target 的两个整数，并输出它们在数组array 中的下标。

在数组中找，一个元素不能重复使用，当然也可能无解

示例

array = {1,3,5,7,9,2,4,6,8,0}，target = 15

结果array[3] + array[8] = 15 ; array[4] + array[7] = 15。

假设需要寻找的数组元素下标为index_1 和index_2，数组长度为length，则index_1 和 index_2 的取值范围分别是 0 ≤ index_1 ≤ length -1 ，0 ≤ index_2 ≤ length -1，同时index_1 ≠ index_2

所以本题的解空间为：{index_1, index_2 | index_1 ∈ [0, length - 1], index_2 ∈ [0, length - 1] , index_1 ≠ index_2}

Java实现代码：

/**
 * @Projectname: JavaData_StructureAndAlgorithm
 * @Classname: SumOfTwoNumbers
 * @Author: Ding Jiaxiong
 * @Data:2023/3/14 14:48
 */
public class SumOfTwoNumbers {
    public static void outupIndexOfArray(int[] array, int target) {
        boolean haveSolution = false;
        for (int index_1 = 0; index_1 < array.length; index_1++) {
            for (int index_2 = 0; index_2 < array.length; index_2++) {
                if (index_1 != index_2 && (array[index_1] + array[index_2] == target)) {
                    // 找到一个解，输出
                    System.out.println("array[" + index_1 + "] + " + "array[" + index_2 + "] = " + target);
                    haveSolution = true;
                }
            }
        }
        if (!haveSolution) {
            System.out.println("无解");
        }
    }
    public static void main(String[] args) {
        int[] array = {
    1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
        int target = 15;
        outupIndexOfArray(array, target);
    }
}

运行结果

在这里插入图片描述

其实可以发现，好像第1个结果和第4个结果是相同的，第2个和第3个结果也是相同，这很容易想明白，因为我们的解空间中包含了重复的解。

在这里插入图片描述

在代码实现上，我们只要将内层循环变量index_2 的起始值从原来的0 改为index_1 + 1，就可以将解空间的大小缩小为原来的一半了，同时也不用再判断index_1 是否等于index_2。

改进实现：

/**
 * @Projectname: JavaData_StructureAndAlgorithm
 * @Classname: SumOfTwoNumbers
 * @Author: Ding Jiaxiong
 * @Data:2023/3/14 14:48
 */
public class SumOfTwoNumbers {
    public static void outupIndexOfArray(int[] array, int target) {
        boolean haveSolution = false;
        for (int index_1 = 0; index_1 < array.length; index_1++) {
            for (int index_2 = index_1 + 1; index_2 < array.length; index_2++) {
                if (index_1 != index_2 && (array[index_1] + array[index_2] == target)) {
                    // 找到一个解，输出
                    System.out.println("array[" + index_1 + "] + " + "array[" + index_2 + "] = " + target);
                    haveSolution = true;
                }
            }
        }
        if (!haveSolution) {
            System.out.println("无解");
        }
    }
    public static void main(String[] args) {
        int[] array = {
    1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
        int target = 15;
        outupIndexOfArray(array, target);
    }
}