喝汽水問題

                                                  by flyinghearts

有1000瓶汽水，喝完后每3個(gè)空瓶能換1瓶汽水，問最后最多可以喝幾瓶汽水，此時(shí)剩余幾個(gè)空瓶？

不妨假設(shè)，共有n瓶汽水，每a個(gè)空瓶能換b瓶汽水（a > b）。剛開始有n瓶汽水，喝完后就有n個(gè)空瓶，多喝的汽水是靠空瓶換來的，每進(jìn)行一次空瓶換汽水，就能多喝b瓶汽水、空瓶數(shù)目就減少了a-b個(gè)（a個(gè)空瓶換了b瓶汽水，喝完后得到b個(gè)空瓶）。

(下面用 [x] 表示x的整數(shù)部分)

1 如果允許從別處（老板或其他顧客處）借空瓶（當(dāng)然，有借有還）

空瓶換汽水次數(shù)：   [n / (a - b)]

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

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

2 不允許借空瓶

 空瓶換汽水過程中，一但空瓶數(shù)小于a，則停止交換。

 對(duì) n < a，顯然，空瓶換汽水次數(shù)為0，總共可以喝到汽水n瓶，最后剩余空瓶n個(gè)

 對(duì) n >= a：（下面提供三種解法）

  解法一    空瓶換汽水次數(shù)k等于滿足n – (a-b)*t < a的最小非負(fù)整數(shù)t:

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

              剩余的空瓶數(shù)：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)

解法二   先預(yù)留a個(gè)空瓶，將剩余的n-a個(gè)空瓶進(jìn)行換汽水，換的過程中，若空瓶不夠a個(gè)，則從預(yù)留的a個(gè)空瓶中“借”，因而，

空瓶換汽水次數(shù)：[(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]（預(yù)留的a個(gè)空瓶也能換一次）

最后剩余空瓶： (n-b) % (a-b) + b（預(yù)留的a個(gè)空瓶換得b瓶汽水）

解法三   最后一次空瓶換汽水得到的b瓶汽水，喝完后得到b個(gè)空瓶，因而最后剩余空瓶數(shù)必然大于b個(gè)，先預(yù)留b個(gè)空瓶，將剩余的n-b個(gè)空瓶進(jìn)行換汽水，若空瓶不夠a個(gè)，則從預(yù)留的b個(gè)空瓶中“借”（由于能進(jìn)行空瓶換汽水，空瓶數(shù)>= a – b，因而“借”完后，可以保證空瓶數(shù)大等于a），

           空瓶換汽水次數(shù)：[(n-b)/(a-b)]，

最終剩余空瓶數(shù)：b + (n-b) % (a-b)

（對(duì)解法三，n>=b時(shí)結(jié)論成立，對(duì)解法一、二，可以驗(yàn)證n >=b時(shí)，結(jié)論也成立）

因而，對(duì) n >= b

空瓶換汽水次數(shù)：   [(n-b)/(a-b)]

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

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

對(duì)原題：

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

 若允許借空瓶    

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

剩余空瓶：1000 % 2 = 0

若不允許借空瓶

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

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