枚举——简单枚举

古代科举考试时，考生要在砚台下放一枚铜钱，寓意‘一举成名’。 #生活乐趣# #日常生活趣事# #生活智慧小知识# #历史文化趣闻#

  第一次写博客，写得不好请见谅，我想把acm之路的过程记录下来

思想：

1、枚举也称暴力法，很多问题都可以通过枚举来完成，虽然大多数题目都有可能超时，但是枚举法都是分析清楚题目的初始解法，本人中招过某些题目就是因为想得太复杂而做不出甚至浪费大量时间

2、主要是通过枚举所有可能的解或者子集来对比是否是自己想要的结果

例如：输出前n个素数，就是由枚举2—n的数来判断是否为素数，emm还是做题实际

穷举算法的步骤：

1、明确问题的答案范围，这是最难的，首先要明确要枚举什么，其次要明确枚举的数量，在其中可能会配合数学知识来减少不必要的枚举

2、（1）对每一种可能进行判断（2）若不满足的话就进行下一个可能，如果符合的话就跳出

例题链接：百练的2810:完美立方 例题原图：

例题分析：

由于a,b,c,d都是整数且少于100，并且a >（b <= c <= d），所以我们按照提议枚举a,b,c,d所有可能的样例就行了

解答：

#include <iostream>

#include <cstdio>

using namespace std;

int main(){

int a,b,c,d;

int n;

scanf("%d",&n);

for(int a = 5; a <= n; a++)

for(int b = 2; b < a; b++)

for(int c = b; c < a; c++)

for(int d = c; d < a; d++)

if(a*a*a == b*b*b+c*c*c+d*d*d){

printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);

}

return 0;

}

这道枚举是不是很简单，那再来一道要点思考的，要用到一点数学

例题链接：UVa10976：分数拆分 图片：

题目大意：输入一个k，让你求得所有的满足 1/k = 1/x + 1/y 的情况，并且打印出来 。 分析：

这是紫书上的一题，看完题目就知道要枚举x和y了，但是x和y的上限是完全不知道的，这个时候我们就要对题目给出来的数据进行分析了：

1、x>=y，则有1/x <=1/y，因此1/k<=1/y+1/y；由此可得y的上限为2k

2、知道y后怎样判断x是否为整数是一个问题，这个时候我们就要对题目的等式进行化简了，最后当 k*y%(y-k) == 0 就知道x是否为整数了

这题展现了暴力求解的时候也是要结合一定的思考和数学知识，不然可能连暴力的数据范围也不知道

代码：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <map>

using namespace std;

const double minn = 1e-6;

int main(){

int k;

while(scanf("%d",&k) == 1){

map<int,int> store;

int num = 0;

for(int y = k+1; y <= 2*k; y++)

if(k*y% (y-k) == 0){

store[y] = k*y/(y-k);

num++;

}

printf("%d\n",num);

for(map<int,int>::iterator it = store.begin(); it != store.end(); it++){

printf("1/%d = 1/%d + 1/%d\n",k,it->second,it->first);

}

}

return 0;

}

简单枚举的内容大概为以上这些，建议配合大量的练习，下面给出了紫书的两道题，建议练习：

UVA725：Division     

UVA11059： Maximum Product

答案在这里-->点击打开链接

枚举进阶篇：点击打开链接

如果有眼前一亮的题目或者解答欢迎和楼主讨论 ε=ε=ε=┏(゜ロ゜;)┛ 楼主的QQ486291187.

网址：枚举——简单枚举 https://www.yuejiaxmz.com/news/view/950737

相关内容

枚举算法应用解析
现代枚简装修，简约而不简单
瑜伽好处不胜枚举 练习注意4事项
旅行商问题（枚举，回溯，动态规划，贪心，分支界限）
河北这枚金牌沉甸甸
百亿补贴:BRITA 碧然德 标准版滤芯 4枚 多人团 81元
收纳控也要情怀 快收了这枚冰箱酒瓶磁力贴
素食主义菌菇粽4枚装热量
魅洁 马桶清洁剂 蓝泡泡 20枚装 14.8元包邮（需用券）
34枚金币时间管理法

随便看看