约瑟夫问题

太过爱你忘了你带给我的痛 2022-08-10 17:55 146阅读 0赞

约瑟夫问题如下：

n个人围成一圈，从1号开始报数，报到m就退出，剩下的人从下一个人开始继续报数。。。问最后剩下的是谁？也可问每个人的死亡顺序.

这一题在数据量比较小的情况下，可以采用模拟的方法解决。代码如下：

<span style="font-size:10px;">#include<cstdio>
    #include<cstring>
    int p[10000];
    int main()
    {
        int n,k;
        freopen("1.txt","w",stdout);
        while (scanf("%d %d",&n,&k)==1)
        {
            int i,count=1,sign=1,cal=0;
            memset(p,0,sizeof(p));
            while (sign)
            {
                sign=0;
                for (i=1;i<=n;i++)
                {
                    if (p[i]==0)
                    {
                        ++cal;
                        if (!sign)sign=1;
                        if (cal==k)
                        {
                            coun=0;
                            p[i]=count++;
                        }
                    }
                }
            }
            for (i=1;i<=n;i++)
                printf("%d\n",p[i]);
            //printf("\n");
        }
        return 0;
    }</span>

如果问题是让你死亡顺序输出人员编号，可直接输出，也可用map 容器替代数组解决。这同样可以用链表解决，不过个人感觉链表好像有点麻烦.....

当然在数据量较大后，这种方法就不在适用，一是储存空间问题，二是时间问题。此代码的最糟糕情况复杂度为n^2级别。

URAL  1521 [http://acm.timus.ru/problem.aspx?space=1&num=1521][http_acm.timus.ru_problem.aspx_space_1_num_1521] 就是用模拟会挂掉的题目，于是只能优化，采用线段树的方法解决。

具体方法参见[http://blog.csdn.net/lilongherolilong/article/details/6614430][http_blog.csdn.net_lilongherolilong_article_details_6614430]

[http_acm.timus.ru_problem.aspx_space_1_num_1521]: http://acm.timus.ru/problem.aspx?space=1&num=1521
[http_blog.csdn.net_lilongherolilong_article_details_6614430]: http://blog.csdn.net/lilongherolilong/article/details/6614430