初探算法的魅力——【暴力枚举】

点击下面查看作者专栏🔥🔥C语言专栏🔥🔥🌊🌊编程百度🌊🌊🌠🌠如何获取自己的代码仓库🌠🌠

🌐索引与导读

• 暴力枚举（BF）的概念
• 暴力枚举的算法步骤
• 例题讲解
  • 经典案例讲解一：百鸡问题
    • 题目解析
    • 思路方案
  • 经典案例讲解二：盛最多水的容器
    • 暴力枚举算法
    • 最优解
  • 经典案例讲解三：两数之和
  • 经典案例讲解四：2025
    • 💻 代码实现
• 希望读者多多三连
• 给小编一些动力
• 蟹蟹啦！

暴力枚举（BF）的概念

暴力枚举也称为穷举法，是计算机算法中最基础、最直观，但也是最费劲的一种解题思路

像我们平时没有最优解的算法题，往往都可以通过暴力枚举去算出最终结果

• 核心思想
  不靠巧妙的技巧，而是利用计算机强大的计算能力，把所有可能的情况列举出来，一个一个去验证，直到找到正确答案

暴力枚举的算法步骤

• 列举 ：确定解空间的范围，列出所有可能的解候选者
• 检验 ：对每一个候选者进行判断，看它是否满足题目条件

例题讲解

下面我们通过几道算法题来感受暴力拆解的快感💪💪 💥 💥

经典案例讲解一：百鸡问题

Lucy的空间骇客裂缝：洛谷百鸡问题

题目解析

我们要解决的核心问题是找到三个未知数（公鸡数量、母鸡数量、小鸡数量）

• 假设：
  • 公鸡数量为 i i i
  • 母鸡数量为 j j j
  • 小鸡数量为 k k k
• 必须满足的两个等式：
  • 数量守恒： i + j + k = m i + j + k = m i+j+k=m （鸡的总数是 m m m）
  • 价格守恒： i × x + j × y + k z = n i \times x + j \times y + \frac{k}{z} = n i×x+j×y+zk​=n （总花费是 n n n）
• 隐含条件：
  • k k k 必须能被 z z z 整除（因为题目说 z z z 只小鸡 1 元，如果买的小鸡数量不是 z z z 的倍数，价格就不是整数，这在古代数学题中通常隐含价格为整数，且代码中 k/z 若不能整除会有精度问题，需特别判断）
  • i , j , k i, j, k i,j,k 必须是非负整数。

思路方案

• 方案 A：三层循环
  • 写三层 for 循环
  • 时间复杂度： O ( m 3 ) O(m^3) O(m3)

// ❌ 效率低，不推荐for(int i =0; i <= m; i++){// 第一层：猜公鸡数量for(int j =0; j <= m; j++){// 第二层：猜母鸡数量for(int k =0; k <= m; k++){// 第三层：猜小鸡数量// 此时我们要检查两个条件：// 1. 数量够不够 m 只？ (i + j + k == m)// 2. 钱对不对？if(i + j + k == m && k % z ==0&&(i * x + j * y + k / z == n)){ count++;}}}}

• 方案 B：两层循环
  • 时间复杂度： O ( m 2 ) O(m^2) O(m2)

#include<stdio.h>intmain(){// 定义变量// x: 公鸡单价, y: 母鸡单价, z: z只小鸡1元// n: 总钱数, m: 总鸡数int x, y, z, n, m;// 读取输入if(scanf("%d %d %d %d %d",&x,&y,&z,&n,&m)!=5){return1;}int count =0;// 用来记录满足条件的方案总数// 第一层循环：枚举公鸡数量 i// 公鸡最多买 m 只（其实也可以优化为 n/x 只，但写 m 不会错且逻辑简单）for(int i =0; i <= m; i++){// 第二层循环：枚举母鸡数量 j// 母鸡的数量加上公鸡数量不能超过总数 mfor(int j =0; j <= m - i; j++){// 剩下的就是小鸡数量 kint k = m - i - j;// 核心判断逻辑：// 1. k % z == 0 : 小鸡数量必须是 z 的倍数，否则价格不是整数（题目隐含逻辑）// 2. 价格公式 : 公鸡钱 + 母鸡钱 + 小鸡钱 == 总钱数 nif(k % z ==0&&(i * x + j * y + k / z == n)){ count++;// 如果满足条件，方案数 +1}}}// 输出结果printf("%d\n", count);return0;}

经典案例讲解二：盛最多水的容器

Lucy的空间骇客裂缝：力扣（盛最多水的容器）

暴力枚举算法

// 辅助函数：求两个数的较小值intmin(int a,int b){return a < b ? a : b;}intmaxArea(int* height,int heightSize){int max_water =0;// 用于记录最大水量// 外层循环：确定左边界 ifor(int i =0; i < heightSize -1; i++){// 内层循环：确定右边界 jfor(int j = i +1; j < heightSize; j++){// 1. 计算当前容器的高度（受限于较短的一边）int current_height =min(height[i], height[j]);// 2. 计算当前容器的宽度int current_width = j - i;// 3. 计算当前面积int current_area = current_height * current_width;// 4. 如果当前面积比历史最大值大，则更新if(current_area > max_water){ max_water = current_area;}}}return max_water;}

• 这段代码
  又是函数开销，又是双for循环实现的暴力枚举，在比赛中很容易导致超时

所以暴力枚举只要不是没办法，最好慎用！！！

最优解

#defineMAX(a,b)(a>b?a:b)#defineMIN(a,b)(a<b?a:b)intmaxArea(int* height,int heightSize){int ret =0;int l =0;int r = heightSize -1;while(l < r){int current_height =MIN(height[l], height[r]);int current_Water = current_height *(r - l); ret =MAX(ret, current_Water);if(height[l]< height[r]){++l;}else{--r;}}return ret;}

运用#define宏定义来减少开销，并运用双指针避免用到双for循环 导致超时

经典案例讲解三：两数之和

Lucy的空间骇客裂缝：力扣（两数之和）

解题思路

• 暴力枚举的核心思想
  检查数组中每一个可能的数对组合
  • 外层循环： 使用指针i从数组的第0个元素遍历到倒数第2个元素
  • 内层循环： 使用指针j从i + 1开始遍历到数组的最后一个元素（这样可以避免重复使用同一个元素，且避免重复检查）
  • 判断： 如果 nums[i] + nums[j] == target，则说明找到了答案
  • 返回： 分配内存并返回包含i和j的数组

代码示例

int*twoSum(int* nums,int numsSize,int target,int* returnSize){// 外层循环：遍历第一个数for(int i =0; i < numsSize; i++){// 内层循环：遍历第二个数// j 从 i+1 开始，确保不重复使用元素，也不重复计算for(int j = i +1; j < numsSize; j++){// 判断两数之和是否等于目标值if(nums[i]+ nums[j]== target){// 分配内存用于存储结果（需要存放2个int）int* result =(int*)malloc(2*sizeof(int));// 检查内存分配是否成功if(result ==NULL){*returnSize =0;returnNULL;}// 存入下标 result[0]= i; result[1]= j;// 设置返回数组的大小为 2*returnSize =2;// 返回结果指针return result;}}}}

🔥下面罗列出这段代码中需要强调的点🔥

• int* result = (int*)malloc(2 * sizeof(int));

result → [ int空间 ][ int空间 ] result[0] result[1] 

• result[0] = i;
result[1] = j;
  虽然result是指针，但可以像数组一样使用
  result[0] 等价于 *(result + 0)
result[1] 等价于 *(result + 1)

数组和指针关系不理解的看下面
Lucy的空间骇客裂缝：数组与指针

经典案例讲解四：2025

这是一个非常经典的暴力枚举（Brute Force） 算法题目

💻 代码实现

#include<iostream> using namespace std; bool check(int num){int c0 =0, c2 =0, c5 =0;//逐步取出最后一个数字while(num >0){int my_Function_Num = num %10;if(my_Function_Num ==0){ c0++;}elseif(my_Function_Num ==2){ c2++;}elseif(my_Function_Num ==5){ c5++;} num /=10;}// 条件：至少1个0，2个2，1个5return(c2 >=2)&&(c0 >=1)&&(c5 >=1);}intmain(){//统计满足条件的数的数量int count =0;//检查函数，判断一个数是否满足条件for(int i =0; i <=20250412; i++){if(check(i)){ count++;}} cout <<"满足条件的数的数量为："<< count << endl;return0;}

希望读者多多三连

给小编一些动力

蟹蟹啦！