C/C++程序设计常用算法——穷举法

文档声明：
以下资料均属于本人在学习过程中产出的学习笔记，如果错误或者遗漏之处，请多多指正。并且该文档在后期会随着学习的深入不断补充完善。

---

资料仅供学习交流使用。
作者：Aliven888

1、简述

  程序设计的关键就是算法，算法简单来说就是程序设计时问题解题步骤或者数据数据的流程。这里我们将介绍以下几种常用的算法：迭代法、穷举法、递推法、递归发、回溯法、贪婪法、查找算法、排序算法。

本章节主要介绍穷举法。

2、穷举法

  穷举法是对众多候选答案按照一定顺序逐一验证，最终得出正确答案的过程。其中心思想就是：首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况逐一验证，直到全部问题均通过了验证为止，而满足这个情况的就是最终的答案。
  如果某个候选答案满足所有的条件，表示该候选答案就是正确答案；如果全部候选答案遍历完了后，依旧没有符合所有条件候选答案，那么说明该问题无解。

特点：
  算法简单，而且容易理解，但是因为涉及到大量重复操作，导致运算量比较大。

注意事项：

1. 穷举法的候选答案必须是有限个的，不能造成死循环。

代码实例：

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;
                }
            }
        }
    }
}

运行结果：

运行结果