约瑟夫问题

分手后的思念是犯贱 2022-06-18 05:24 177阅读 0赞

###     ###

### 约瑟夫问题 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][] [ Statistic][Statistic]

#### Problem Description ####

n个人想玩残酷的死亡游戏，游戏规则如下：  
  
n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。  
  
请输出最后一个人的编号。

#### Input ####

输入n和m值。

#### Output ####

输出胜利者的编号。

#### Example Input ####

5 3

#### Example Output ####

#### Hint ####

第一轮：3被杀第二轮：1被杀第三轮：5被杀第四轮：2被杀

#### Author ####

\#include <stdio.h>  
\#include <math.h>  
struct mon  
\{  
    int num;  
    struct mon \* next;  
\};  
struct mon \* creat(int n) ///无空节点  
\{  
    int i;  
    struct mon \* p,\* tail,\*head;  
    p=(struct mon \*)malloc(sizeof(struct mon));   
    p->next=NULL;  
    head=p;  
    tail=p;  
    p->num=1;  
    for(i=2; i<=n; i++)  
    \{  
        p=(struct mon \*)malloc(sizeof(struct mon));  
        p->next=NULL;  
        p->num=i;  
        tail->next=p;  
        tail=p;  
    \}  
    tail->next=head; ///循环链表已建立  
    return head;  
\}  
int sel(struct mon \* head,int m,int n)  
\{  
    int num=0;  
    int count=0;  
    struct mon \*p,\*q;  
    q=head;  
    while (q->next!=head)   
        q=q->next;  
    while(count<n-1)  
    \{  
        p=q->next;///p=head;  
        num++;  
        if(num%m==0)  
        \{  
            q->next=p->next;  
            free(p);  
            count++;  
        \}  
        else q=p;  
    \}  
    return q->num;  
\}

int main()  
\{  
    int m,n;  
    struct mon \* head;  
    scanf("%d%d",&n,&m);  
    head=creat(n);  
    printf("%d\\n",sel(head,m,n));  
    return 0;  
\}

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2024/pid/1197.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2024/pid/1197.html