搜索 循环枚举
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了搜索 循环枚举,现在分享给大家,供学习和参考。文章包含1889字,纯文字阅读大概需要5分钟。
教程信息
通过题目解题认识循环枚举搜索
题目来源:
https://www.luogu.com.cn/problem/P4956
题目内容:
循环枚举就是用循环实现暴力枚举的过程。核心思路就是回答下列几个问题:
1、枚举哪些变量?
2、从哪枚举到哪?
3、哪些可能性是符合要求的?
4、这个解法有无优化的可能?
一、朴素的循环枚举
1、枚举哪些变量?——题目中提到的x(每个星期一筹集到的钱)
和k(星期一往后每天增量筹集的钱)
2、从哪枚举到哪?——题目中提到0 < x≤ 100,1456 ≤N≤ 145600,在满(3)时,0 < k≤ 133(145600/(21*52)=133.3333,用最大目标金额除于全年增量的K的最大倍数,得出K最多不能大于133)
3、哪些可能性是符合要求的?——(x+x+k+x+2k+x+3k+x+4k+x+5k+x+6k)*52==n,即(7x+21k)*52==n
4、这个解法有无优化的可能?——有,后续继续分析。
代码实现:
#include<bits/stdc++.h> using namespace std; int main() { int n,x,k; //定义一下 cin>>n; int count=0; // 要找x最大,k最小的情况,所以找x的时候就要从1开始往大找,【因为会跑完全排列,最后匹配的数就是最大的数。】 for (int i=1;i<=100;i++) { // k则往小找,x与k中保留的就是最终答案【因为会跑完全排列,最后匹配的数就是最小的数。】 for (int j=133;j>=1;j--) { if(i*7+j*21==n/52) { x=i; k=j; } count++; } } cout<<"X结果:"<<x<<endl<<"k结果:"<<k<<endl; cout<<"循环次数:"<<count<<endl; return 0; }
执行结果:
二、优化的循环枚举
对于循环枚举而言,其最大的问题就在于“慢”(多个for嵌套),甚至在限定的时间范围内慢到得不出想要的答案。因此常常对循环枚举进行优化,而不是单单无脑列出每一个结果。
一般来说,循环枚举的优化有两种方法——缩小枚举范围(减少某个for的循环次数),局部枚举(减少for循环的个数)。
1、缩小枚举范围
通过对问题三“哪些可能性是符合要求的?”所对应的表达式进行分析,从而对问题二“从哪枚举到哪?”进行范围的收缩
——上题中,因为要找x最大,k最小的情况,可以改变循环方向,要找x最大,就从大到小;要找k最小,就从小到大,第一个找到的就是最终答案,后续的可以跳过,从而缩小了枚举范围。
实现代码:
#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int count=0; // 要找x最大,就从大到小 for (int i = 100; i > 0; i--) { // 要找k最小,就从小到大 for (int j = 1; j <= 133; j++) { count++; if (i * 7 + j * 21 == n / 52) { cout<<"X结果:"<<i<<endl<<"k结果:"<<j<<endl; cout<<"循环次数:"<<count<<endl; return 0; } } } }
执行结果:
2、局部枚举
又称减少枚举变量,如果存在某个局部,一旦这个局部的状态被确定,那么剩余其他部分的状态只能是确定的一种,或者不多的几种,那么就只需枚举这个局部的状态即可,即原来需要枚举的变量数是n,现在只需要枚举其中的m种,而剩下的m-n个变量的状态可以由m个变量确定,那么枚举循环就少了m-n个,时间复杂度大大降低。
——上题中,因为(7x+21k)*52==n,所以k实际上可以用(n/52-7x)/21来表示,若当前k是一个正整数(向上向下取整相同),则问题顺利解决。
实现代码:
#include<bits/stdc++.h> using namespace std; int main() { double n; cin>>n; n=n/52; int count=0; for (int i=100;i>=1;i--) { count++; double j=(n-7*i)/21; if(floor(j)==ceil(j)&&j>0) { cout<<"X结果:"<<i<<endl<<"k结果:"<<j<<endl; cout<<"循环次数:"<<count<<endl; return 0; } } return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供搜索 循环枚举的全部内容,希望教程文章能够帮你了解学习搜索 循环枚举,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-258.html