请选择 进入手机版 | 继续访问电脑版
点击联系客服
客服QQ:509006671 客服微信:mengfeiseo

东莞老站长

 找回密码
立即注册
热搜: 活动 交友 discuz
查看: 158|回复: 50

约瑟夫·凌-自杀环问题简单明确的循环链板

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-3-5 14:21:20 | 显示全部楼层 |阅读模式
这是一道经典的链表题

约瑟夫环自杀环问题

约瑟夫环问题有着这样的历史:

Josephus有过的故事:39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀。然后下一个重新报数,直到所有人都自杀身亡为止。然而Josephus  和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

大体意思

共有N人围坐在一起,循环周期为M,第一个人报告1,第二个人报告2,数字到了M,那个人就会出列。下一个人从1开始继续报告数字,整个过程持续到所有人都出来。这种问题一般会问最后一个出列的人是谁,或者是第一个出列的人。

对于学习了计算机的我们来说,重复性如此强的过程,当然要交给计算机来帮我们完成呐。所以我们一起来编写这个程序吧。

之前更了数组实现和数学推理方法,现在来补链表法。

大致思路

建立一个单向循环链表(看题目而定),先建立一个表头,在把每个人一个一个的尾插进去,然后把头尾相连。在模拟报数,把要自杀的人一个一个删掉,最后留下来的那个,就是答案。

#includestdio.h

#includestdlib.h

Typedef  struct  node{

Int  data

结构节点*下一步;

}节点;

Node* creat(
keyword">int data)
{
        node *head;
        head = (node *)malloc(sizeof(node));
        head->data = data;
        head->next = NULL;
        return head;
}
//建立链表
node* creatnode(node* head, int data)
{
        node *now = head;
        node *neww = (node*)malloc(sizeof(node));
        neww->data = data;
        neww->next = NULL;
        while(NULL != now->next)
                now = now->next;
        now->next = neww;
        return neww;
}
//插入节点
void merge(node* head, node* end)
{
        end->next = head;
}
//首尾相连
void detele(node* qian, node* need){
        qian->next = need->next;
        free(need);
}
//删除节点
int main()
{
        node *head = creat(1);
        node *end;
        node *now = head;
        int n, m, i, j;//n表示有多少个人,m表示报到几就自杀。
        scanf("%d%d", &n, &m);
        for(i=2;in;i++)
                end = creatnode(head, i);
        merge(head, end);
        node *qian = end;
        for(i=1;in;i++)
        {
                for(j=1;jm;j++)
                {
                        now = now->next;
                        qian = qian->next;
                }
                if(i!=(n-1)){
                        detele(qian, now);
                        now = qian->next;
                }
        }
        printf("%d", qian->data);
        return 0;
}

谢谢观看!数组模拟实现和数学推理法在这里!
回复

使用道具 举报

1

主题

215

帖子

-29

积分

限制会员

积分
-29
发表于 2021-3-5 14:23:25 | 显示全部楼层
没看完~~~~~~ 先顶,好同志
回复

使用道具 举报

0

主题

208

帖子

34

积分

新手上路

Rank: 1

积分
34
发表于 2021-3-5 14:53:22 | 显示全部楼层
难得一见的好帖
回复

使用道具 举报

1

主题

217

帖子

-16

积分

限制会员

积分
-16
发表于 2021-3-5 15:13:50 | 显示全部楼层
支持一下
回复

使用道具 举报

0

主题

187

帖子

15

积分

新手上路

Rank: 1

积分
15
发表于 2021-3-5 15:34:00 | 显示全部楼层
好帖,来顶下
回复

使用道具 举报

1

主题

211

帖子

-37

积分

限制会员

积分
-37
发表于 2021-3-5 15:55:19 | 显示全部楼层
好帖,来顶下
回复

使用道具 举报

1

主题

238

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2021-3-5 16:16:03 | 显示全部楼层
前排支持下
回复

使用道具 举报

0

主题

217

帖子

-1

积分

限制会员

积分
-1
发表于 2021-3-5 16:36:07 | 显示全部楼层
不错,支持下楼主
回复

使用道具 举报

1

主题

241

帖子

41

积分

新手上路

Rank: 1

积分
41
发表于 2021-3-5 16:59:40 | 显示全部楼层
路过,学习下
回复

使用道具 举报

1

主题

218

帖子

-23

积分

限制会员

积分
-23
发表于 2021-3-5 17:19:41 | 显示全部楼层
支持一下
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|东莞@IT精英团

GMT+8, 2021-4-13 15:14 , Processed in 0.109053 second(s), 40 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表