问题描述：皇帝决定找出全国中最幸运的一个人，于是从全国选拔出 n 个很幸运的人，让这 n 个人围着圆桌进餐，可是怎么选择出其中最幸运的一个人呢？皇帝决定：从其中一个人从 1 开始报数，按顺序数到第 k 个数的人自动出局，然后下一个人从 1 开始报数，数到 k 的人出局……。如此直到最后只剩下约瑟夫一人，然后他就成为全国最幸运的人。请问约瑟夫最初的位置？(注：原问题略显暴力，故自创此趣味题目)
分析：把第一个开始报 1 的人标定为 1，然后按报数顺序依次标定其余的人为：2，3，……，n - 1，n。按规则进行淘汰，直到最后剩一个数字，这个数字就是约瑟夫的位置。
解决方案：
1. 模拟法（simulation）
数组模拟，时间复杂度最高为 O(n) (当k≈n时 ) ，空间复杂度O(n)
/********** 用数组模拟 *************/
void findNext(bool *out, int n, int &curPosition){
if(!out[curPosition]) {
int pNext = (curPosition + ) % n;
if(!out[pNext])
curPosition = pNext;
else{
curPosition = pNext;
while(out[curPosition])
curPosition = (curPosition + ) % n;
}
}else
{
while(out[curPosition])
curPosition = (curPosition + ) % n;
}
}
int josephus(int n, int k)
{
if(n < || k < ) return -;
if(n == ) return n;
bool *out = new bool[n]; /********* 记录是否出局 *********/
for(int i = ; i < n; ++i)
out[i] = false;
int current = ;
int n2 = n;
while(n2 != )
{
int cnt = k;
while(--cnt)
findNext(out, n, current);
out[current] = true;
findNext(out, n, current);
--n2;
}
delete[] out;
out = NULL;
return (current + );
}
Code
循环链表模拟：时间复杂度O(n)，空间复杂度O(n)
/********** 循环链表 *************/
struct ListNode{
int val;
ListNode * next;
ListNode(int x):val(x), next(NULL) {}
}; int josephus(int n, int k)
{
if(n < 1 || k < 1)
return -1;
if(n == 1) return n;
ListNode *head = new ListNode(1);
ListNode *prior = head;
for(int i = 2; i <= n; ++i)
{
ListNode *tem= new ListNode(i);
prior->next = tem;
prior = prior->next;
}
prior->next = head;
while(head->next != head)
{
int cnt = k;
while(--cnt)
{
head = head->next;
prior = prior->next;
}
prior->next = prior->next->next;
ListNode *current = head;
head = head->next;
delete current; /*** 只释放堆内存空间，局部指针自动回收 ***/
}
return head->val;
}
2.建模法（modeling）
使用队列建模。
/********** 用队列（注：使用STL可简单化） *************/
bool ERROR = false;
typedef int ELEM;
struct Node{
ELEM val;
Node *next;
Node(ELEM e):val(e), next(NULL){}
};
struct queue{
queue():front(NULL), tail(NULL) {}
ELEM pop();
void push(ELEM val);
bool empty();
private:
Node *front;
Node *tail; };
ELEM queue::pop(){
if(front == NULL){
ERROR = true;
return -;
}else{
ELEM v = front->val;
front = front->next;
return v;
}
}
void queue::push(ELEM val){
Node *p = new Node(val);
if(front == NULL)
front = tail = p;
else
{
tail->next = p;
tail = tail->next;
}
}
bool queue::empty(){
if(front == NULL)
return true;
else
return false;
} int josephus(int n, int k)
{
if(n < || k < ) return -;
if(n == ) return ;
queue qu;
for(int i = ; i <= n; ++i)
qu.push(i);
int result = ;
while(!qu.empty())
{
for(int i = ; i <= k-; ++i)
qu.push(qu.pop());
result = qu.pop();
}
return result;
}
Code
3. 数学推理 && 动态规划
初始：0 1 ... (k-2) (k-1) k ... (N-1)
K 出局: 新的顺序：
k 0
... p ...
N-1 映 N - k - 1 P(x) = (x - k + N) mod N
0 射 N - k 令：y = P(x) = (x - k + N) mod N
1 N - k + 1 则，x = (y + k - N) mod N
... ... = (y + k) mod N
k-2 N - 2 P(x) = (x + k) mod N
设 f(N，k) 为最后所得的数字，则：
f(N，k) = P( f(N-1，k) ) = (f(N-1，k) + k) mod N
所以有如下递推公式：
int josephus(int n, int k)
{
if(n < 1 || k < 1) return -1;
if(n == 1) return 1;
int result = 0;
for(int i = 2; i <= n; ++i)
result = (result + k) % i;
return result+1;
}
另外，简洁的递归：（不推荐，递归栈太小，容易溢出）
int josephus(int n, int k)
{
if(n < 1 || k < 1) return -1;
if(n == 1) return 1;
else
return ((josephus(n - 1, k) + k - 1) % n + 1);
}
最后，当 k = 2 时，如下公式可直接求出：
代码为：
int n = 1000;
cout<< 2*(n - pow(2.0, int(log((float)n) / log((float)2))))+1 <<endl;