首页 > 代码库 > 数据结构与算法之枚举（穷举）法 C++实现
数据结构与算法之枚举（穷举）法 C++实现
枚举法的本质就是从全部候选答案中去搜索正确的解，使用该算法须要满足两个条件：
1、能够先确定候选答案的数量。
2、候选答案的范围在求解之前必须是一个确定的集合。
枚举是最简单。最基础。也是最没效率的算法
枚举法长处：
1、枚举有超级无敌准确性。仅仅要时间足够。正确的枚举得出的结论是绝对正确的。
2、枚举拥有天下第一全面性，由于它是对全部方案的全面搜索。所以，它可以得出全部的解。
程序优化：
对于枚举算法，加强约束条件，缩小枚举的范围。是程序优化的主要考虑方向。
实例1：百钱买百鸡
一百个铜钱买了一百仅仅鸡。当中公鸡一仅仅3钱、母鸡一仅仅5钱。小鸡一钱3仅仅，问一百仅仅鸡中公鸡、母鸡、小鸡各多少）
一百个铜钱买了一百仅仅鸡。当中公鸡一仅仅3钱、母鸡一仅仅5钱。小鸡一钱3仅仅，问一百仅仅鸡中公鸡、母鸡、小鸡各多少）
代码：
#include<iostream>
const int COCKPR = 3;
const int HENPR = 5;
const int CHICKS = 3; //原错误const double CHICKPR = 1/3; 1 3 为整形，1/3也为整形所以为0,又一次声明1钱能买3仅仅小鸡
void buyChicken(int money, int chooks);
int main()
{
int money = 100;
int chooks = 100;
buyChicken(money, chooks);
return 0;
}
void buyChicken(int money, int chooks)
{
using namespace std;
int MaxCock = money/COCKPR;
int MaxHen = money/HENPR;
int MaxChick = chooks;
int cock,hen,chick;
int count = 0;
for(cock=0; cock<= MaxCock; cock++)
{
for(hen=0; hen<=MaxHen; hen++)
{
for(chick=0; chick<=MaxChick; chick++)
{
if (0 == chick%3 && cock + hen + chick == chooks && COCKPR*cock + HENPR*hen + chick/CHICKS == money)
cout << "公鸡: " << cock << " 母鸡: " << hen << " 小鸡: " << chick << " 第 " << count << "有结果" <<endl;
count ++;
}
}
}
cout << "总共枚举多少次：" << count <<endl;
}
执行结果：
仅仅对小鸡的数量加入一个最小的起始值
函数里面加 int MinChick = chooks-MaxCock-MaxHen;
把最里层小鸡数量的for循环的起始条件改为小鸡最小值 for(chick=MinChick; chick<=MaxChick; chick++)
运算时间复杂度例如以下。
时间复杂度降低一半。说明对于枚举算法。加强约束条件。缩小枚举的范围，是程序优化的主要考虑方向。
代码例如以下：
#include<iostream>
const int COCKPR = 3;
const int HENPR = 5;
const int CHICKS = 3; //原错误const double CHICKPR = 1/3; 1 3 为整形。1/3也为整形所以为0,又一次声明1钱能买3仅仅小鸡
void buyChicken(int money, int chooks);
int main()
{
int money = 100;
int chooks = 100;
buyChicken(money, chooks);
return 0;
}
void buyChicken(int money, int chooks)
{
using namespace std;
int MaxCock = money/COCKPR;
int MaxHen = money/HENPR;
int MaxChick = chooks;
int MinChick = chooks-MaxCock-MaxHen;
int cock,hen,chick;
int count = 0;
for(cock=0; cock<= MaxCock; cock++)
{
for(hen=0; hen<=MaxHen; hen++)
{
for(chick=MinChick; chick<=MaxChick; chick++)
{
if (0 == chick%3 && cock + hen + chick == chooks && COCKPR*cock + HENPR*hen + chick/CHICKS == money)
cout << "公鸡: " << cock << " 母鸡: " << hen << " 小鸡: " << chick << " 第 " << count << "有结果" <<endl;
count ++;
}
}
}
cout << "总共枚举多少次：" << count <<endl;
}实例2：填数字游戏
代码：
#include<iostream>
int main()
{
using namespace std;
int t1,t2,t3,t4,t5;
for (t1=1; t1<=9; t1++)
{
for(t2=0; t2<=9; t2++)
{
for(t3=0; t3<=9; t3++)
{
for(t4=0; t4<=9; t4++)
{
for(t5=0; t5<=9; t5++)
{
if(t5*100000 + t5*10000 + t5*1000 + t5*100 + t5*10 + t5 == t5*t1 + t4*t1*10 + t3*t1*100 + t2*t1*1000 + t1 *t1*10000 )
{
cout << " 算的数值为: " << t1 << " 法的数值为: " << t2 << " 描的数值为: " <<t3 << " 述的数值为: " << t4 << " 题的数值为: " << t5<<endl;
cout << " " << t1 << " " << t2 << " " << t3 << " " << t4 << " " << t5 <<endl;
cout << "X " << t1<<endl;
cout << "________________\n";
cout << " " << t5 << " " << t5 << " " << t5 << " " << t5 << " " << t5 << " " << t5 <<endl;
}
}
}
}
}
}
return 0;
}
执行结果：
数据结构与算法之枚举（穷举）法 C++实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。