江苏龙网

  1. 首页 > 人文 > >

非典型算法题，用程序和电脑玩一个游戏( 二 )


到这里距离解出这道题已经非常接近了 ， 只差临门一脚 ， 但是这里我还是走了弯路 。 我当时的想法是把这些数两两配对 ， 这样就可以确定出其中的一半 。 之后我们再把解不出来的数再进行配对 ， 直到最后只剩下一个数为止 。 后来发现也有反例 ， 比如[1, 3, 2, 4, 5] ， 在这个例子当中1和3配对 ， 2和4配对 ， 5落单 。 我们还是没办法解出来 。
我在这里苦思冥想了很久 ， 后来才发现答案远在天边近在眼前 ， 解法其实非常简单 。 我们只需要从前往后遍历维护一个最大值即可 。 我们假设最大值是id ， 凡是遇到小于id的数 ， 都可以通过它和id取模的结果求出来 。 如果遇到了比id更大的数 ， 同样可以通过取模的结果求出id 。 所以到最后的时候 ， 我们可以求出除了最大值其他的所有数 ， 这个剩下的数就是n 。
想通了真的非常非常简单 ， 说穿了一钱不值 ， 但是要靠自己想明白还是不太容易的 。 并且这道题的题目形式也很新颖 ， 非常非常有趣 ， 适合在周末一玩 。
最后 ， 我们来看代码：
import sysdef guess(x, y):print('? {} {}'.format(x, y))# 输出之后需要flush一下 ， 防止影响输入sys.stdout.flush()st = input()return int(st)st = input()n = int(st)num = [-1 for _ in range(n+2)]# 一开始将最大值的下标设为1idx = 1for i in range(2, n+1):x = guess(idx, i)y = guess(i, idx)# 说明遇到了更大的数 ， 那么x就是之前的最大值if x > y:num[idx] = xidx = i# 否则求出来的就是ielse:num[i] = ynum[idx] = nprint('! {}'.format(' '.join(map(str, num[1:n+1]))))今天的问题到这里就结束了 ， 衷心祝愿大家每天都有所收获 。 如果还喜欢今天的内容的话 ， 请来一个三连支持吧~（点赞、关注、转发）
- END -
本文始发于公众号：TechFlow ， 求个关注


推荐阅读


上一篇：小米若出mini版，恐被喷

下一篇：自定义Github个人首页