浅谈穷举法

浅谈穷举法

引用

CSDN

1.

https://blog.csdn.net/wxdzuishaui/article/details/142407537

穷举法是一种通过逐一列举所有可能情况来寻找解决方案的方法。虽然看似简单粗暴，但其适用范围广泛，能够解决许多实际问题。本文将详细介绍穷举法的概念、结构、应用条件以及具体求解过程，并通过多个实例帮助读者深入理解这一算法思想。

穷举法

穷举法是一种通过逐一列举所有可能情况来寻找解决方案的方法。就像找到一把钥匙打开一把锁，我们会尝试每一把钥匙直到找到正确的那一把。比如，如果你忘记了自己的密码，可以尝试每一种可能的组合直到找到正确的密码为止。

穷举法的结构

count = 0;  //所求解的个数
// i, j, k 分别为解空间
for( i = <解空间下限> ; i = <解空间上限> ; i++)
{
  for( j = <解空间下限> ; j = <解空间上限> ; j++)
  {
    for( k = <解空间下限> ; k = <解空间上限> ; k++)
    {
        if(<约束条件>)
        {
          printf(<满足条件的解>);
          count++;
        }
    }
  }
}  

穷举法的应用条件

解空间相对较小

也就是说答案的空间是已知的，在某个区间，或者某个集合内

1. 解决九宫格数独谜题：在一个九宫格数独谜题中，每个格子需要填入1到9的数字，且每行、每列、每个九宫格内的数字不能重复。可以通过逐一尝试每个格子的数字组合来找到唯一解。

2. 寻找一个四位数的密码：假设密码为四位数字，且每位数字在0到9之间，可以通过穷举法逐一尝试所有可能的数字组合来找到正确的密码。

可以通过有限次尝试找到答案

1. 猜数字游戏：在一个猜数字游戏中，玩家需要猜一个数字，范围在1到100之间。通过有限次尝试不同的数字，玩家可以找到正确的答案。

2. 解开一个简单的拼图：在一个简单的拼图游戏中，玩家需要将零散的拼图块组合成完整的图案。通过有限次尝试不同的组合方式，玩家可以完成拼图。

穷举法的具体求解过程

确定需要哪些变量

首先分析题目，明确我们需要的变量是什么，还要分析出变量的数据类型

确定每个变量的取值范围

变量的取值范围也就是其对应的解空间，不同的变量有着不同的解空间，需要我们加以分析

确定限制条件

1. 分析需要几层循环（一般是求解几个变量就用几层循环嵌套）

2. 在最内层当中增加限制条件（if判断语句等等）

穷举法虽然看似很笨拙，但由于其简单的原因，很多的问题都可以通过暴力的穷举法来解决（不考虑时间因素其他）

例如素数问题，约瑟夫环问题（今年春晚刘谦的魔术就是这个原理类似，我做过一个c语言的复刻，视频在b站，各位有兴趣的话可以了解了解）