有2*k个人，围成一圈，问，最小的m（从1到m报数，数到m的人离开队列），使得编号k+1到2*k的人先出队列。

我用单向循环链表来做，不过发现数据大于10的时候速度很慢，我不知道如何优化，

题目原题http://。

我的代码如下：



#include <iostream>
using namespace std;


typedef struct node{
    int number;
    bool exit;
    struct node* next;
}node,*pnode;


int main(){
   
    node head;
    head.number=1;
    head.exit=true;
    head.next=NULL;

   
    node* p=NULL;
    p=&head;
    node* q=NULL;
   
    int k;
    int i;
    int m;
    int count;
   
   
    while(cin>>k){

        if (k==0)return 0;

        for (i=0;i<2*k-1;i++)
        {
            q=new node;
            q->number=i+2;
            q->exit=true;
            q->next=NULL;
            p->next=q;
            p=q;
            
        }
        p->next=&head;

        for (m=1;m<2504884;m++)//0x7fffffff
        {
            for (i=0;i<2*k;i++)
            {
                p->exit=true;
                p=p->next;
            }
            p=&head;
            i=1;
            count=0;
            while(1){
                if (i <= m)
                {
                    if (p->exit==true)
                    {
                        if (i==m)
                        {
                            int fsdfsd=p->number;
                            if (p->number <= k)break;
                            else
                            {
                                count++;
                                p->exit=false;
                                if (count==k)
                                {
                                    goto showm;
                                }
                            }   
                        } //if(i==m)
                        p=p->next;
                        i++;
                    }
                    else
                    {
                        p=p->next;
                    }
                }
                else
                {
                    i=1;
                }   
            }//while(1)
        }//m=0;m<10000;m++
showm:
        cout<<m<<endl;

        p=&head;
        for (i=0;i<2*k;i++)
        {
            p->number=0;
            p->exit=false;
            p=p->next;
        }
        
    }
    return 0;
}

核心思想
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 　　为了讨论方便，先把问题稍微改变一下，并不影响原意： 　　问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出 　　，剩下的人继续从0开始报数。求胜利者的编号。 　　我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的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-3 --> n-3 　　k-2 --> n-2 　　序列1： 1, 2, 3, 4, …, n-2, n-1, n 　　序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n 　　序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1 　　序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1 　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来： 　　∵ k=m%n; 　　∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n 　　∴x'= (x+ m%n)%n = (x+m)%n 　　得到 x‘=(x+m)%n 　　如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
http://baike.baidu.com/view/717633.htm

其实还有比楼上更快的数学方法，可我只有资料没研究过。

[ 本帖最后由 卧龙孔明 于 2011-2-19 18:30 编辑 ]

发上来看一看，是不是利用位运算，或者不需要求余的加减算法.

点线面的方法确实是最经典的“数学原理”法。但，如果就是需要模拟出圈的过程，而且还要记载（或输出）出圈人的顺序，那么就得使用“程序模拟”法了。
不过，楼主用链表解决这个问题实在有些让人感觉“蛋疼”；链表中节点的删除是需要时间的啊。这里我给大家另外一种解决方案，核心思想是：用数组模拟链表，所谓的“假链表”。（不过确实是链表的概念）
先讨论所使用的数据结构：
int man[N];//这里，N的值是原来圈内的人数；man数组的每个元素表示一个在圈内的人，那么，man[i](0<=i<N)的下标+1正好是这个人在圈内的编号；
关键问题是，令man[i]的值为“链域”，也就是所谓的“指针”，其实是下一个人的下标值。这可以通过循环：
for(i = 0; i < N; i++)
    man[i] = (i + 1) % N;
注意这里没有简单地进行i++，这样就可以做到最后一个人man[N-1]的值是0，即最后一个人的下一个人的下标是0！
下来，如何解决按在圈内的人的顺序“报数”是关键。
而这里又有一个关键问题，就是如何从当前的man[i]走到下一个还在圈内的man[j]，注意，这里的i，j不是简单的j = i+1的关系，因为man[i]的下一个人很可能已经“出圈”了。
注意到上面对main[i]的值的定义可知，其实只要保证这个定义不受破坏，那么，下一个人的下标一定是：man[i]！
也就是说，走到man[i]的下一个还在圈内的人的方法应该是：i = man[i]
再一个问题就是“出圈”，如何让一个人出圈。看下例，设当前已在man[i]处，而man[i]要出圈：
man[i-2] => i-1 //i-1就是man[i-2]元素的值，它表示man[i-2]的下一个人的下标是i-1
man[i-1] => i
man[i]   => i+1
man[i+1] => i+2
现在让man[i]出圈的方法是：将man[i]的值赋值给man[i-1]，这样将得到：
man[i-2] => i-1
man[i-1] => i+1 //这表示man[i-1]的下一个人的下标是：i+1，这就把man[i]跳过去了！
man[i]   => i+1
man[i+1] => i+2
为了实现这个过程，需要有一个指向当前正在处理的人的前一个人的下标，令为j，那么，上述要求转换成语句：
man[j] = man[i];

说到这里感觉上已经没有问题了，其实还有一个大问题：
如果当前的人没有被“出圈”，那么只要执行：
j = i;
i = man[i];
就可以完成遍历过程；
但是，一旦有人出圈，那么，j所指向的人是不能变动的！
所以，如果没有人出圈，才能执行j = i的操作！

最后一个问题，循环条件：
很简单，设一个变量alive，初值为所有圈内人数，以后每出圈一个人，就alive--，直到其值为0！
综上，程序如下：
#include<stdio.h>

#define N 100 //初始人数
#define M 10  //厄运数值，谁数到这个数，谁出圈

void Joseph(int *man, int alive);

void Joseph(int *man, int alive)
{
    int i, j = N - 1/*让j指向最后一个人*/, ss = 0/*数的数字，初值为0*/;

    for(i = 0; alive; i = man[i])
    {
        if(++ss >= M) //数到厄运数字了，要出圈、输出、减人数
        {
            printf("%d\t", i+1); //编号为i+1的人出圈，输出显示其编号
            ss = 0; //重新开始数数
            alive--; //减少人数
            man[j] = man[i]; //让man[i]出圈
        }
        else
            j = i;
    }
}

int main(void)
{
    int p[N], i;

    for(i = 0; i < N; i++)
        p[i] = (i+1) % N;
    Joseph(p, N);
    return 0;
}
完毕！（程序经过验证）
从时间复杂度来看，这个算法其实还是O(N*M)，这是遗憾！

学习了，还是不怎么懂

好难( ⊙ o ⊙ )啊！我表示看不懂···