本文简述了骑士金币问题的两种实现方法

首先我们来看下什么是 骑士金币问题:

骑士金币问题

国王要用金币赏赐忠于他的骑士.骑士在就职的第一天得到一枚金币,接下来的两天(第二天和第三天)每天会得到两枚金币,接下来的三天(第四、五、六天)每天会得到三枚金币,接下来的四天(第七、八、九、十天)每天会得到四枚金币,这样的赏赐形式会一直持续下去,问题是给定一个天数(譬如第十天),求骑士将会获得的总的金币数量.

举个简单的例子,如果给定第十天( N N N = 10),那么骑士将会获得的总的金币数量( C C C)为:

C = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 1 + 2 2 + 3 2 + 4 2 = 30 C = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 1 + 2^2 + 3^2 + 4 ^ 2 = 30 C=1+2+2+3+3+3+4+4+4+4=1+22+32+42=30

按照题意,我们直接以连续获得相同金币的天数为循环量来累加金币,当然还需要处理一下最后一轮循环天数不足的情况,代码大概是这个样子(Lua)

function golden_coins(target_days)
    local coins = 0
    local cur_coin = 1
    local days = 0
    
    while days + cur_coin <= target_days do
        coins = coins + cur_coin * cur_coin
        days = days + cur_coin
        cur_coin = cur_coin + 1
    end
    
    local remaining_days = target_days - days 
    coins = coins + cur_coin * remaining_days
    
    return coins
end

该实现方法的时间复杂度为 O ( N ) O(\sqrt{N}) O(N ​)

我们也可以直接使用公式来进行求解,主要是要了解以下两个公式:

S 1 = 1 + 2 + 3 + . . . + N = N ( N + 1 ) 2 S 2 = 1 2 + 2 2 + 3 2 + . . . + N 2 = N ( N + 1 ) ( 2 N + 1 ) 6 S1 = 1 + 2 + 3 + ... + N = \frac{N(N + 1)}{2} \\ S2 = 1^2 + 2^2 + 3^2 + ... + N^2 = \frac{N(N + 1)(2N + 1)}{6} S1=1+2+3+...+N=2N(N+1)​S2=12+22+32+...+N2=6N(N+1)(2N+1)​

骑士金币问题可以认为是已知 S 1 S1 S1 的数值,来求解 S 2 S2 S2 的数值(当然,仍然要处理一下最后一轮循环天数不足的情况),代码大概是这个样子:

function golden_coins_v2(target_days)
    local sq_days = math.floor(0.5 * (-1 + math.sqrt(1 + 8 * target_days)))
    local coins = (sq_days * (sq_days + 1) * (2 * sq_days + 1)) / 6
    local remaining_days = target_days - sq_days * (sq_days + 1) * 0.5
    coins = coins + (sq_days + 1) * remaining_days
    return coins
end

该实现的时间复杂度为 O ( 1 ) O(1) O(1)