约瑟夫问题——循环链表

秒速五厘米 2022-09-28 11:46 161阅读 0赞

think:  
1顺序建立循环链表+循环链表中的符合题意的元素结点的删除  
2注意只有一个人玩死亡游戏的情况

[sdut原题链接][sdut]

约瑟夫问题  
Time Limit: 1000MS Memory Limit: 65536KB

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

Input  
输入n和m值。

Output  
输出胜利者的编号。

Example Input  
5 3

Example Output  
4

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

Author

以下为accepted代码1

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int Data;
        struct node *next;
    }*head, *tail;
    void Build(int n);//顺序建立循环链表
    void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点
    int main()
    {
        int n, m;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            if(n == 1)
                printf("%d\n", n);
            else
            {
                head = (struct node *)malloc(sizeof(struct node));
                head->Data = 1;//循环链表中头结点不再为空
                head->next = NULL;
                tail = head;
                Build(n);//顺序建立循环链表
                Search_ans(head, m);//循环链表中删除满足题意的元素结点
            }
        }
        return 0;
    }
    void Build(int n)//顺序建立循环链表
    {
        struct node *p;
        for(int i = 2; i < n; i++)
        {
            p = (struct node *)malloc(sizeof(struct node));
            p->Data = i;
            p->next = tail->next;
            tail->next = p;
            tail = p;
        }
        p = (struct node *)malloc(sizeof(struct node));
        p->Data = n;
        tail->next = p;
        p->next = head;
    }
    void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点
    {
        int cnt = 0;
        struct node *q, *p;
        q = tail->next;
        p = head;
        while(p->next != p)
        {
            cnt++;
            if(cnt % m == 0)
            {
                q->next = p->next;
                free(p);
                p = q->next;
            }
            else
            {
                q = p;
                p = p->next;
            }
        }
        printf("%d\n", p->Data);
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-03-10 21:04:59
    ****************************************************/

以下为accepted代码2

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int Data;
        struct node *next;
    }*head, *tail;
    void Build(int n);//顺序建立循环链表
    void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点
    int main()
    {
        int n, m;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            head = (struct node *)malloc(sizeof(struct node));
            head->Data = 1;//循环链表中头结点不再为空
            head->next = NULL;
            tail = head;
            Build(n);//顺序建立循环链表
            Search_ans(head, m);//循环链表中删除满足题意的元素结点
        }
        return 0;
    }
    void Build(int n)//顺序建立循环链表
    {
        struct node *p;
        for(int i = 2; i < n; i++)
        {
            p = (struct node *)malloc(sizeof(struct node));
            p->Data = i;
            p->next = tail->next;
            tail->next = p;
            tail = p;
        }
        if(n != 1)
        {
            p = (struct node *)malloc(sizeof(struct node));
            p->Data = n;
            tail->next = p;
            p->next = head;
        }
        else
        {
            head->next = head;
        }
    }
    void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点
    {
        int cnt = 0;
        struct node *q, *p;
        q = tail->next;
        p = head;
        while(p->next != p)
        {
            cnt++;
            if(cnt % m == 0)
            {
                q->next = p->next;
                free(p);
                p = q->next;
            }
            else
            {
                q = p;
                p = p->next;
            }
        }
        printf("%d\n", p->Data);
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-03-10 21:06:48
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2024/pid/1197