洛谷 P1996 约瑟夫问题（链表或数组模拟）

题目链接： 以下提供两种思路，一种是纯模拟（题目数据小，只有100），一种是链表（貌似还是模拟哈哈） 1.上代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
    int n,m;
    int a[105]={
         
  0};//标记这个人是否被踢出去
    scanf("%d %d",&n,&m);
    if(m==0)m=n;//如果m等于0，把m置为n
    int num=n;//目前还剩下的人
    int last=1;//上一次的最后一人
    while(num){
         
  //只要还有人
        int cnt=0;//一个累加变量
        for(int i=last;cnt!=m;i++){
         
  //从最后一人开始，数到m为止
            if(i>n)i%=n;//在下面的程序中出现了加到比n大的情况，就模n
            if(a[i]==-1)continue;//被踢出去了就continue
            ++cnt;//cnt+1
            if(cnt==m){
         
  //数到m了
                a[i]=-1;//把这个人踢出去
                num--;//还在的人数-1
                last=i+1;//下一次数的起点
                printf("%d ",i);//输出
                break;
            }
        }
    }
return 0;
}

2.链表

//循环链表实现。流程：数到这个人就把这个人从链表元素中删除并输出编号
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
struct node{
    int data;
    node *next;
};
int n,m;
node *head,*p,*r;
int main(){
    scanf("%d %d",&n,&m);
    if(m==0)m=n;//同上
    head=new node;//申请空间
    head->data=1;//头节点数据置为1
    head->next=NULL;//头节点下一个为空
    r=head;//尾指针现在是头
    for(int i=2;i<=n;i++){
        p=new node;
        p->data=i;
        p->next=NULL;
        r->next=p;//把申请的新节点连到前面的链表上
        r=p;//尾指针后移一个
    }
    r->next=head;//尾指针指向头
    r=head;//循环链表建立完成
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m-2;j++)r=r->next;//循环到m的前两个人
        cout<<r->next->data<<" ";//输出这第m个人的数据
        r->next=r->next->next;//跳过这个节点
        r=r->next;//新的一轮从上次的最后一个的下一个开始
    }
return 0;
}

总结：用来练习数据结构的基础题·