JavaScript电影购票成本计算函数超时优化求助

问题背景 #

我的朋友约翰有两种电影购票方案可选：

• System A：每次购买一张票价为ticket的门票，n次的总花费为 n * ticket
• System B：先花费card金额购买会员卡，后续每次购票的价格是上一次的perc倍，n次的总花费为 card + ticket*perc + ticket*perc² + ... + ticket*percⁿ

需要实现movie(card, ticket, perc)函数，返回最小的整数n，使得 ceil(System B总花费) < n*ticket。

示例：

• movie(500, 15, 0.9) 返回43
• movie(100, 10, 0.95) 返回24

原代码的问题 #

你提供的代码执行超时，核心原因是频繁调用Math.pow——这个方法的计算开销并不低，而且每次循环都要计算幂次，随着循环次数增加，累积的耗时会导致超时。

原代码：

function movie(card, ticket, perc) {
 var WithTicketPrice = 0;
 var WithCardPrice = card+ticket*perc;
 var Counter = 1;
 while (WithTicketPrice <= Math.ceil(WithCardPrice)) {
 WithTicketPrice = WithTicketPrice + ticket;
 WithCardPrice = WithCardPrice + (ticket*Math.pow(perc, Counter)*perc);
 Counter++;
 }
 return Counter-1;
};

优化方案 #

我们可以通过递推记录当前优惠票价的方式，完全避免Math.pow的调用，同时简化循环内的计算逻辑，大幅提升效率：

function movie(card, ticket, perc) {
    let systemA = 0;
    let systemB = card;
    let currentDiscountedTicket = ticket * perc;
    let n = 0;
    
    // 循环直到System B的ceil花费小于System A的花费
    while (Math.ceil(systemB) >= systemA) {
        n++;
        systemA += ticket;          // System A累加单次票价
        systemB += currentDiscountedTicket; // System B累加当前优惠票价
        currentDiscountedTicket *= perc;    // 更新下一次的优惠票价
    }
    
    return n;
}

优化逻辑说明 #

1. 避免幂次计算：用currentDiscountedTicket变量跟踪当前的优惠票价，每次只需要乘以perc就能得到下一次的价格，完全替代了Math.pow的开销
2. 简化累加逻辑：systemA直接每次加ticket，相当于直接计算n*ticket；systemB从会员卡费用开始，每次累加当前的优惠票价，计算更直观高效
3. 循环条件精准：每次循环先递增n，再更新花费，确保判断的是第n次购票后的花费对比，完全符合问题要求

额外优化思路：数学公式法 #

如果遇到循环次数极大的场景，还可以用等比数列求和公式直接计算System B的总花费，再通过二分查找找到最小的n：
System B的总花费（n次购票）为：
card + ticket*perc*(1 - percⁿ)/(1 - perc)（当perc ≠ 1时）

不过这种方法需要处理浮点数精度问题，且在大多数场景下，上面的递推循环已经足够高效，不会出现超时问题。

内容的提问来源于stack exchange，提问作者RedruM