【C/C++】约瑟夫环问题

2024-08-28 17:28
文章标签 c++ 问题 约瑟夫

本文主要是介绍【C/C++】约瑟夫环问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

    • 题目描述
      • 输入描述
      • 输出描述
    • 示例
    • 题解

题目描述

n个人(0,1,2,3,4…n-1),围成一圈,从编号为k的人开始报数,报数报到m的人出队(报数是1,2,…m这样报的)。下次从出队的人之后开始重新报数,循环往复,当队伍中只剩最后一个人的时候,那个人就是大王。现在,给定n,k,m,
请你求出大王的编号。

输入描述

输入一行包含三个整数n,k,m
1<=n<=100,1<=k<=n-1,1<=m<=100

输出描述

输出一个整数

示例

输入
5 1 2

输出
3

题解

解法一:
用数组做标记,模拟

#include <stdio.h>
int main(){int n,k,m;scanf("%d %d %d",&n,&k,&m);int a[105] = {0},count = n;//0表示还未被淘汰,1表示已经被淘汰while(count != 1){for(int i=1;i<=m-1;i++){while(a[(k+1)%n]){  //判断后面的一个人是否已经淘汰k=(k+1)%n;}k=(k+1)%n;}a[k] = 1; //表示报到m的人淘汰 count--;  //相应的人数要减一 while(a[k]){k = (k+1)%n; //下次从出队的人之后开始重新报数,循环往复}}printf("%d",k);return 0;
}

解法二:

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k,m;cin>>n>>k>>m;int ans=0;for(int i=1;i<=n;i++){ans=(ans+m)%i;}cout<<(ans+k)%n;return 0;    
}

解法三:
利用c++的queue

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;int main() {queue<int>q;int n, k, m; cin >> n >> k >> m;for (int i = k; i < n; i++){q.push(i);}for (int i = 0; i < k; i++){q.push(i);}int id = 0;while (q.size()!=1){int a = q.front();q.pop();id++;if (m == id)id = 0;else q.push(a);}cout<<q.front();return 0;
}

解法四:
queue的不同解法

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int main() {int n,k,m;cin>>n>>k>>m;queue<int> q;for(int i=0;i<n;i++) q.push(i);for(int i=0;i<k;i++){q.push(q.front());q.pop();}int cnt =0;while(q.size()>1){cnt++;if(cnt==m){q.pop();cnt=0;}else{q.push(q.front());q.pop();}}cout<<q.front();return 0;
}

请添加图片描述

这篇关于【C/C++】约瑟夫环问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL