Java实现约瑟夫斯问题
2024-10-09 04:47:34
1 问题描述
引用自《算法设计与分析基础》第三版:
约瑟夫斯问题,是以弗拉瓦斯。约瑟夫斯(Flavius Josephus)的名字命名的。约瑟夫斯是一个著名的犹太历史学家,参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫斯作为一个将军,设法守住了裘达伯特的堡垒达47天之久,但在城市陷落了以后,他和40名顽强的将士在附近的一个洞穴中避难。在那里,这些反抗者表决说“要投降毋宁死”。于是,约瑟夫斯建议每个人应该轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫斯有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降罗马。
上述是约瑟夫斯问题的起源,看完后个人感觉有点抽象,其实约瑟夫斯问题的本质为:n个人(编号由 1,2, …, n)围成一圈,由编号为1的人从1开始报数,报到k的退出自杀,剩下的人继续从1开始报数,直到圈内只剩余1人,求胜利者的编号。(n>0, k>0)
例如:
原n个人编号:
1 2 3 4 … … n-1 n
现在进行报数:
1 2 3 4… k(出列自杀) 1 2 …(循环报数,当到达编号为n的人时,下一个报数的从编号为1的人开始进行)
2 解决方案
约瑟夫斯问题的核心即找出给定n个人从前到后的自杀顺序,最后一个将要进行自杀的人即为幸存者。
具体编码如下:
package com.liuzhen.chapter4;
import java.util.Scanner;
public class JosephProblem {
/*
* 参数n:给定总人数
* 参数k:报数为k的人出列
* 函数功能:返回n个人从前到后的自杀顺序
*/
public int[] getKillOrder(int n,int k){
int[] result = new int[n];
int[] man = new int[n];
for(int i = 0;i < n;i++)
man[i] = i+1; //给n个人编号,编号分别为1~n
int count = 0; //用于计算当前已经自杀的人数
int pos = -1; //用于记录遍历数组man当前下标
int tempK = 0; //用于计算报数大小,一旦tempK = k,则喊到k的人出列
while(count < n){
pos = (pos+1)%n; //遍历过程中,会出现环列,取余可以除去环的影响
if(man[pos] != 0) //man[pos] == 0,表示此人已自杀
tempK++;
if(tempK == k){
result[count++] = man[pos]; //记录当前自杀人的编号
man[pos] = 0;
tempK = 0;
}
}
return result;
}
public static void main(String[] args){
JosephProblem test = new JosephProblem();
Scanner in = new Scanner(System.in);
System.out.println("请输入约瑟夫斯问题的总人数n:");
int n = in.nextInt();
System.out.println("请输入约瑟夫斯问题的报数设定值k:");
int k = in.nextInt();
int[] result = test.getKillOrder(n,k);
System.out.println("共"+n+"人,依次报数,当报到"+k+"的人自杀,其自杀顺序为:");
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+" ");
}
}
运行结果:
请输入约瑟夫斯问题的总人数n:
请输入约瑟夫斯问题的报数设定值k:
共6人,依次报数,当报到2的人自杀,其自杀顺序为:
4 6 3 1 5
请输入约瑟夫斯问题的总人数n:
请输入约瑟夫斯问题的报数设定值k:
共7人,依次报数,当报到2的人自杀,其自杀顺序为:
4 6 1 5 3 7
请输入约瑟夫斯问题的总人数n:
请输入约瑟夫斯问题的报数设定值k:
共10人,依次报数,当报到3的人自杀,其自杀顺序为:
6 9 2 7 1 8 5 10 4
详细的可以看另一篇文章约瑟夫斯问题
最新文章
- oracle学习笔记(二)
- 深入理解Spring Redis的使用 (一)、Spring Redis基本使用
- 按下enter键后表单自动提交问题
- jquery中append()、prepend()、after()、before()的区别详解
- codeforces 336D. Vasily the Bear and Beautiful Strings 组合数学 dp
- Oracle 学习系列之二(会话与事务级临时表和dual表 )
- hust 1017 DLX
- Visual Studio 2012 破解版
- [wiki]CDN
- Android 报错:error: too many padding sections on bottom border
- 第四章:Oracle12c 数据库在linux环境安装
- 【论文速读】Shitala Prasad_ECCV2018】Using Object Information for Spotting Text
- Opecv + Anaconda 读取视频(windows)
- 使用vue iview遇到的一些问题
- 轻型池不支持执行公共语言运行时(CLR)。禁用以下两个选项中的一个: “clr enabled”或“lightweight pooling”解决方法
- ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket
- JAVA面试题整理(3)-Spring
- unity3d之实现各种滑动效果
- Asp.net MVC 自定义错误页面以及return HttpNotFound遇到的问题
- LeetCode Next Closest Time
热门文章
- python selenium unittest Fixture(setUp/tearDown)笔记
- npm加载包报错 :syscall access
- css3弹性布局
- Jenkins-插件开发-BUG-Messages类编译报错
- strom_hdfs与Sequence详解
- oracle分析函数Rank, Dense_rank, row_number
- 关于Slow HTTP Denial of Service Attack slowhttptest的几种慢攻击DOS原理
- Python之日志处理(logging模块二实战)
- PHP 获取当前目录下的所有文件
- 安装依赖jdk---linux