约瑟夫环问题的模拟和递归方法

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),代码如下:

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),代码如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注