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

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

HDOJ-2552 三足鼎立——数学不是白学的

描述

MCA 山中人才辈出,洞悉外界战火纷纷,山中各路豪杰决定出山拯救百姓于水火,曾以题数扫全场的威士忌,曾经高数九十九的天外来客,曾以一剑铸十年的亦纷菲,歃血为盟,盘踞全国各个要塞(简称全国赛)遇敌杀敌,遇佛杀佛,终于击退辽军,暂时平定外患,三人位置也处于稳态。

可惜辽誓不甘心,辽国征南大将军<耶律 javac++>欲找出三人所在逐个击破,现在他发现威士忌的位置 s,天外来客的位置 u,不过很难探查到亦纷菲 v 所在何处,只能知道三人满足关系:

arctan(1 / s) = arctan(1 / u) + arctan(1 / v)

定义 f(s,u,v)=v*u-s*u-s*v 的值为”三足鼎立”

<耶律 javac++>想计算<三足鼎立>的值

输入

首先输入一个 t,表示有 t 组数据,跟着 t 行:

输入 s, u(s <= 12^3; u <= 2^20; s, u, v > 0), s, u, v 均为实数

输出

输出 v * u – s * u – s * v 的值,为了简单起见,如果是小数,直接取整

比如:答案是 1.7,则输出 1。

分析

第一感觉,这题一定是个纯模拟,反正 arctan 是可以算的。

不过,仔细想过之后发现,这个题反而是用 arctan 好好的骗了我们一把——当你看到 f(s,u,v) = v * u – s * u – s * v 的时候是不是反映到了 tan 的运算法则呢?

所以,我觉得这是一道数学题。

运算

中等数学告诉我们

tan(a + b) = (tan(a) + tan(b)) / (1 – tan(a) * tan(b)) (1)

tan(arctan(a)) = a (2)

有了以上两个基本准则,我们针对 arctan(1 / s) = arctan(1 / u) + arctan(1 / v)进行推导:

tan(arctan(1 / s)) = tan(arctan(1 / u) + arctan(1 / v))

1 / s=(1 / u + 1 / v) / (1 – 1 / u * v)

1 / s – 1 / s * u * v = 1 / u + 1 / v

v * u – s * u – s * v = 1

所以,我们居然推导出了这道题的结果直接为1!数感拯救世界!

代码