一道网易Python招聘会的考题, 领略大企业的雄风!

image

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

题目描述：

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置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

image

输出：

输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-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整除的位置。python代码如下：

image

好啦，这道题到此已经完美解决啦～

希望对大家有所帮助～

image