8.31 顺丰笔试题（猜测序列题解）
顺丰的运筹优化工程师岗位，2道题，代码量极小。想明白原理后很容易A。
第一题：幸运数
小昱非常喜欢5这个数字，如果一个数在十进制表示下数字5出现了不少于5次，则是一个幸运数。例如，55555、152****55565就是幸运数；而5、123则不是幸运数。小昱想知道大于N的最小的幸运数是多少。
解法：看到这题懒得多想，暴力硬解即可。很明显最坏的复杂度只有10万。比如输入 155555，我需要遍历到 255555 。因此，必不可能超时。
n = int(input()) + 1
while str(n).count('5') < 5:
n += 1
print(n) 第二题：猜测序列
小明有一个由1到n的整数组成的排列，他让你来猜出这个排列是什么。你每次可以猜测某一位置的数字，小明会告诉你所猜测的数是“大了”、“小了”或是“正确”。你想知道你在最坏情况下，需要猜测几次，才能在排列的所有位置都得到小明“正确”的回复？
这题其实看懂题难度大于写代码难度，解法想明白之后很好写。就拿样例输入 5， 输出 11 为例分析一下：
- 首先，我猜第一个位置的数。它有 5 种可能性，采用二分猜测的方法，最坏情况下要猜 3 次、
- 然后，第二个位置的数只剩下 4 种可能性，但最坏情况下依然要猜 3 次。
- 第三个位置，只剩下 3 种可能性了，因此在 2 次之内一定能猜出来。
- 同理，第四、第五个位置分别需要 2、1 次。总次数为 3+3+2+2+1 = 11
总结一下规律，对于有 k 种可能性的数字，最坏时需要次 。我们需要求的是。其中，对于所有 ，均有。
代码实现：使用循环，先把 1 到 2^p - 1 的f值求和，再加上 2^p 到 n 的f值即可 。复杂度为 O(log n)。
import math n = int(input()) ans = 0 p = math.floor(math.log(n, 2)) for i in range(p): ans += (i + 1) * math.pow(2, i) ans += (p + 1) * (n + 1 - math.pow(2, p)) print(int(ans))
类似资料：