雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

喝汽水问题

                                                  by flyinghearts

 

1000瓶汽水,喝完后每3个空瓶能换1瓶汽水,问最后最多可以喝几瓶汽水,此时剩余几个空瓶?

 

 

不妨假设,共有n瓶汽水,每a个空瓶能换b瓶汽水(a > b)。刚开始有n瓶汽水,喝完后就有n个空瓶,多喝的汽水是靠空瓶换来的,每进行一次空瓶换汽水,就能多喝b瓶汽水、空瓶数目就减少了a-ba个空瓶换了b瓶汽水,喝完后得到b个空瓶)。

 

(下面 [x] 表示x的整数部分)

1 如果允许从别处(老板或其他顾客处)借空瓶(当然,有借有还)

空瓶换汽水次数:   [n / (a - b)]

最后剩余空瓶:     n % (a - b)

总共可以喝到汽水: n + [n / (a - b)] * b

 

2 不允许借空瓶

 空瓶换汽水过程中,一但空瓶数小于a,则停止交换。

  n < a,显然,空瓶换汽水次数为0,总共可以喝到汽水n瓶,最后剩余空瓶n

  n >= a:(下面提供三种解法)

  解法一    空瓶换汽水次数k等于满足n – (a-b)*t < a的最小非负整数t:

              t > (n-a)/(a-b),最小的t [(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]

              剩余的空瓶数:n – (a-b)*t

= n – (a-b)*([(n-b)/(a-b)])

                           = b + (n-b) - (a-b)*([(n-b)/(a-b)])

= b + (n-b)%(a-b)

 

解法二   先预留a个空瓶,将剩余的n-a个空瓶进行换汽水,换的过程中,若空瓶不够a个,则从预留的a个空瓶中“借”,因而,

空瓶换汽水次数:[(n-a)/(a-b)] + 1 = [(n-b)/(a-b)](预留的a个空瓶也能换一次)

最后剩余空瓶: (n-b) % (a-b) + b(预留的a个空瓶换得b瓶汽水)

 

解法三   最后一次空瓶换汽水得到的b瓶汽水,喝完后得到b个空瓶,因而最后剩余空瓶数必然大于b个,先预留b个空瓶,将剩余的n-b个空瓶进行换汽水,若空瓶不够a个,则从预留的b个空瓶中“借”(由于能进行空瓶换汽水,空瓶数>= a – b,因而“借”完后,可以保证空瓶数大等于a),

           空瓶换汽水次数:[(n-b)/(a-b)]

最终剩余空瓶数:b + (n-b) % (a-b)

 

(对解法三,n>=b时结论成立,对解法一、二,可以验证n >=b时,结论也成立)

 

因而, n >= b

空瓶换汽水次数:   [(n-b)/(a-b)]

最后剩余空瓶:     b + (n-b) % (a-b)

总共可以喝到汽水: n + [(n-b)/(a-b)] * b

 

对原题:

 n = 1000a = 3, b = 1 a – b = 2

 若允许借空瓶    

可以喝到汽水: 1000 + 1000 / 2 = 1500

剩余空瓶:1000 % 2 = 0

 

若不允许借空瓶

可以喝到汽水: 1000 + (1000 - 1) / 2 = 1499

剩余空瓶:     1 + (1000 - 1) % 2 = 2

 

posted on 2011-09-23 19:45 flyinghearts 阅读(2547) 评论(7)  编辑 收藏 引用 所属分类: 算法

评论

# re: 喝汽水问题 2011-09-23 20:16 cheap lace front wigs
呵呵,这个算法相当有意思,学习了  回复  更多评论
  

# re: 喝汽水问题 2011-09-23 20:19 飞舞的烟灰缸
其实这个是小学三年级的奥赛题,我那时候就做过。不过现在重新做这个题目花的时间比小时候还多,唉。  回复  更多评论
  

# re: 喝汽水问题 2011-09-24 01:25 Archen
我就是做了漫画那家伙 我觉得你有点想的过于复杂。
汽水兑换本质上找汽水内容和瓶子的兑换比
由条件可以知道,一空瓶=b/(a-b)汽水
能借的话等于兑换不设条件,所以n瓶汽水=n空瓶+n汽水=n*b/(a-b)汽水+n
不能借的话起码剩一个空瓶,那么n瓶汽水=(n-1)空瓶+n汽水=(n-1)*b/(a-b)+n,结果取整即可  回复  更多评论
  

# re: 喝汽水问题 2011-09-24 09:47 cheap lace front wigs
@Archen 正解!
  回复  更多评论
  

# re: 喝汽水问题 2011-09-24 20:27 flyinghearts
@Archen
不能借的话,最后至少剩下b个空瓶,而不是1个。
你可能没注意到,你我得到的答案都不一样。

利用“饮料和空瓶的价值比”的计算结果,在b>1时可能不正确。

比如说,5个空瓶可以换2瓶汽水,
开始有5瓶水,则无论是否可以借瓶,最多只能喝7瓶汽水
开始有6瓶水,不能借瓶的话,最多只能喝8瓶水。
  回复  更多评论
  

# re: 喝汽水问题 2012-05-21 16:49 啊啊啊
把汽水分成空瓶子和饮料2个部分;
1瓶汽水 = 1个空瓶子(空瓶子) + 1瓶子容量的汽水(饮料)

因为: 3瓶汽水 = 3空瓶子 + 3份饮料 = 1瓶汽水 + 3份饮料
所以: 2瓶汽水 = 3份饮料 即 1瓶汽水 = 1.5份饮料
现有1000瓶汽水,所以可以喝到的饮料是 1.5份饮料X1000瓶汽水 = 1500份饮料

因为最后得出的是整数,所以不用再算了,如果不是整数,则可以退一瓶。
  回复  更多评论
  

# re: 喝汽水问题 2012-05-29 19:56 flyinghearts
@啊啊啊

又一个不认真看帖就回帖的。

先不说 “价值法”是不是正确的,你觉得“列一个方程再推出结果” 与 “不列方程直接得出结果” 哪一种方法更容易理解?

再说下“价值法”,“价值法”要得出正确结果,就必须“耍点无赖”:

1 必须能借到空瓶, 不然 3空瓶换1汽水时,开始有2瓶汽水时,得到的不是正确答案。

2 若6空瓶能换2汽水,则要求 3空瓶一定能换到1汽水,不然在开始有2瓶汽水时,计算得到的不是正确答案。(网上的题目,都是n空瓶能换1汽水,所以不存在这个问题)

在实际兑换中,极有可能这两个条件都不能满足。










  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理