网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
易语言吧 关注：266,566贴子：1,664,569
  • 11回复贴，共1页

【XramixStudio】【教程】易语言：：贪心算法

取消只看楼主收藏回复

课前注意：为保证易吧热度特发教程，XramixStudio所有权
前言：在本文大家将学到一个新算法叫做贪心算法，贪心算法求局部最优解，但是没有固定模型，做题时注意可不可以用贪心算法来解决该模型
这里有一道题：

题目样例：

前面输入的两个数是题目的n和r，后面n个数是打水人数所需时间
我们先来列个变量再来讲解题目吧：
1楼2017-12-12 23:05回复
    首先题目的意思是想求出最快的排队时间
    且每次可能有比较多的水龙头
    我们先看只有一个水龙头的情况：
    n:3
    r:1(一个水龙头)
    2
    5
    8
    那么2 5 8分别是三个人所需时间，第一个人打水的时间也会影响到后面的人
    那么顺序也肯定是258（题目中顺序需要排序）
    2+5=7
    7+2=9（算上前面第一个人打水时间）
    9+8=17
    17+7=24(上个人等待的时间再算上自身的）
    一样的如果是两个水龙头的情况
    第一个水龙头：2 8
    第二个：5
    （具体怎么分配需要问可以现场回复）
    这样第一个水龙头需要的：2+8+2=12
    第二个只有一个，总共：5
    因为题目要求全部时间，那么12+5=17
    所以两个水龙头的情况就是17
    4楼2017-12-12 23:14
    回复
      这题目就是**的要算算前面那个人打水的时间要最短，所以有了这鬼畜的题目
      5楼2017-12-12 23:15
      回复

        首先j t变量是我们一会儿要用的，n，r先输入，然后这边可能有些人不懂：为什么要在队这个变量数组每个赋值为999？
        因为接下来要用的是易语言的排序函数，如果直接用前面几个一定是0，因为0是最小的，于是我们要让每个数组都大于可能输入的时间，然后输入的时候覆盖，排序后999一定在时间的后面，因为999我们假设比每个时间都大，所以我们只要取前面几个，不算999的部分就可以了
        万一大于999我们也可以设成9999
        当然了这里也可以用重定义数组，无限数组等来解决问题，易语言虽然这方面好用，但是为了锻炼其他语言的思想（因为其他语言没这玩意儿）那还是每个都赋值吧
        6楼2017-12-12 23:18
        回复
          今天先更到这里，给大家弄懂题目，明天开始核心部分
          7楼2017-12-12 23:21
          回复
            顶
            来自Android客户端11楼2017-12-13 20:56
            回复
              之前拖更现在继续更新
              14楼2017-12-16 10:31
              回复

                这是剩下的代码，我来做解释
                首先第一行判断r是否为0，如果没有水龙头直接输出0
                下面的循环意思是输入n个人的等待时间（简单吧）
                然后为了使我们更方便，让等待时间从小到大进行排序，直接用易语言的数组排序函数，当然也可以用选择排序
                这边的排序会把0算进去，我们也可以把数组改成0，输入n的时候重定义数组这样就不会有0的情况了，也可以留个很大的数组全部赋值999，输入的时候覆盖，当然这只是模拟时间都不会超过999的情况
                接下来是代码的核心部分，由于贪心算法没有定型，所以不一定每个贪心算法都长得差不多
                先进行判断，j变量的意思是到第几个水龙头了，如果j分配到最后一个水龙头，就重新再从第一个水龙头开始分配，意思就是：
                样例：
                3
                2
                1
                2
                3
                假设是这样，那么程序执行到j=3的时候就会变成1
                此时前面两步就是将排序前面最少的两个数分配到两个水龙头里，接下来再把剩下的也按这样的顺序分配，当然3是最后一个数所以直接挤第一个水龙头就可以达到最小时间
                所以对临时队的操作就是分配水龙头
                然后放进总共计算时间的t变量里
                然后输出
                那么贪心算法最基本的一道题是讲完了，过几天还会再讲个这个排队打水的升级版，也会附上详细的讲解哦！
                如果有什么不会的，可以在以下帖子回复，或者加入本工作室群：424820976
                ——XramixStudio代码所有
                15楼2017-12-16 10:38
                收起回复
                  ddt
                  16楼2017-12-16 10:48
                  收起回复
                    ddt
                    来自Android客户端19楼2017-12-16 13:08
                    回复
                      ddt
                      来自Android客户端20楼2017-12-16 23:01
                      回复
                        ddt
                        26楼2017-12-23 17:18
                        回复

                          扫二维码下载贴吧客户端

                          下载贴吧APP
                          看高清直播、视频！
                          • 11回复贴，共1页
                          发表回复
                          发贴请遵守贴吧协议及“七条底线”贴吧投诉
                          内  容:
                            查看全部
                          发 表
                          保存至快速回贴

                          发布成功
                          去贴吧APP订阅抽奖结果通知
                          扫码进入贴吧APP
                          ···········
                          开奖后第一时间站内信通知
                          ···········
                          中奖结果全员公示