Java实现 蓝桥杯 算法提高 奥运会开幕式
2024-09-06 22:24:12
试题 算法提高 奥运会开幕式
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
学校给高一（三）班分配了一个名额，去参加奥运会的开幕式。每个人都争着要去，可是名额只有一个，怎么办？班长想出了一个办法，让班上的所有同学（共有n个同学）围成一圈，按照顺时针方向进行编号。然后随便选定一个数m，并且从1号同学开始按照顺时针方向依次报数，1, 2, …, m，凡报到m的同学，都要主动退出圈子。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下的那个人就是去参加开幕式的人。
要求：用环形链表的方法来求解。所谓环形链表，即对于链表尾结点，其next指针又指向了链表的首结点。基本思路是先创建一个环形链表，模拟众同学围成一圈的情形。然后进入循环淘汰环节，模拟从1到m报数，每次让一位同学（结点）退出圈子。
输入格式：输入只有一行，包括两个整数n和m，其中n和 m的含义如上所述。
输出格式：输出只有一个整数，即参加开幕式的那个人的编号。
输入输出样例
样例输入
8 3
样例输出
7
PS：花里胡哨的说一大堆，其实就是约瑟夫环
每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。
因为求出的结果是数组中的下标，最终的编号还要加1
import java.util.Scanner;
public class 约瑟夫环 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int p = 0;
for (int i = 2; i <= n; i++) {
p = (p + k) % i;
}
System.out.println(p + 1);
}
}
详细的可以看另一篇文章约瑟夫斯问题
最新文章
- python安装第三方类库的方法
- 循序渐进Python3（十）-- 2 -- SqlAlchemy
- Android MediaRecorder录制音频
- C# GridControl 行背景颜色
- BIP_开发案例10_BI Publisher报表国际化多语言的实现（案例）
- nodeJs事件之监听移除事件
- 1022. Genealogical Tree（topo)
- oracle ref游标
- dotnet core 开发体验之Routing
- linux环境下搭建环境发布web项目
- JS时间日期格式转换
- hadoop--安装1.2.1版本
- C#7.0之ref locals and returns (局部变量和引用返回,之前欠大家的,现在补上)
- bug：翻页
- 三张图搞懂JavaScript的原型对象与原型链
- vue(四)-vuex与组件联合使用
- C++拷贝构造函数与 = 重载
- C#阿里云移动推送列表
- python安装途中遇到的问题和解决方法
- 从Qt到PyQt