今天面试问到一个算法: 一个汽水是 $1, 两个汽水的 空瓶 换一瓶可乐, 请问给一些钱, 最多能喝几瓶呢?
当时思路有些乱, 算法没写清楚, 面试结束去个奶茶店, 重新写了一下.
英文的描述:
A bottle of Coke is $1. You can exchange two empty bottles for a bottle of Coke. You have $20 now in your pocket. So how many bottles of Coke can you drink at most?
1. 模拟喝汽水的过程.
当时写算法的时候, 面试官很看重的是可读性, 例如变量名的定义.
作为一个 Python 程序员, 我以后也在这方面也要更加注意.
1 | def cal_drinks(n): |
2. 递归
写递归最重要的就是找到那个推倒式.
1 | # n 个空瓶: f(n) = n/2 + f(n/2 + n%2) |
3: ???
就是为什么结果是 n + (n-1), 是因为这个推导式有什么简化的方法吗?
最后献上一张奶茶图留念: