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

1748:约瑟夫问题

题目

总时间限制: 1000ms 内存限制: 65536kB

描述

约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入

每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:

0 0

输出

对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号

样例输入

6 2
12 4
8 3
0 0

样例输出

5
1
7

题意

有n只猴子围成一圈,顺时针从第1号开始报数,数到m的猴子退出,输入n和m,输出最后一只猴子的编号。

思路

创建一个包含n个点的循环链表,再通过指针遍历链表,数到m时就将当前节点从链表中删除,一直重复这个过程直到链表中只剩下一个节点,这个节点的编号就是猴王的编号。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
//定义链表
struct p{int num;//猴子的编号p *next;//指向下一个节点的指针p(){next=NULL;//初始化next为空}
};
void f(int n,int m){//创建头节点p *h=new p();h->num=1;h->next=NULL;p *tmp=h;//用于遍历链表//创建剩余的n-1个节点for(int i=1;i<n;i++){p *t=new p();//创建新节点t->num=i+1;//设置编号tmp->next=t;//连接新节点到链表末尾tmp=tmp->next;//移动tmp到新节点}tmp->next=h;//将链表首尾相连,形成循环//直到只剩一个节点时停止while(tmp->next!=tmp){//当节点的next指向自己时,说明只剩一个节点//移动m-1次for(int i=1;i<m;i++){tmp=tmp->next;//指向下一个节点}//将tmp的next指向下下个节点,跳过第m个节点(删除)tmp->next=tmp->next->next;}//输出最后剩下的猴王编号cout<<tmp->num<<endl;
}int main(){//循环输入,直到遇到0 0while(cin>>n>>m){if(n==0&&m==0) break;//输入0 0时结束程序f(n,m); //调用函数}return 0;
}
http://www.hskmm.com/?act=detail&tid=19205

相关文章:

  • Ansible + Docker 部署 Apache Nifi 1.28 单用户集群
  • 候机的队伍
  • Keil uVision5 设置 hex 输出路径,不放Objects目录下
  • 垃圾收集器G1ZGC详解
  • 2025海丰杯WP
  • 油猴脚本(tampermonkey)离线安装文件下载,带油猴(tampermonkey)插件清单
  • react useEffect Hook讲解
  • SentinelOne与MITRE ATTCK企业版2025评估的深度解析
  • 详细介绍:Docker的介绍
  • gen-ui-python
  • SPI和普通设计模式区别
  • 2025国内裱纸机厂家最新推荐排行榜:聚焦智能高速与全自动机型,权威精选综合实力 TOP3 厂家
  • 【题解】P13345 [EGOI 2025] IMO
  • 2025电线电缆厂家最新权威推荐榜:聚焦电线电缆实力企业,覆盖多场景需求助力精准选购
  • 9.27课后作业
  • 调度算法,上古三算法
  • 2025 年电脑租赁公司最新推荐排行榜:深度解析 TOP3 优质租电脑公司,助企业个人租赁电脑选择指南
  • 完整教程:✨WPF编程基础【1.2】:XAML中的属性
  • 学位论文中 公式的插入,格式调整、编号以及引用
  • 2025 北京羊蝎子餐厅推荐排行榜:TOP3最新必吃榜单,聚焦朝阳昌平东城等区域,揭秘北京羊蝎子餐厅必吃的门店!
  • 复刻江协激光触发器
  • Eurocrypt 2021 s Accepted Papers
  • Linux云服务器如何手动配置DNS?
  • Python 输入、输出的用法
  • 第一章——概论 - AlgosEng
  • 劝娃妈和娃不要学老人坐姿有感:老人无奈才坐成那样的。。AI协助分析很到位
  • 使用JOL查看对象布局
  • 集训队互测投题——封印
  • 一天一款实用的AI工具,第4期,AI翻译成英语
  • Docker基础与工程部署