文档声明:
以下资料均属于本人在学习过程中产出的学习笔记,如果错误或者遗漏之处,请多多指正。并且该文档在后期会随着学习的深入不断补充完善。
资料仅供学习交流使用。
作者:Aliven888
1、简述
程序设计的关键就是算法,算法简单来说就是程序设计时问题解题步骤或者数据数据的流程。这里我们将介绍以下几种常用的算法:迭代法、穷举法、递推法、递归发、回溯法、贪婪法、查找算法、排序算法。
本章节主要介绍穷举法。
2、穷举法
穷举法是对众多候选答案按照一定顺序逐一验证,最终得出正确答案的过程。其中心思想就是:首先根据问题的部分条件预估答案的范围,然后在此范围内对所有可能的情况逐一验证,直到全部问题均通过了验证为止,而满足这个情况的就是最终的答案。
如果某个候选答案满足所有的条件,表示该候选答案就是正确答案;如果全部候选答案遍历完了后,依旧没有符合所有条件候选答案,那么说明该问题无解。
特点:
算法简单,而且容易理解,但是因为涉及到大量重复操作,导致运算量比较大。
注意事项:
- 穷举法的候选答案必须是有限个的,不能造成死循环。
代码实例:
void fun()
{
//算法:100元面值的人民币换成用20元、10元 、5元面值的人民币,
//在每种面值至少存在一张的情况下,有多少种组合。
//首先我们分析题目可以得出如下结论:
// 20 元面值的最多只能有 4 张
// 10 元面值的最多只能有 7 张
// 5 元面值的最多只能有 14 张
//定义组合变量
int iNum_20 = 0; //20元面值的张数
int iNum_10 = 0; //10元面值的张数
int iNum_5 = 0; //5元面值的张数
int iCount = 0; //组合计数
for (iNum_20 = 1; iNum_20 <= 4; iNum_20++) //穷举 20 元面值的所有情况
{
for (iNum_10 = 1; iNum_10 <= 7; iNum_10++) //穷举 10 元面值的所有情况
{
for (iNum_5 = 1; iNum_5 <= 14; iNum_5++) //穷举 5 元面值的所有情况
{
if (100 == ((iNum_20 * 20) + (iNum_10 * 10) + (iNum_5 * 5)))
{
++iCount;
cout << "第" << iCount << "种组合:20元面值" << iNum_20 << "张 - 10元面值" << iNum_10 << "张 - 5元面值" << iNum_5 << "张" << endl;
}
}
}
}
}
运行结果:
网友评论