C++019-C++暴力枚举
C++019-C++暴力枚举
在线练习：
枚举
枚举就是列出一个范围内的所有成员的程序，或者说是将所有情况都举出，并判断其是否符合题目条件，生活中常见的枚举有星期里面有星期一、星期二…星期日。在前面我们已经接触过简单的枚举，了解过枚举的概念。
关于简单枚举，其概念我们已经抓住要点:
定范围 列成员 选类型 算答案
枚举优缺点
优点:
1.能举出所有情况，保证解为正确解。 ⒉.能解决许多用其他算法难以解决的问题。 3.便于思考与编程。
缺点:
枚举–暴力枚举理论上这种方式能求解一切问题，然而暴力枚举仅适用于一些规模较小的问题，对于规模巨大的情形，时间复杂度会过高
多重枚举
有时候，我们需要求解的变量不止一个，这时候，将涉及到多重变量的枚举,枚举一切可能情形的组合，再从中筛选出合法的解。
枚举两个变量x和y:
#include <bits/stdc++.h>
using namespace std;
int main()
{
for(int x=left;x<=right;x++)
{
for(int y=left1;y<=right1;y++)
{
//删选x和y的取值组合
}
}
return 0;
}复杂度很高
枚举举例
题目描述 百钱买百鸡
题目描述
一只公鸡值5元，一只母鸡值3元，而1元可买3只小鸡。现有100元钱，想买100只鸡。问可买公鸡、母鸡、小鸡各几只?
解题思路
用枚举思想来验证：
在数学中解决这个问题，设公鸡x只，母鸡y只，小鸡z只，则: x+y+z=100 5_x+3_y+z/3=100 同时满足上述两个条件的x、y、z值就是所求。 为了解决以上的问题，我们可以通过三重循环将所有情况都列一遍，然后通过if判断是不是满足条件，如果满足条件，便输出。 公鸡数量x的取值范围是0-100/5， 母鸡数量y的取值范围是0-100/3, 小鸡数量z的取值范围是0-3*100。
解决方法1：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z;
for(x=0;x<=100/5;x++)
for(y=0;y<=100/3;y++)
for(z=0;z<=3*100;z++)
{
if(5*x+3*y+z/3==100 && x+y+z==100)
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
return 0;
}输出为：
修正浮点数的方法
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z;
for(x=0;x<=100/5;x++)
for(y=0;y<=100/3;y++)
for(z=0;z<=3*100;z++)
{
// if(5*x+3*y+z/3==100 && x+y+z==100)
if(5*x+3*y+z/3.0==100 && x+y+z==100) //修正浮点数
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
return 0;
}
算法优化
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y,z;
for(x=0;x<=100/5;x++)
for(y=0;y<=100/3;y++)
{
z=100-x-y; //减少一层循环
if(5*x+3*y+z/3.0==100 && x+y+z==100) //修正浮点数
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
return 0;
}添加计算时间
//#include <bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include <time.h>
using namespace std;
clock_t start,stop;
double duration;
int main()
{
start = clock();
int money=10000;
int x,y,z;
for(x=0;x<=money/5;x++)
for(y=0;y<=money/3;y++)
// for(z=0;z<=money*3;z++)
{
z=money-x-y; //减少一层循环
if(5*x+3*y+z/3.0==money && x+y+z==money) //修正浮点数
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
stop = clock();
duration = ((double)(stop-start))/CLK_TCK;
printf("The time was:%.5lfs",(double)clock()/CLOCKS_PER_SEC);
return 0;
}一重循环优化
最终优化（一重循环）
在尝到直接削去一重循环带来的甜头后，不知足的我们又开始想，是否可以再削去一重循环，只用一重循环来解决呢？我们反观上面的二重循环，发现我们并没有使用z这个变量了，那么我们在只使用一重循环的时候，是否也应该只使用一个变量呢？我们想到，x,y,z之间并不是毫无联系的，我们假设万钱刚好买到万鸡，据此我们列出两个方程组：
5*x+3*y+z/3=10000 x+y+z=10000
我们进行数学消元，只保留x，得到
y=2500-7*x/4 z=7500+3*x/4，
这是我们假设条件成立得到的关系式，下面我们只需令x取不同的值，同时对y和z进行检查，若x,y,z均满足我们预设的条件，那么这组解就是有效的。对于y，我们要令其为非负数，所以x不能大于1428；对于z，我们要令其为3的倍数。此外，我们得到的y和z两个关于x的关系式是由假设上述两个方程组成立得到的，所以我们的解还需要满足上述两个关系式。据此，我们得到以下的代码：
#include<iostream>
#include<stdio.h>
#include <time.h>
using namespace std;
clock_t start,stop;
double duration;
int main()
{
start = clock();
int money=10000;
int x,y,z;
for(x=0; x<1429; x++)
{
y = 2500-7*x/4;
z = 7500+3*x/4;
if((x+y+z==money)&&(5*x+3*y+z/3==money)&&(z%3==0))
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}
stop = clock();
duration = ((double)(stop-start))/CLK_TCK;
printf("The time was:%.5lfs",(double)clock()/CLOCKS_PER_SEC);
return 0;
}总结
作业
在线练习：
总结
本系列为C++学习系列，会介绍C++基础语法，基础算法与数据结构的相关内容。本文为C++循环结构的中的暴力枚举案例，包括相关案例练习。
腾讯云开发者
