约瑟夫环-两种兑现方法，两种时间复杂度

约瑟夫环-两种实现方法，两种时间复杂度

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为r的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求最后出列的人的编号。

第一种方法就是使用循环链表的方法，因为这种方法在删除一个节点后，对于其他节点的位置改动不用太大。这是一种很浪费时间的方法，每次都删除第m个数字（注意题意包含摸的概念），也就是说，每次删除，都要用O(m)的时间，一共有n个数字，想要剩下一个，其余都要删除，那么就得用(n-1)*O(m)的时间，故算法的时间复杂度为O(mn).下面贴上两种代码的实现，分别为c和c++，之后给出另一种时间复杂度的算法。

c:

#include<iostream>#include<list>using namespace std;int get_last_num(int n, int m){int last_num = 0;for(int i = 2; i <= n; i++)last_num = (last_num + m) % i;return last_num;}void main() {int result = get_last_num(9, 5);cout << result << endl;}