喝汽水问题
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