当前位置: 首页 > news >正文

【蓝桥杯】环形链表的约瑟夫问题

 目录

题目描述:

输入描述:

输出描述:

示例1

解法一(C):

解法二(Cpp):



正文开始:

题目描述:

        据说著名犹太历史学家 Josephus 有过以下故事:在罗马人占领乔塔帕特后,39 个犹太人与 Josephus 及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一种自杀方式:41 个人排成一个圆圈,由第 1 个人开始报数,报数到 3 的人就自杀,然后再由下一个人重新报 1,报数到 3 的人再自杀,这样依次下去,直到剩下最后一个人时,那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。

输入描述:

        一行两个整数 n 和 m, n 表示环形链表的长度, m 表示每次报数到 m 就自杀。

输出描述:

        输出最后存活下来的人编号(编号从1开始到n)

示例1

        输入:        5        2

        输出:        3

(备注:   1≤n,m≤1000)


解法一(C):

        创建环形链表,通过两个函数实现:

typedef struct ListNode LS;//根据传入的x的值,创建val = x 的新节点
LS* BuyNewnode(int x)
{LS* newnode = (LS*)malloc(sizeof(LS));if(newnode == NULL){perror("malloc");exit(1);}newnode->val = x;newnode->next = NULL;return newnode;
}//将新节点链接起来
LS* CreateL(int n)
{//第一个节点的val的初始值赋值为1LS* phead = BuyNewnode(1);LS* ptail = phead;for(int i = 2;i <= n;i++){ptail->next = BuyNewnode(i);ptail = ptail->next;}ptail->next = phead;//由于链表中删除某一节点,必须能找到前驱节点,如此才能改变前驱节点的next指针的方向//为了在初始时找到头节点的前驱节点,所以CreateL函数选择返回ptailreturn ptail;
}

         重点:

        1.         while()的终止条件,当pcur->next == pcur 时,循环终止;(这个时候只剩一个人了)

        2.        f:计数作用;(表示每个人报的数);pcur 每动一次,f 都跟着变化;并且初始 f 是1;(第一个人也是要报数的)

        3.        如果f==m,(这个人要自杀);前驱节点next指针指向pcur的下一个节点;同时把pcur这个节点free掉,pcur后移。

        4.        如果f != m,正常报数;pcur向后,prev向后,f++;

主体部分: 


int ysf(int n, int m ) {// write code hereLS* ptail = CreateL(n);LS* pcur = ptail->next;LS* prev = ptail;int f = 1;while(pcur->next != pcur){if(f == m){prev->next = pcur->next;free(pcur);pcur = prev->next;f = 1;}else{pcur = pcur->next;prev = prev->next;f++;}}return pcur->val;
}

解法二(Cpp):

(源自 牛客Huster水仙)

  • 将编号改为从0开始,记f(n,m)为原问题的解

  • 由于第一次遍历了0~(m-1)%n,则第二次遍历相当于将整个队伍循环左移了k位(k=m%n)

  • 所以子问题f(n-1,m)的解循环右移k位即为原问题的解f(n,m)

#include<iostream>
#include<queue>
using namespace std;int getans(int n,int m){if(n==1)return 0;else{return (getans(n-1,m)+m)%n;}}int main(){int m,n;while(scanf("%d%d",&n,&m)!=EOF){printf("%d\n",getans(n,m)+1);}return 0;
}

 


完~

 未经作者同意禁止转载

相关文章:

【蓝桥杯】环形链表的约瑟夫问题

目录 题目描述&#xff1a; 输入描述&#xff1a; 输出描述&#xff1a; 示例1 解法一&#xff08;C&#xff09;&#xff1a; 解法二&#xff08;Cpp&#xff09;&#xff1a; 正文开始&#xff1a; 题目描述&#xff1a; 据说著名犹太历史学家 Josephus 有过以下故事&a…...

深度学习本科课程 实验1 Pytorch基本操作

一、Pytorch基本操作考察 1.1 任务内容 使用 &#x1d413;&#x1d41e;&#x1d427;&#x1d42c;&#x1d428;&#x1d42b; 初始化一个 &#x1d7cf;&#x1d7d1; 的矩阵 &#x1d474; 和一个 &#x1d7d0;&#x1d7cf; 的矩阵 &#x1d475;&#xff0c;对两矩阵…...

大数据分析|设计大数据分析的三个阶段

文献来源&#xff1a;Saggi M K, Jain S. A survey towards an integration of big data analytics to big insights for value-creation[J]. Information Processing & Management, 2018, 54(5): 758-790. 下载链接&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1…...

华为机考入门python3--(7)牛客7-取近似值

分类&#xff1a;数字 知识点&#xff1a; str转float float(str) 向上取整 math.ceil(float_num) 向下取整 math.floor(float_num) 题目来自【牛客】 import math def round_to_int(float_num): # 如果小数点后的数值大于等于0.5&#xff0c;则向上取整&#xf…...

C# Avalonia 11.0.6 绘图

在 Avalonia 11.0.6 中&#xff0c;Render 方法是被标记为 sealed 的&#xff0c;意味着不能直接在子类中重写这个方法。这样的设计可能是为了确保一致性和避免误用。 如果你需要在 Avalonia 中进行自定义的绘图操作&#xff0c;可以使用 DrawingContext&#xff0c;但是需要通…...

使用java -jar命令运行jar包提示“错误:找不到或无法加载主类“的问题分析

用maven把普通java项目打包成可运行的jar后&#xff0c;打开cmd用java -jar运行此jar包时报错&#xff1a; 用idea运行该项目则没有问题 。 其实原因很简单&#xff0c;我们忽略了2个细节。 java指令默认在寻找class文件的地址是通过CLASSPATH环境变量中指定的目录中寻找的。我…...

Tomcat组件架构与数据流

一、背景与简介 Tomcat我们都知道是一个开源的、实现了大部分Java EE、Servlet、JSP规范的Servlet容器, 允许我们将实现了Serlvet接口的Web程序war包进行部署运行。 但是你有对Tomcat做过细致的学习么? 我相信大部分同学和我一样&#xff0c;之前也是只会进行简单使用&#x…...

AES算法:数据传输的安全保障

在当今数字化时代&#xff0c;数据安全成为了一个非常重要的问题。随着互联网的普及和信息技术的发展&#xff0c;我们需要一种可靠的加密算法来保护我们的敏感数据。Advanced Encryption Standard&#xff08;AES&#xff09;算法应运而生。本文将介绍AES算法的优缺点、解决了…...

前端小案例——动态导航栏文字(HTML + CSS, 附源码)

一、前言 实现功能: 这案例是一个具有动态效果的导航栏。导航栏的样式设置了一个灰色的背景&#xff0c;并使用flex布局在水平方向上平均分配了四个选项。每个选项都是一个li元素&#xff0c;包含一个文本和一个横向的下划线。 当鼠标悬停在选项上时&#xff0c;选项的文本颜色…...

前置机、堡垒机(跳板机)【2024-02-04】

文章目录 0、前言1、前置机1.1、概念1.2、功能1.3、使用场景1.4、总结 2、堡垒机2.1、概念2.2、功能2.3、使用场景2.4、总结 3、前置机和堡垒机3.1、设计理念与目的3.2、功能3.3、使用场景 0、前言 文章借鉴&#xff1a; https://blog.csdn.net/weixin_45565886/article/detai…...

从编程中理解:大脑的短期记忆和长期记忆

在编程中&#xff0c;我们可以将大脑的短期记忆和长期记忆类比为程序中的变量作用域和持久化存储。在Unity C#编程环境下&#xff0c;可以这样解释&#xff1a; 假设金庸武侠世界中的人物张无忌正在修炼九阳真经。我们用C#代码来模拟他学习武功的过程&#xff0c;其中涉及的“…...

Rust 本地文档的使用:rustup doc

Rust 是一种系统级编程语言&#xff0c;以其安全性、速度和内存控制能力而闻名。为了方便开发者更好地了解并利用 Rust 标准库和工具链中的功能&#xff0c;Rust 提供了一种内置的文档浏览方式——通过 rustup doc 命令。 安装 rustup 在查阅 Rust 文档之前&#xff0c;确保你…...

uni-app切换页面刷新,返回上一页刷新(onShow钩子函数的使用)

切换页面刷新&#xff1a;通过onShow()便可实现 返回上一页通过uni.navigateBack({delta: 1});实现 以返回上一页刷新为例 从B页面返回上一页到A页面&#xff0c;在A页面写入方法refreshHandler() //a.vue methods: { // 执行刷新逻辑refreshHandler() {uni.request({ur…...

adb 无线连接 操作Android设备

最近集五福活动比较热门 可以用这个工具 用自己擅长的语言写一个循环程序 运行起来就可以 自动帮我们 看视频得福卡了 很方便 while (true) {sleep(mt_rand(15, 25));system(adb shell input swipe 500 2000 500 1000 100); } 1. 首先下载 安卓开发工具 adb adb网盘链接 链接…...

春节运维不打烊:一体化运维高效保障企业IT与机房环境

随着技术的不断发展和企业数字化转型的深入&#xff0c;IT运维已经成为企业运营不可或缺的一部分。尤其在春节期间&#xff0c;一体化运维管理系统以其独特的技术特性和卓越的功能&#xff0c;为企业的稳定运行提供了坚实保障&#xff0c;确保了节日的祥和与工作的连续高效。 一…...

类银河恶魔城学习记录1-5 CollisionCheck源代码 P32

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Player.cs using System.Collections; using System.Collections.Generic; using Unity.VisualScripting; u…...

spring boot 使用 Kafka

一、Kafka作为消息队列的好处 高吞吐量&#xff1a;Kafka能够处理大规模的数据流&#xff0c;并支持高吞吐量的消息传输。 持久性&#xff1a;Kafka将消息持久化到磁盘上&#xff0c;保证了消息不会因为系统故障而丢失。 分布式&#xff1a;Kafka是一个分布式系统&#xff0c…...

LFU缓存(Leetcode460)

例题&#xff1a; 分析&#xff1a; 这道题可以用两个哈希表来实现&#xff0c;一个hash表&#xff08;kvMap&#xff09;用来存储节点&#xff0c;另一个hash表&#xff08;freqMap&#xff09;用来存储双向链表&#xff0c;链表的头节点代表最近使用的元素&#xff0c;离头节…...

Vue学习笔记:计算属性

计算属性 入门进阶二次进阶三次进阶四次进阶结界五次进阶六次进阶七次进阶八次进阶九次进阶终章彩蛋 入门 Vue.js中&#xff0c;计算属性示例&#xff1a; export default {data() {return {firstName: John,lastName: Doe};},computed: {// 计算属性&#xff1a;全名fullNam…...

深度学习本科课程 实验2 前馈神经网络

任务 3.3 课程实验要求 &#xff08;1&#xff09;手动实现前馈神经网络解决上述回归、二分类、多分类任务 l 从训练时间、预测精度、Loss变化等角度分析实验结果&#xff08;最好使用图表展示&#xff09; &#xff08;2&#xff09;利用torch.nn实现前馈神经网络解决上述回归…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...