约瑟夫环问题的模拟和递归方法
Description
成都信息工程学院又要发年终大奖了!这次获大奖的人从n名会员中按以下规则选出:首先,让会员们围成一个大圈,按 0, 1, 2, …, n – 1编号.然后,随机抽取一个数 m,让编号为 0 的会员开始报数.每次喊到 m 的那个会员出列,不再回到圈中,从他的下一个人开始,继续 1, …, m 报数.这样下去,直到剩下最后一个会员为止.这名会员就能获得大奖了.输入格式输入有多组数据.每组数据一行,包含 2 个整数 n(1 <= n <= 100,000), m(1 <= m <= 100,000). n, m 分别表示会员的人数(编号 0, 1, 2, …, n – 1)和数 m(如上文所述).输出对应每组数据,输出最后拿到大奖的会员编号.
1. Linked List(Simulation)
使用链表进行模拟，空间复杂度 O(n)，时间复杂度 O(mn)，代码如下：
int josephRingLinkedList(int n, int m) {
int i = 0;
list<int> integers;
for(i = 0; i < n; ++i) {
integers.push_back(i);
}
list<int>::iterator currentInteger = integers.begin();
while (integers.size() > 1) {
for (int i = 1; i < m; ++i) {
currentInteger++;
if (currentInteger == integers.end()) {
currentInteger = integers.begin();
}
}
currentInteger++;
list<int>::iterator nextInteger = currentInteger;
if (nextInteger == integers.end()) {
nextInteger = integers.begin();
}
currentInteger--;
integers.erase(currentInteger);
currentInteger = nextInteger;
}
return *(currentInteger);
}
2. Math Problem(Recursive)
把这个序列的 n 个元素记为 0, 1, 2, 3, …, n – 1。把一个 m 与 n 的组合得到的结果记为 f(n, m)。
假定第一次去掉的元素为 k，k的值为 (m – 1) % n，则去掉之后，序列剩余元素为0, 1, …, k + 1, k + 2, …, n – 1。顺序地，序列事实上变换为了k + 1, k + 2, …, n – 1, 0, 1, …, k – 1。这时候，这个序列的结果还是函数 f 吗？由于排列的顺序发生了变化，同时 n 减掉了 1，我们把这个结果记为 g(n – 1, m)。但是，第二个排列是第一个排列计算中的一个过程，所以结果应该是相同的，即：
f(n, m) = g(n – 1, m)
这时我们只需要寻找 g(n – 1, m) 与 f(n – 1, m) 建立联系，即可得到 f 的递归法则。它们的不同其实是元素的排列起始点不同，由于它们都是连续的，则只要找到两个排列之间的偏移量即可。将两个排列的顺序列举如下：
0 -> k + 1
1 -> k + 2
…
n – k – 2 -> n – 1
n – k – 1 -> 0
…
n – 2 -> k – 1
可以看出，右侧的结果是左侧加上 k + 1 再对 n 取余的结果。所以，对于 f 和 g 有：
f(n, m) = g(n – 1, m) = (f(n – 1, m) + k + 1)%n
显然，对于 n = 1 的情况，最后一定剩下的是元素 0。到这里我们可以得到 f(n, m)的递归公式：
对于 n > 1 f(n, m) = (f(n – 1, m) + k + 1) % n
对于 n = 1 f(n, m) = 0
这种递归的空间复杂度为 O(1)，时间复杂度为 O(n)，代码如下：
int josephRingRecursive(int n, int m) {
int lastInteger = 0;
for (int i = 2; i <= n; ++i) {
lastInteger = (lastInteger + m) % i;
}
return lastInteger;
}
发表评论