欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

笔试题-饥饿的小易

程序员文章站 2022-06-09 11:03:36
...

一道网易的笔试题,很有意思,需要通过观察之后利用数学方法解出。

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

分析题目中的信息:
小章鱼只能移动到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整除的位置。

>>> def hungry(n):
...     location = [n,4*n+3,16*n+15]
...     for i,x in enumerate(location):
...         for j in range(100000):
...             x = (8*x+7)%1000000007
...             if x==0:
...                 return i+j+1
...     return -1
... 
>>> hungry(1)
-1
>>> hungry(125000000)
1
相关标签: 笔试