Sweet Snippet 之 骑士金币问题

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

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

骑士金币问题

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

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

• 循环实现

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

代码语言：javascript复制

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(sqrt{N})

• 公式实现

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

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 的数值,来求解 S2 的数值(当然,仍然要处理一下最后一轮循环天数不足的情况),代码大概是这个样子:

代码语言：javascript复制

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)

lua

0 人点赞