圆环报数程序, 抛砖引玉解决办法

圆环报数程序, 抛砖引玉
n个人围成一圈, 从第一个人从1开始报数。到m时， 第m个退出，m+1从1开始报。

C/C++ code

#include "stdafx.h"#include <stdio.h>#include <stdlib.h>typedef struct NODE{    int iValue;    NODE* prev;    NODE* next;    NODE()    {        iValue = 0;        prev = NULL;        next = NULL;    }} *PNODE;PNODE initList(int n ){    PNODE p = new NODE;    p->iValue = 1;    PNODE ret = p;    for(int i = 1; i< n; i++)    {        PNODE temp = new NODE;        temp->iValue = i + 1;        p->next = temp;        temp->prev = p;        p = temp;    }    p->next = ret;    ret->prev = p;    return ret;}void fun(PNODE p , int m){    if(p == NULL)        return;    if(p->next == p)    {        printf("%d\n", p->iValue);        delete p;        return ;    }    int t = m - 1;    while(t--)    {        p = p->next;    }    p->prev->next = p->next;    p->next->prev = p->prev;    printf("%d\n", p->iValue);    PNODE temp = p->next;    delete p;    fun(temp, m);}void main(){    int n = 15;    PNODE p = initList(15);    fun(p, 4);}

[解决办法]
约瑟夫环问题是一道经典的数据结构题目
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
一般我们采用一个循环队列来模拟约瑟夫环的求解过程，但是如果n比较大的时候，采用模拟的方式求解，需要大量的时间来模拟退出的过程，而且由于需要占用大量的内存空间来模拟队列中的n个人，并不是一个很好的解法。
在大部分情况下，我们仅仅需要知道最后那个人的编号，而不是要来模拟一个这样的过程，在这种情况下，可以考虑是否存在着一种数学公式能够直接求出最后那个人的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
我们先看第一个人出列后的情况，显而易见，第一个出列的人的编号一定是m%n-1,这个人出列后，剩下的n-1个人组成了一个新的约瑟夫环，这个约瑟夫环的第一个人在最开始的环中的编号是k=m%n（就是第一个出列的人的下一个）
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
事实上，可以把这个环又映射成为一个新的环：
k --- 0
k+1 --- 1
k+2 --- 2
... ....
k-2 -- n-1
可以看出，这就是原问题中把n替换成n-1的情况，假设我们已经求出来在这种情况下最后胜利的那个人的编号是x，那个倒推回去的那个人的编号就正好是我们要求的答案，显而易见，这个编号应该是(x+k)%n
那么如何知道n-1个人下面的这个x呢，yes，就是n-2个人情况下得到的x'倒推回去，那么如何知道n-2情况下的x'呢，当然是求n-3个人，这就是一个递归的过程
f(1) = 0（f(1)就是现在还剩下1个人，那么无论m为几，这个人总会出列，因此f(1)=0)
f(n) = (f(n-1)+m)%n
那么我们要求f(n)，就从f(1)倒推回去即可
int f(int n, int m)
{
int r = 0;
for(int i = 2; i <= n; i++)
r = (r + m) % i;
return r + 1; //这是因为日常生活中编号总是从1开始
}
这种方法比模拟的方法快多了，我们在碰到问题的时候，可以想一想是否有数学公式来求解
[解决办法]

C# code

//n可以达到 100亿，k不超过1000的版本，结果从0开始数的。int64 solve(int64 n, int64 k){    if (n == 1 || k == 1) return n - 1;    if (n <= k)    {        int ans = 0;        for (int i = 2; i <= n; ++i) ans = (ans + k) % i;        return ans;    }    int64 leave = n / k;    int64 tans = solve(n - leave, k);    int64 tail = n - leave * k;    if (tans < tail) return leave * k + tans;    tans -= tail;    int64 id = tans / (k - 1);    int64 off = tans % (k - 1);    return id * k + off;} 

 

查看更多 下一篇