经典算法-----约瑟夫问题(C语言)

news/2024/2/23 15:55:37/文章来源:

 目录

前言

故事背景

约瑟夫问题

环形链表解决

 数组解决



前言

        今天我们来玩一个有意思的题目,也就是约瑟夫问题,这个问题出自于欧洲中世纪的一个故事,下面我们就去通过编程的方式来解决这个有趣的问题,一起来看看吧!

故事背景

        据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

        17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。

约瑟夫问题

从键盘获取两个数据,n和s,n是表示人数,s是表示从第一个人开始数,数到第s个的时候那个人就出局,问:最后剩下的最后一个人是第几个?

环形链表解决

        这里我们可以去通过环形链表的形式来解决这个问题 ,过程图如下所示:

先根据当前输入的人数去创建一个相对应的环形链表,依次把每个人的位置存入进去

 然后就去从第一个人开始数,当数到第三个人的时候就进行删除操作,如下所示,后面就从第四个节点开始新的一轮……

代码如下所示: 

#include <stdio.h>
#include<stdlib.h>
//节点
typedef struct node {
int num;
struct node* next;
}Node;
//创建一个环形链表
Node* create_list(int n) {
Node* head, * tail;
head = tail = NULL;
for (int i = 0; i < n; i++) {
Node* p = (Node*)malloc(sizeof(Node));
p->num = i + 1;    //依次标记当前位置
if (head == NULL) {
head = p;
tail = p;
head->next = NULL;
}
else
{
tail->next = p;
tail = p;
}
tail->next = head;
}
return head;  //返回头结点
}
int main() {
int n, s;
printf("请输入:");
scanf("%d %d", &n, &s);
Node* cur = create_list(n);
int count = 1; //此时cur指向的是第一个节点&#xff0c;所以count为1
while (n != 1) {	//当n=1时候&#xff0c;结束循环&#xff0c;此时剩下最后一个人
count++;//先进行count统计
if (count == s) {
n--;	
//进行删除节点操作
Node* del_node = cur->next;	
cur->next = del_node->next;
free(del_node);//释放掉这个节点
//此时count回归到1&#xff0c;也就是重新开始新的一轮
count = 1;
}
cur = cur->next;
}
printf("最后剩下的是&#xff1a;%d\n", cur->num);
}

 数组解决

         不同与链表的是&#xff0c;数组不能去自定义人的数量&#xff0c;也就是说这里数组的数量是提前写好了的&#xff0c;还有就是数组的执行效率更加高&#xff0c;环形链表要去通过遍历执行&#xff0c;时间复杂度为O(n),而数组可以去直接找到这个位置时间复杂度为O(1)&#xff0c;不需要去一个一个遍历&#xff0c;代码如下&#xff1a;

//数组实现
#include<stdio.h>
void function(int* num, int length, int s, int start) {
int count = 0;
int i = start - 1;//标记起始位置
int n = length;	//当前人数
while (n != 1) {
i = (i + s - 1) % n;	//下一个出局人的位置
for (int j = i + 1; j < length; j++)
num[j - 1] = num[j];	//进行删除操作&#xff0c;把要删除的数字后面的依次往前移动&#xff0c;覆盖掉这个要删除的数字
n--;//删除操作完成&#xff0c;减少一个人
if (i == n) {	//当i超出数组范围的时候&#xff0c;i就回归到第一个为止
i = 0;
}
}
printf("最后一个 :%d", num[i]);
return;
}
int main() {
int num[6];//这里就已经定义好了6个人
int s;	//每次数到s&#xff0c;出局一个
printf("请输入:");
scanf("%d", &s);
for (int i = 0; i < sizeof(num) / sizeof(int); i++)
num[i] = i+1;
function(num, sizeof(num) / sizeof(int), s, 0);
}

以上就是今天的内容&#xff0c;我们下次见&#xff01;

分享一张壁纸&#xff1a;

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

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

相关文章

2023最新安装微信小程序开发软件安装教程

一&#xff0c;安装开发者工具 我们在开发小程序之前&#xff0c;首先需要安装小程序开发者工具&#xff0c;今天就来教大家安装小程序开发者工具。 微信开放文档 (qq.com)https://developers.weixin.qq.com/miniprogram/dev/framework/ 官网工具下载地址&#xff1a; 微信…

pytorch代码实现之动态卷积模块ODConv

ODConv动态卷积模块 ODConv可以视作CondConv的延续&#xff0c;将CondConv中一个维度上的动态特性进行了扩展&#xff0c;同时了考虑了空域、输入通道、输出通道等维度上的动态性&#xff0c;故称之为全维度动态卷积。ODConv通过并行策略采用多维注意力机制沿核空间的四个维度…

【深度学习】实验13 使用Dropout抑制过拟合

文章目录 使用Dropout抑制过拟合1. 环境准备2. 导入数据集3. 对所有数据的预测3.1 数据集3.2 构建神经网络 3.3 训练模型3.4 分析模型 4. 对未见过数据的预测4.1 划分数据集4.2 构建神经网络4.3 训练模型4.4 分析模型 5. 使用Dropout抑制过拟合5.1 构建神经网络5.2 训练模型5.3…

加密货币交易所偿付能力的零知识证明

如何检测下一个 FTX 和 Mt. Gox 加密货币交易所 FTX 的内爆导致数十亿客户资金流失&#xff0c;这是加密货币历史上交易所破产的最新例子。历史可以追溯到 2014 年&#xff0c;当时处理 70% 比特币交易的历史最悠久、规模最大的交易所 Mt. Gox 丢失了用户的 850,000 个比特币。…

python使用websocket实现多端数据同步,多个websocket同步消息,断开链接自动清理

我使用的是flask_sock这个模块&#xff0c;我的使用场景是&#xff1a;可以让数据多端实时同步。在游戏控制后台和游戏选手的ipad上都可以实时调整角色的技能和点数什么的&#xff0c;所以需要这样的一个功能来实现数据实时同步。 下面是最小的demo案例&#xff1a; from fla…

指数渐变线

指数渐变线是非均匀传输线的一种。为何叫指数渐变线呢&#xff1f;其分布参数变化规律为指数规律&#xff0c;比如&#xff1a;单位长度的电感、电容、特性阻抗。 1、分析过程 从非均匀线的微分方程出发&#xff1a; 对方程两侧同时取微分&#xff1a; 化简得&#xff1a; …

elementui 中 DateTimePicker 组件时间自定义格式化

elementui 中 DateTimePicker 组件时间自定义格式化 需求分析 需求 elementui 中 DateTimePicker 组件时间自定义格式化 自定义需求&#xff1a;需要获取到 DateTimePicker 组件时间的值为[“2023/9/5 20:2”,“2023/9/4 2:10”] 分析 源码如下&#xff1a; <el-date-pick…

2023数学建模国赛游记

第一参加数学建模国赛&#xff0c;大概也是最后一次参加了&#xff0c;记录一下这几天的历程吧。 我们队的情况是计算机电气数统&#xff0c;计算机负责编程&#xff0c;电气学院的负责论文部分&#xff0c;数统的同学负责建模&#xff0c;数据处理部分我们是共同承担。 第一天…

微服务学习(七):docker安装Mysql

微服务学习&#xff08;七&#xff09;&#xff1a;docker安装Mysql 1、拉取镜像 docker pull mysql2、查看安装的镜像 docker images3、安装mysql docker run -p 3306:3306 --name mysql \ -v /mydata/mysql/log:/var/log/mysql \ -v /mydata/mysql/data:/var/lib/mysql \…

基于SpringBoot+Vue的宠物领养饲养交流管理平台设计与实现

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

计算机专业毕业设计项目推荐08-英语在线点读平台(SpringBoot+Vue+MongoDB)

英语在线点读平台&#xff08;SpringBootVueMongoDB&#xff09; **介绍****系统总体开发情况-功能模块****各部分模块实现** 介绍 本系列(后期可能博主会统一为专栏)博文献给即将毕业的计算机专业同学们,因为博主自身本科和硕士也是科班出生,所以也比较了解计算机专业的毕业设…

SSRF漏洞(利用file协议读取本地文件)

简介 当利用SSRF漏洞时&#xff0c;攻击者可以通过构造恶意请求来读取本地文件。其中一种方法是使用file协议来读取本地文件。例如&#xff0c;file:///etc/passwd是一个常见的示例&#xff0c;它用于读取Linux系统上的passwd文件。 passwd文件是Linux系统中用于存储用户账户…

2.求循环小数

题目 对于任意的真分数 N/M &#xff08; 0 < N < M &#xff09;&#xff0c;均可以求出对应的小数。如果采用链表表示各个小数&#xff0c;对于循环节采用循环链表表示&#xff0c;则所有分数均可以表示为如下链表形式。 输入&#xff1a; N M 输出&#xff1a; 转换…

时序数据库 TimescaleDB 安装与使用

TimescaleDB 是一个时间序列数据库&#xff0c;建立在 PostgreSQL 之上。然而&#xff0c;不仅如此&#xff0c;它还是时间序列的关系数据库。使用 TimescaleDB 的开发人员将受益于专门构建的时间序列数据库以及经典的关系数据库 (PostgreSQL)&#xff0c;所有这些都具有完整的…

力扣:103. 二叉树的锯齿形层序遍历(Python3)

题目&#xff1a; 给你二叉树的根节点 root &#xff0c;返回其节点值的 锯齿形层序遍历 。&#xff08;即先从左往右&#xff0c;再从右往左进行下一层遍历&#xff0c;以此类推&#xff0c;层与层之间交替进行&#xff09;。 来源&#xff1a;力扣&#xff08;LeetCode&#…

Android StateFlow初探

Android StateFlow初探 前言&#xff1a; 最近在学习StateFlow&#xff0c;感觉很好用&#xff0c;也很神奇&#xff0c;于是记录了一下. 1.简介&#xff1a; StateFlow 是一个状态容器式可观察数据流&#xff0c;可以向其收集器发出当前状态更新和新状态更新。还可通过其 …

Go语言开发环境搭建指南:快速上手构建高效的Go开发环境

Go 官网&#xff1a;https://go.dev/dl/ Go 语言中文网&#xff1a;https://studygolang.com/dl 下载 Go 的语言包 进入官方网站 Go 官网 或 Go 语言中文网&#xff1a; 选择下载对应操作系统的安装包&#xff1a; 等待下载完成&#xff1a; 安装 Go 的语言包 双击运行上…

Linux 远程登录(Xshell7)

为什么需要远程登录Linux&#xff1f;因为通常在公司做开发的时候&#xff0c;Linux 一般作为服务器使用&#xff0c;而服务器一般放在机房&#xff0c;linux服务器是开发小组共享&#xff0c;且正式上线的项目是运行在公网&#xff0c;因此需要远程登录到Liux进行项日管理或者…

PgSQL-安全加固实践-如何设置非全零监听

PgSQL-安全加固实践-如何设置非全零监听 1、介绍 PgSQL在启动前需要配置listen_addresses配置项&#xff0c;该配置项表示允许PgSQL服务监听程序绑定的IP。我们知道一个host上可以有多个网卡&#xff0c;每个网卡可以绑定多个IP&#xff0c;该参数就是控制PgSQL服务绑定在哪个或…

容器的数据卷

容器的数据卷 操作数据卷 # 基本格式 docker volume [common] # 创建一个volume docker volume create # 显示一个或多个volume docker volume inspect # 列出所以的volume docker volume ls # 删除未使用的volume docker volume prune # 删除一个或多个volume docker volume…