约瑟夫问题

心已赠人 2022-05-30 04:46 170阅读 0赞

1.知识点：循环链表  
2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号  
3.注意事项：注意删除节点的前后节点的指针域的指向变化

代码：

#include <stdio.h>
    #include <stdlib.h>
    struct peo
    {
        int date;
        struct peo *next;
    };//定义结构体
    struct peo * num(int n)//定义顺序建循环链表函数, 注意返回值类型
    {
        struct peo *head, *tail, *p;
        int i;
        p = (struct peo *)malloc(sizeof(struct peo));
        p -> date = 1;
        p -> next = NULL;
        head = p;
        tail = p;
        for(i = 2; i <= n; i++)
        {
            p = (struct peo *)malloc(sizeof(struct peo));
            p -> date = i;
            tail -> next = p;
            p -> next = NULL;
            tail = p;
            ///wrong answer:p = tail;
        }//顺序建链表
        tail -> next = head;//转化为循环链表
        return head;
    }
    int sur(struct peo * head, int n, int m)//进行约瑟夫问题, 注意返回值类型
    {
        struct peo *q, *p;
        int count, a;
        count = 1;//根据题设条件灵活变通
        a = 0;
        q = head;
        while(a < n-1)//控制
        {
            p = q -> next;
            count ++;
            if(count % m == 0)
            {
                q -> next = p -> next;
                free(p);
                p = q -> next;
                a++;
            }//节点的删除问题
            else
                q = p;
        }
        return q -> date;//最后一个节点的数据域即为最优解
    }
    int main()
    {
        int n, m;
        struct peo *head;
        scanf("%d %d", &n, &m);
        head = num(n);
        printf("%d\n", sur(head, n, m));
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫问题

约瑟夫问题作者：Ackarlix 这是一个非常经典的问题：n个骑士编号1，2，...，n，围坐在圆桌旁，编号为k的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1

刺骨的言语ヽ痛彻心扉/ 2022年09月19日 13:29/ 0 赞/ 201 阅读

相关约瑟夫问题

约瑟夫问题如下： n个人围成一圈，从1号开始报数，报到m就退出，剩下的人从下一个人开始继续报数。。。问最后剩下的是谁？也可问每个人的死亡顺序. 这一题在数据量比较小的

太过爱你忘了你带给我的痛/ 2022年08月10日 17:55/ 0 赞/ 146 阅读

相关约瑟夫问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？ ![Center][] 第一种方法：循环思想

待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 181 阅读

相关约瑟夫问题

适合队列初学者 \include<queue> //队列头文件 queue<int>q; //定义队列q，I

ゝ一世哀愁。/ 2022年08月04日 04:10/ 0 赞/ 176 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被

￡神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 174 阅读

相关约瑟夫问题

约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis

分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 178 阅读

相关约瑟夫问题

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017

╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 273 阅读

相关约瑟夫问题

1.知识点：循环链表 2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号 3.注意事项：

心已赠人/ 2022年05月30日 04:46/ 0 赞/ 171 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人

我就是我/ 2022年05月16日 06:06/ 0 赞/ 184 阅读

相关约瑟夫问题

约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述：开始有5个人围成圆形，从0号开始，数2个人，谁被数到就

灰太狼/ 2022年04月16日 00:46/ 0 赞/ 199 阅读