Sweet Snippet 之骑士金币问题

用户2615200

发布于 2021-12-06 11:21:06

4590

发布于 2021-12-06 11:21:06

文章被收录于专栏：tkokof 的技术,小趣及杂念

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

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

骑士金币问题

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

举个简单的例子,如果给定第十天( N = 10),那么骑士将会获得的总的金币数量( C ）为 C = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 1 + 2^2 + 3^2 + 4 ^ 2 = 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(\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 的数值(当然,仍然要处理一下最后一轮循环天数不足的情况),代码大概是这个样子:

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)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/10/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

lua

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

lua

登录后参与评论

0 条评论

热度