14-2 Josephus permutation

We define the Josephus problem as follows. Suppose that \(n\) people form a circle and that we are given a positive integer \(m \le n\). Beginning with a designated first person, we proceed around the circle, removing every \(m\)th person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all \(n\) people. The order in which the people are removed from the circle defines the \((n, m)\)-Josephus permutation of the integers \(1, 2, \ldots, n\). For example, the \((7, 3)\)-Josephus permutation is \(\langle 3, 6, 2, 7, 5, 1, 4 \rangle\).

a. Suppose that \(m\) is a constant. Describe an \(O(n)\)-time algorithm that, given an integer \(n\), outputs the \((n, m)\)-Josephus permutation.

b. Suppose that \(m\) is not a constant. Describe an \(O(n\lg n)\)-time algorithm that, given integers \(n\) and \(m\), outputs the \((n, m)\)-Josephus permutation.

(Removed)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用