滑雪租借难题：一个巧妙的随机算法

本文探讨了经典的滑雪租借问题，该问题在算法领域中属于在线算法的范畴。问题描述如下：滑雪者不知道自己会滑雪几天，租借一天滑雪板花费1个单位，购买滑雪板花费B个单位。文章首先介绍了离线算法的最优解，然后分析了一个简单的在线算法，其竞争比为2。更重要的是，文章深入探讨了一个随机算法，该算法利用连续概率分布逼近离散问题，最终得到了约等于e/(e-1)的期望竞争比，显著优于简单的在线算法。尽管该算法在现实生活中应用有限，但对于需要多次进行类似决策的情况，它提供了一种理论上的最优策略。