可爱的幸运羔羊

Question

我正试图从google的foobar中解决这个问题。然而，我的代码超过了时间限制，即使当我测试它时，我得到了正确的答案。如何使我的代码更高效？

可爱的幸运羔羊是一个追随者，并不是所有的苦差事。偶尔，当兰布达指挥官感到慷慨时，她会分发幸运羔羊(兰伯达的万能金钱雄鹿)。追随者可以用幸运的羊羔买第二双袜子，枕头作为他们的铺位，甚至第三天的饭！然而，实际上分发羊羔并不容易。每个追随者队伍都有一个严格的资历等级，这必须得到尊重--否则，这些追随者会反抗，你们都会再次被降职为奴才！为了避免叛乱，你必须遵守四条关键规则: 1.最低级的追随者(资历最少的)只有一只羔羊。(队里总会有至少一名追随者) 2.如果排在他们前面的人得到的羔羊数量是他们的两倍以上，那么一个追随者就会反抗。3.如果给下两个下属的羔羊加起来的数量超过了他们得到的羔羊的数量，那么一个亲信就会反抗。(请注意，两个最低级的追随者不会有两个下属，所以这条规则不适用于他们。4.你总能找到更多的仆人--指挥官有很多雇员。如果剩下足够多的羔羊，那么在遵守其他规则的同时，还可以增加另一个亲信为最高级的，那么你就必须不断地增加并付钱给那个亲信。请注意，您可能无法分发所有的羔羊。一只羔羊不能再细分。也就是说，所有的追随者都必须得到一个正整数的羔羊数。编写一个名为“答案”( total_lambs )的函数，其中total_lambs是要除以的讲义中羊羔的整数。它应该返回一个整数，表示能够分享羊羔的最小和最大数目的区别(也就是说，尽可能慷慨地对待你付出的人和尽可能吝啬的人)，同时仍然遵守上述所有规则以避免叛乱。例如，如果你有10只羔羊，并且尽可能慷慨的话，你只能支付3只追随者(1，2，4只羔羊，按等级排列)，而如果你吝啬的话，你可以付给4名追随者(1，1，2和3只羔羊)。因此，答案(10 )应该返回4-3 = 1。为了保持趣味性，Lambda指挥官改变了幸运羔羊支付的大小:您可以期望total_lambs总是在100亿到10亿之间( 10 ^ 9)。提供solution.py解决方案的语言，编辑solution.java解决方案，编辑solution.java测试用例输入：(int) total_lambs = 10输出：(int) 1输入：(int) total_lambs =143个输出：(int) 3使用验证文件测试解决方案，看看它是如何实现的。编辑完代码后，使用submit 文件提交答案。如果您的解决方案通过测试用例，它将从您的主文件夹中删除。

def answer(lambs):
    totals = [generous(lambs), stingy(lambs)]
    difference = max(totals) - min(totals)
    return difference

def generous(lambs):
    num = 1
    while True:
        total = 2**(num) - 1
        if total <= lambs:
            num += 1
        else:
            num -= 1
            break
    return num

def stingy(lambs):
    num = 1
    while True:
        total = (fibonacci(num + 2) - 1)
        if total <= lambs:
            num += 1
        else:
            num -= 1
            break
    return num

def fibonacci(num):
    if num > -1 and num < 3:
        return 1
    else:
        num = fibonacci(num - 1) + fibonacci(num - 2)
        return num

Answer 1

在@Zeta优秀答案的基础上，如果将fibonacci转换为生成器，则只需在stingy中的每个项加和，并在之和大于羊羔数量时停止。钱的数目是你可以雇佣的仆从的数目。要有效地这样做，您可以使用itertools.accumulate。

您还在重新发明generous中的车轮，因为您正在计算的是一个基本的2对数。

最后，很明显，吝啬的策略会给你更多的追随者，而不是慷慨的。所以这里不需要min和max。但是，即使您想要确定，也宁愿使用abs。

拟议改进：

from math import log2
from itertools import accumulate


def answer(lambs):
    return stingy(lambs) - generous(lambs)


def generous(lambs):
    return int(log2(lambs + 1))


def stingy(lambs):
    for henchmen, total_pay in enumerate(accumulate(fibonacci())):
        if total_pay > lambs:
            return henchmen


def fibonacci():
    a, b = 1, 1
    while True:
        yield a
        a, b = b, a + b