题解 P1996 【约瑟夫问题】

· · 题解

这是一道模拟题，模拟虽然简单，但是，我们可以用循环链表来实现。
它更简洁，更高效。

循环链表是啥？？？
度娘：循环链表是另一种形式的链式存贮结构。
额，我想我没听懂。
来看看这个：

这就是循环链表。
除了尾节点以外，其他节点都指向下一个节点。
尾节点捏？？
尾节点指向头结点。

讲了大半天废话，辣么，题目怎么写呢？？
我们可以建立一个指针数组，为了方便（其实是我不会指针），我们可用数组实现。
先读入n、m，然后初始化链表。 

//初始化
for(i=1; i<n; i++)
    next[i]=i+1;//除了尾节点以外，其他节点都指向下一个节点
next[n]=1;//尾节点指向头结点。

然后，开始踢人了！
首先，我们知道，游戏结束的条件是只剩下一个人，对吧。
我们可以每踢掉一个人后，就把要被踢掉的人之前的人指向要被踢掉的人的后面。
可能有点难懂，来看看样例：（n=10，m=3） 首先踢掉3号，对吧？
于是成了这样。
继续踢6号。
踢完9号后，变成了这样。 要注意了，这一次要踢的，是2号。如图（从9号开始踢人） 然后踢到7号 以此类推。
结束条件便是当某一个数指向他自己时（只剩下他自己了）。

//核心代码
while(p!=next[p]) {//边界
    for(i=1; i<=m-2; i++)
        p=next[p];//往后跳m-2步，这样的话，下一个人就要被踢
    printf("%d ",next[p]);//输出
    next[p]=next[next[p]];//踢人了
    p=next[p];//继续
}
printf("%d",p);//别忘了我哦

我想大家应该都明白了吧！
噢，对了，还有一个坑点： 

//特判一下
if(!n&&!m)return 0;

完整代码：

#include<stdio.h>
int n,m,next[101],i,p;
int main() {
    scanf("%d%d",&n,&m);
    if(!n&&!m)return 0;
    for(i=1; i<n; i++)next[i]=i+1;
    next[n]=1,p=1;
    while(p!=next[p]) {
        for(i=1; i<=m-2; i++)
            p=next[p];
        printf("%d ",next[p]);
        next[p]=next[next[p]];
        p=next[p];
    }
    printf("%d",p);
    return 0;
}

不喜勿喷哦