美文网首页
C/C++程序设计常用算法——穷举法

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

作者: Aliven888 | 来源:发表于2020-09-22 11:27 被阅读0次

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


    资料仅供学习交流使用。
    作者: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;
                    }
                }
            }
        }
    }
    

    运行结果:

    运行结果

    相关文章

      网友评论

          本文标题:C/C++程序设计常用算法——穷举法

          本文链接:https://www.haomeiwen.com/subject/mvgvyktx.html