喝汽水問題
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