标签 数论 下的文章
约瑟夫问题的一些解法
约瑟夫问题:
有n个人,编号为$1..n$,从第1个人开始报数,报到m的人离开,求最后的幸存者。
算法1(Simple算法):
用队列模拟,可以算出每一次出队的人。
时间复杂度$O(nm)$
当n很小而m很大时,可以通过取膜将$O(nm)$优化为$O(n^2)$
有n个人,编号为$1..n$,从第1个人开始报数,报到m的人离开,求最后的幸存者。
用队列模拟,可以算出每一次出队的人。
时间复杂度$O(nm)$
当n很小而m很大时,可以通过取膜将$O(nm)$优化为$O(n^2)$