python 饥饿的小易(网易笔试题)

2018-08-13 07:48:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

本周早些时候,学弟给我发了一道网易的笔试题,饥饿的小易,感觉有点意思~分享给大家

 

题目描述:

小易总是感觉饥饿,所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x_0。对于小易所处的当前位置x,他只能通过神秘的力量移动到 4 * x + 3或者c。因为使用神秘力量要耗费太多体力,所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如:位置0,位置1,000,000,007,位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

 

输入:

输入一个初始位置x_0,范围在1到1,000,000,006

 

输出:

输出小易最少需要使用神秘力量的次数,如果使用次数使用完还没找到贝壳,则输出-1

 

乍一看这道题,是有点懵逼的,如果用暴力法来做100%超时。以我的经验来看估计这是一道数学问题,我们就分析一下题目描述中的关键信息吧,看看有没有什么玄机。小章鱼只能移动到4 * x + 3或者8 * x + 7,那我们认为f(x)=4 * x + 3, g(x)=8 * x + 7。关键部分到了,我瞪俩眼睛观察了好久,终于发现

1. f(g(x)) = g(f(x))  我们可以认为最终小章鱼的移动路线是可以用fg表示的字符串,而且fg可以随意调换位置~所以说腻,ffggffgf=fffffggg

2. f(f(f(x)))=g(g(x)) 也就是说,每做3次f移动等于2次g移动,那么我们可以将结果的fg串中每3个f换成2个g,那么结果的fg串是一个最多包含2个f的fg串~所以说腻,fffffggg=ffggggg

现在解题思路就很清晰了,以0,f,ff为起始位置,每次都移动g,看什么时候能移动到能被1000000007整除的位置。代码如下:

#!/usr/bin/python
# -*- coding: utf-8 -*-


def get_result(n):
    l_ = [n, n * 4 + 3, 16 * n + 15]
    for j, m in enumerate(l_):
        for i in range(100000):
            m = (8 * m + 7) % 1000000007
            if m == 0:
                return i+j+1
    return -1

if __name__ == '__main__':
    n = input()
    print get_result(n)

 

好啦,这道题到此已经完美解决啦~

希望对大家有所帮助~

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Python基础语法(一)

下一篇:Python可编程红外USB适配器!Python还真是无所不能!