数据结构——约瑟夫环C语言链表实现

        约瑟夫环问题由古罗马史学家约瑟夫(Josephus)提出,他参加并记录了公元66—70年犹太人反抗罗马的起义。在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。起义者表示“宁为玉碎不为瓦全”,约瑟夫则想“留得青山在不愁没柴烧”。于是,约瑟夫建议41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。问:约瑟夫及其朋友应该站在哪个位置?、

        n个人围成一个圆圈,然后从第一个人开始,按:1,2,3,…,m报数,数到m的人出圈,并有出圈者的下一个人重新开始报数,数到m又要出圈,如此类推,直到所有人都出圈,打印出圈的次序,其中n和m为输入数据

        这个问题可以通过数学推理和递归算法来解决。通过不断地计算,可以发现每次移除一个人后,剩下的人重新排列成一个新的圆圈,规模减小并且从下一个人开始。通过不断地递归计算,可以找到最后一个人的位置。

        本篇博客用C语言,利用循环单链表求解约瑟夫环问题。

        引用的头文件

#include<stdio.h>
#include<malloc.h>
#include<time.h>//计算执行时间 

        在main函数中,首先输入总人数count和报数规律num,然后调用Solve_lijie函数求解约瑟夫环问题。为了计算程序执行时间,使用了clock函数来记录开始和结束时刻,然后计算差值得到执行时间。

int main()
{int count, num;double duration; Loop* L;printf("输入总人数count和报数规律num:");scanf("%d%*c%d", &count, &num);//循环单链表求解clock_t start, finish;//长整型数 start = clock();Solve(L, count, num);finish = clock();//记录前后时刻 duration = (double)(finish - start) / CLOCKS_PER_SEC;//这个是有定义的宏 printf("\n使用循环单链表存储所用执行时间:%lf", duration);return 0; } 

结构体定义

typedef int ElemType;
typedef struct Josephus
{ElemType MEN;	struct Josephus* next;
}Loop;
// 循环单链表初始化
void Init(Loop* &L)
{L = (Loop *)malloc(sizeof(Loop));L -> next = L;	// 头尾相连 
}void Create(Loop* &L, int count)
{if(count < 1){printf("介个是个空环\n");return;}Loop *s, *r;Init(L); //初始化头节点 L->MEN = 1; r = L;	//指向头节点 for(int i = 2; i <= count; i++){	//对头节点后面的节点进行初始化并录入数据 Init(s);s->MEN = i;s->next = L;//循环,尾部也是L r->next = s;//r指向头节点 r = s;}
}void Display(Loop* &L)//用于检测是否正常录入数据 
{Loop *p = L;if(L == NULL)return;	printf("报数:\n");do{printf("%d\t", p->MEN);p = p->next;}while(p != L);//兜兜转转回到原点 printf("\n");return; 
}
void Solve(Loop* &L, int count, int num)
{Create(L, count);Display(L);int j;//循环,根据报数规律num让成员出列,受总人数count影响//每杀一个,count--; 每到第num个,就打印后free一个 Loop *p, *r;r=p = L;while(r->next != L)r = r->next;for(int i = count; i > 1; i--){j = 1;do{		r = p;	//形成一前一后两指针 p = p->next;j++;}while(j < num);// 不符合出列条件。此时两指针各下移一个单位r->next = p->next;printf("这个人死了: %d\n", p->MEN);free(p);p = r->next;//符合条件。此时后指针后续链接前指针的后续,释放前指针p,然后恢复前后位置顺序。}printf("获胜者是%d\n", p->MEN);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/374288.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

go语言Gin框架的学习路线(六)

gin的路由器 Gin 是一个用 Go (Golang) 编写的 Web 框架&#xff0c;以其高性能和快速路由能力而闻名。在 Gin 中&#xff0c;路由器是框架的核心组件之一&#xff0c;负责处理 HTTP 请求并将其映射到相应的处理函数上。 以下是 Gin 路由器的一些关键特性和工作原理的简要解释…

第十八章 Express multer 文件上传

本章将学习Express multer 文件上传 &#xff0c;因为Nest 的文件上传是基于 Express 的中间件 multer 实现的&#xff0c;所以在学习 Nest 文件上传之前&#xff0c;我们先学习下 multer 包 首先先创建 multer-test 文件夹执行下面代码 创建package.json npm init -y接着安装…

单例模式的简单理解

单例模式 前言一、单例模式是什么二、单例模式的使用饿汉模式单线程下的懒汉模式多线程下的懒汉模式&#xff08;优化懒汉模式&#xff09;加锁 三、总结 前言 设计模式是将一些经典的问题场景进行整合归纳&#xff0c;并提供一些解决方案&#xff0c;相当于一种“套路”。 熟…

数据仓库介绍_维度表(三)

维度表概述 维度表是维度建模的基础和灵魂。前文提到&#xff0c;事实表紧紧围绕业务过程进行设计&#xff0c;而维度表则围绕业务过程所处的环境进行设计。维度表主要包含一个主键和各种维度字段&#xff0c;维度字段称为维度属性。 表设计步骤 确定维度&#xff08;表&…

SQL 针对上面的salaries表emp_no字段创建索引idx_emp_no

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 描述 针对salaries…

【开源合规】开源许可证风险场景详细解读

文章目录 前言关于BlackDuck许可证风险对比图弱互惠型许可证举个例子具体示例LGPL系列LGPL-2.0-onlyLGPL-2.0-or-laterLGPL-2.1-onlyLGPL-2.1-or-laterLGPL-3.0-onlyLGPL-3.0-or-laterMPL系列MPL-1.0MPL-1.1MPL-2.0EPL系列EPL-1.0EPL-2.0互惠型许可证GPL系列GPL-1.0GPL-2.0GPL-…

3.相机标定原理及代码实现(opencv)

1.相机标定原理 相机参数的确定过程就叫做相机标定。 1.1 四大坐标系及关系 &#xff08;1&#xff09;像素坐标系&#xff08;单位&#xff1a;像素&#xff08;pixel&#xff09;&#xff09; 像素坐标系是指相机拍到的图片的坐标系&#xff0c;以图片的左上角为坐标原点&a…

合合信息大模型加速器亮相WAIC大会:文档解析与文本识别新突破

合合信息大模型加速器亮相WAIC大会&#xff1a;文档解析与文本识别新突破 文章目录 合合信息大模型加速器亮相WAIC大会&#xff1a;文档解析与文本识别新突破前言合合信息TextIn平台&#xff1a;智能文档处理的领军者文档解析引擎&#xff1a;百页文档秒级处理大模型的发展背景…

【机器学习】独立成分分析(ICA):解锁信号的隐秘面纱

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 独立成分分析&#xff08;ICA&#xff09;&#xff1a;解锁信号的隐秘面纱引言I…

若依 ruoyi-vue SpringBoot highlight-textarea 输入框敏感词关键词高亮标红(二)

参考文章&#xff0c;非常感谢大佬的分享 实现可高亮的输入框 — HighlightTextarea GitHub:highlight-textarea 可看作者上一篇文章 若依 ruoyi-vue SpringBoot聊天敏感词过滤sensitive-word&#xff08;一&#xff09; 效果图 审核时&#xff0c;输入框高亮敏感词&#xff…

vue3 + tsx 表格 Action 单独封装组件用法

前言 先上图看右侧列 action 的 UI 效果&#xff1a; 正常来说&#xff0c;如果一个表格的附带 action 操作&#xff0c;我们一般会放在最右侧的列里面实现&#xff0c;这个时候有些UI 框架支持在 SFC 模板里面定义额外的 solt&#xff0c;当然如果不支持&#xff0c;更通用的…

LabVIEW实现LED显示屏视觉检测

为了满足LED显示屏在生产过程中的严格质量检测需求&#xff0c;引入自动化检测系统是十分必要的。传统人工检测方式存在检测强度高、效率低、准确性差等问题&#xff0c;自动化检测系统则能显著提高检测效率和准确性。视觉检测系统的构建主要包含硬件和软件两个部分。 视觉系统…

新兴市场游戏产业爆发 传音以技术抢抓机遇 ​

随着年轻人口的增加以及互联网的普及,非洲、中东等新兴市场正迎来游戏产业的大爆发,吸引着全球游戏企业玩家在此开疆辟土。中国出海企业代表传音以新兴市场需求为中心,秉持本地化创新理念不断加强游戏等关键领域技术攻关凭借移动终端设备为全球玩家带来极致游戏体验,收获了消费…

谷粒商城实战笔记-26-分布式组件-SpringCloud-Gateway网关核心概念原理

微服务架构中&#xff0c;API网关扮演着至关重要的角色&#xff0c;它不仅作为微服务间的通信桥梁&#xff0c;还负责安全、监控、限流等职责。 一&#xff0c;网关的发展历程 SpringCloud的网关经历了两代的迭代和更替。 第一代网关是早期的Zuul&#xff0c;由 Netflix 开发…

kafka 消费者

消费者 消费者。消费者连接到Kafka上并接收消息&#xff0c;进而进行相应的业务逻辑处理。 消费组 消费者负责订阅Kafka中的主题&#xff0c;并且从订阅的主题上拉取消息。 消费组&#xff1a;每个消费者都有一个对应的消费组&#xff0c;每一个分区只能被一个消费组中的一个…

深入了解Rokid UXR2.0 SDK内置的Unity AR Glass开发组件

本文将了解到Rokid AR开发组件 一、RKCameraRig组件1.脚本属性说明2.如何使用 二、PointableUI组件1.脚本属性说明2.如何使用 三、PointableUICurve组件1.脚本属性说明2.如何使用 四、RKInput组件1.脚本属性说明2.如何使用 五、RKHand组件1.脚本属性说明2.如何使用3.如何禁用手…

昇思25天学习打卡营第17天|基于 MindSpore 实现 BERT 对话情绪识别

基于 MindSpore 实现 BERT 对话情绪识别 BERT介绍 BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;是一种基于Transformer架构的预训练语言模型&#xff0c;由谷歌在2018年提出。从以下6个方面来介绍BERT&#xff1a; 1. 预训练和微调&…

Linux C语言基础 day8

目录 思维导图&#xff1a; 学习目标&#xff1a; 学习内容&#xff1a; 1. 字符数组 1.1 二维字符数组 1.1.1 格式 1.1.2 初始化 1.1.3 二维字符数组输入输出、求最值、排序 2. 函数 2.1 概念 关于函数的相关概念 2.2 函数的定义及调用 2.2.1 定义函数的格式 2.3…

GaussDB关键技术原理:高性能(五)

GaussDB关键技术原理&#xff1a;高性能&#xff08;四&#xff09;从USTORE存储引擎、计划缓存计划技术、数据分区与分区剪枝、列式存储和向量化引擎、SMP并行执行等五方面对高性能关键技术进行解读&#xff0c;本篇将从LLVM动态查询编译执行、SQL-BYPASS执行优化、线程池化、…

k8s核心操作_Ingress统一网关入口_域名访问配置_ingress域名转发规则配置_根据域名访问不同服务---分布式云原生部署架构搭建026

上一节我们已经把 ingress 安装好了可以看到 kubectl get svc -A 可以看到 出现了ingress-nginx 的service,在ingre-nginx这个命名空间中,有两个,一个是 ingress-nginx-controller 开了两个一个是对应http,一个对应https 一个是 ingress-nginx-controller-admission 对…