约瑟夫问题简析

题目：n个人（1到n）报数，从1报到r，报r的出局，然后下一个又从1开始报。。。，问最后留下的人是几号。

用循环链表应该思路最清晰，报r的人就删除此节点。用数组的话，看见过解法，要判断该位置是否有人，还要注意取余，因为是循环的一个圈。我用数组解就是这样，初始化后，开始报数，用一个变量记录当前报数的值，只有位置上有人（非0）时才增加，到r时把该位置置0。这样操作一次出局一人，循环n-1次就剩 最后一人了，也可以再用个数组记录每次出局的人，就更加清晰。

void josh(int n,int r) //n个人，报r的出局

{
    int a[1000];
    int i,sum,now; //i对r计数，sum表示还没出局的人，now表示当前“指针"不管位置上有人与否-

    int j;
    for(j=1;j<=n;j++) //初始化数组，从a[1]开始

        a[j]=j;
    sum=n;
    now=1;
    for(j=1;j<n;j++){ //循环n-1次，最后剩下的一个为结果

        i=0;
        while(i<r) {
            if (a[now]==0) {
                ++now; //当前位置是0，已经出局了，就只移动指针

                if (now>n)
                    now=1;
                //continue;

            }
            else { //此位置还有人

                i++; //i计数，表示此人报数了

                if(i==r)
                    a[now]=0;
                ++now;
                if (now>n)
                    now=1;
            }
        }
        --sum;
    }

    for(j=1;j<=n;j++)
        if (a[j]!=0)
            printf("result is:%d",a[j]);
}

然后发现网上有用递推实现，时间复杂度是O（n）。想想也是，应该是有规律的。参考了http://hi.baidu.com/wind__talker/blog/item/2375c6238d207547925807fb.html等地方。然后在r=3的时候枚举了一下，还是很明显的，就是不好用公式表达。我上面的程序是从1开始计数，没有用a[0],分析的时候也是这样，和参考的地方有点不同，结果上来看基本一致。
第一次出列的是r mod n 号，取余是怕r比n大。这里有个问题，我是从1到n号，r mod n等于0怎么办，没有0号啊，参考资料里面是从0开始，刚好避免了这个问题。。。我这里没有考虑，最后按答案来修正的了。
继续，第一次出列的是r mod n 号，一般也就是r号嘛，先当做r吧；然后剩下的n-1个数等价于n-1规模的子问题了，不过号码不是从1开始，而是r+1、r+2、...、0、1、...r-1。如果已经知道n-1的问题的答案f(n-1)=k,则在上面的号码中数到k，对应的就是f(n)也就是答案了。可以摸索验证一下，递推式是：

f(n)=[r mod n+f(n-1)] mod n

里面的取余其实可以不要，等价于

f(n)=[r +f(n-1)] mod n

以为很完美，和参考资料一样，可是就因为人数没有从0开始计数到n-1（我这不是更自然嘛，都从1数啊），f(n)可能为0，而没有0号，当为0号的时候答案是n。应该是对的吧。总之基本上是解决了，水平就只有这样了。

看到稍微加难的问题，第一次报数不是从第一个人开始，而是从第s号开始报，答案又是什么呢？取巧的话，可以第一次就先把数组从s开始初始化。。。