喝汽水問題
by flyinghearts
有1000瓶汽水，喝完后每3個空瓶能換1瓶汽水，問最后最多可以喝幾瓶汽水，此時剩余幾個空瓶？
不妨假設，共有n瓶汽水，每a個空瓶能換b瓶汽水（a > b）。剛開始有n瓶汽水，喝完后就有n個空瓶，多喝的汽水是靠空瓶換來的，每進行一次空瓶換汽水，就能多喝b瓶汽水、空瓶數目就減少了a-b個（a個空瓶換了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 = 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