网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
2ch吧 关注：528,878贴子：15,172,799

关于20瓶水最少花多少钱那个问题

只看楼主收藏回复

这个问题可以简单使用计算机算法设计中的greedy algorithm来达到最优解
我发现很多人一来就用“直接买xx瓶”来开头 按照贪婪算法的逻辑 这个问题显然一瓶一瓶买入才是最优解 每买一瓶就要检查是否可以进行兑换 所以只需要理清逻辑关系即可轻易得出答案 楼下放出python源代码以及两个问题的运行结果
IP属地:加拿大来自iPhone客户端1楼2016-05-25 09:35回复
    IP属地:加拿大来自iPhone客户端2楼2016-05-25 09:35
    收起回复
      设水为X，瓶子为Y，瓶盖为Z
      那么根据条件有 4Z=X+Y+Z
      2Y=X+Y+Z
      现在需要20X，已知X+Y+Z=2
      那么思路就简单了，X=0.5,Y=1,Z=0.5
      20个X 也就是0.5*20=10元
      怎么实现呢？很简单
      10元买5瓶水
      然后借15瓶水
      喝完水后用20个空瓶子换10瓶水
      用20个瓶盖换5瓶水
      把换得来的15瓶水还给人家。
      我喜欢这种简单粗暴的解法。
      IP属地:广西3楼2016-05-25 09:59
      收起回复
        话说有人会将代码中用瓶盖数量除以4或者空瓶子数量除以2来算兑换多少瓶水，那样计算出来10元可喝15瓶，这里面有一个逻辑漏洞，因为整个过程会出现瓶盖数以及空瓶数量为奇数的情况，这个时候用除法计算在数学中可行但是现实生活运用是不行的 因为你不可能兑换x.5瓶水出来 兑换的必然是整数。
        IP属地:加拿大来自iPhone客户端4楼2016-05-25 10:43
        收起回复
          这种逻辑问题还是丢给程序员啦(指
          IP属地:浙江来自Android客户端5楼2016-05-25 11:03
          回复
            额刚刚又想了下发现了不对劲的地方 第二题的贪婪算法应该是尽量买最多的啤酒 因此一开始就应该把10元花光来计算最多可以兑换多少瓶才对 重新算了是15瓶水没错 附上改进后的代码
            IP属地:加拿大来自iPhone客户端6楼2016-05-25 11:20
            回复
              IP属地:加拿大8楼2016-05-25 11:21
              回复
                可以借盖和瓶的话是12块，不可以借就是14块
                来自Android客户端9楼2016-05-25 19:37
                收起回复
                  用什么穷举，用等比数列方程做
                  IP属地:浙江来自Android客户端12楼2016-05-26 08:25
                  回复
                    首项为1，公比0.75，前n项和等于4，每一瓶水的价值实际上是4瓶，5瓶能买20瓶
                    IP属地:天津来自Android客户端13楼2016-05-26 08:48
                    回复
                      这就让我想起以前有个人买冰红茶连中四个再来一瓶，然后勉强抱着4瓶没瓶盖的冰红茶颤颤悠悠回寝室了，您们就想着拿瓶盖换瓶子，最后您们拿这些没瓶盖的水怎么办
                      IP属地:北京来自iPhone客户端14楼2016-05-26 08:50
                      收起回复
                        25瓶
                        IP属地:江西来自Android客户端15楼2016-05-26 11:17
                        回复
                          所以说你们这些图样都是站在老板面前一边喝一边换直到喝了20瓶么，小心糖尿病
                          IP属地:广东16楼2016-05-26 11:41
                          回复
                            20瓶康师傅要20块
                            IP属地:江苏来自Android客户端17楼2016-05-26 14:20
                            回复

                              扫二维码下载贴吧客户端

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

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