枚举算法介绍

枚举算法介绍基本思想 枚举也称作穷举 指的是从问题所有可能的解的集合中一一枚举各元素 用题目中给定的检验条件判定哪些是无用的 哪些是有用的 能使命题成立 枚举法的本质就是从所有候选答案中去搜索正确的解 使用该算法需要满足两个条件 1 可预先确定候选答案的数量 2 候选答案的范围在求解之前必须有一个确定的集合

大家好,我是讯享网,很高兴认识大家。

基本思想:

      枚举也称作穷举,指的是从问题所有可能的解的集合中一一枚举各元素。用题目中给定的检验条件判定哪些是无用的,哪些是有用的。能使命题成立。枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:(1)可预先确定候选答案的数量;(2)候选答案的范围在求解之前必须有一个确定的集合。

基本框架:

设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank

for a1←a11 to a1k do

     for a2←a21 to a2k do

         ……………………

              for ai←ai1 to aik do

                   ……………………

                        for an←an1 to ank do

                            if 状态(a1,…,ai,…,an)满足检验条件

                            then 输出问题的解;

 优缺点:

  • 优点:算法简单,在局部地方使用枚举法,效果十分的好
  • 缺点:运算量过大,当问题的规模变大的时候,循环的阶数越大,执行速度越慢


讯享网

 实例:

例1:火柴棒等式

【问题描述】给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示:

注意:

     1. 加号与等号各自需要两根火柴棍

     2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C≥0)

     3. n根火柴棍必须全部用上

【输入】输入一个整数n(n≤24)。

【输出】输出能拼成的不同等式的数目。 

问题简述:给你n(n<=24)根火柴棒,叫你拼出 “A + B = C”这样的等式,求方案数。

提示:1.将0~9所需火柴数保存在一个数组,2.设计一个函数,该函数可计算出A、B、C所需的火柴数。

#include <bits/stdc++.h> using namespace std; int b[10]={6,2,5,5,4,5,6,3,7,6};//保存0~9各自需要的火柴数 int a[2222]={6,2,5,5,4,5,6,3,7,6};//保存每个数对应的火柴数 int need(int x)//计算x所需火柴数 { int c=0,sum=0; if(x==0)return 6; while(x!=0) { c=x%10; sum+=b[c]; x=x/10; } return sum; } int main() { int n; cin>>n; int ans=0; for(int i=10;i<=2222;i++) a[i]=need(i); for(int i=0;i<1000;i++) for(int j=0;j<1000;j++) { a[i]=need(i); b[j]=need(j); if(need(i+j)+need(i)+need(j)+4==n) ans++; } cout<<ans; return 0; } 

讯享网

例二:使用枚举法解决“填写运算符问题”

【问题描述】:在下面的算式中,添加“+”、“-”,“*”,“/”,4个运算符,使得这个式子成立。
 5  5  5  5  5=5
【算法分析】:上述式子左侧有5个数字,一共需要4个运算符。根据题目要求,两个数字之间的运算符只能有4中选择。在 具体编程时,可以通过循环来填入各种运算符,然后再判断算式左侧的值是否等于右侧的值。并保证,当填入的 是除号时,则右侧的数不能为0,并且乘除的优先级高于加减的优先级。
本题借鉴了博主M李丽的代码

讯享网#include<iostream> int main() { int j, i[5]; // 循环变量,数组i用来表示4个运算符 int sign; // 累加运算时的符号; int result; // 保存运算式子的结果值 int count=0; // 计数器,统计符合条件的方案 int num[6]; // 保存操作数 float left, right; //保存中间结果 char oper[5] = { ' ','+','-','*','/' }; //运算符 printf("输入5个数,之间用空格隔开:"); for (j = 1; j <= 5; j++) scanf_s("%d",&num[j]); printf("输入结果:"); scanf_s("%d",&result); //注:这里i[1]代表的第一个运算符的意思,i[1]=1代表第一个运算符是“+”,i[1]=2代表第一个运算符是“减”,i[1]=3代表第一个运算符是“-”,i[1]=4代表第一个运算符是“/” //注:这里i[2]代表的第二个运算符的意思,i[2]=1代表第二个运算符是“+”,i[2]=2代表第二个运算符是“减”,i[2]=3代表第二个运算符是“-”,i[2]=4代表第二个运算符是“/” //i[3],i[4]依次类推。 for (i[1]=1; i[1]<=4; i[1]++) //循环4种运算符,1表示+,2表示-,3表示*,4表示/ { if ((i[1]<4) || (num[2] != 0)) //运算符若是/,则第二个运算数不能为0,(注:“||”是或运算,两个条件至少要有一个成立,即第一个运算符为/时,第二个运算数不为0) { for (i[2]=1; i[2]<=4; i[2]++) { if ((i[2]<4)||(num[3]!= 0)) //当第二个运算符为/时,第三个运算数不为0 { for (i[3] = 1; i[3] <= 4; i[3]++) { if ((i[3] < 4) ||( num[4] != 0)) //当第三个运算符为/时,第四个运算数不为0 { for (i[4] = 1; i[4] <= 4; i[4]++) { if ((i[4] < 4) || (num[5] != 0)) //当第四个运算符为/时,第五个运算数不为0 { left = 0; right = num[1]; sign = 1; //使用case语句,将4种运算符填到对应的空格位置,并进行计算 for (j = 1; j <= 4; j++) { switch (oper[i[j]]) { case '+': left = left + sign*right; sign = 1; right = num[j + 1]; break; case '-': left = left + sign*right; sign = -1; right = num[j + 1]; break; case '*': right = right*num[j + 1]; break; case '/': right = right / num[j + 1]; break; } } //开始判断,如果运算式子的结果和输入的结果相同,则表示找到一种算法,并输出这个解 if (left + sign*right == result) { count++; printf("%3d:",count); for (j = 1; j <= 4; j++) printf("%d%c",num[j],oper[i[j]]); printf("%d=%d\n",num[5],result); } } } } } } } } } if (count == 0) printf("没有符合要求的方法!\n"); system("pause"); return 0; } 

小讯
上一篇 2025-02-26 21:34
下一篇 2025-03-19 07:34

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/112872.html