约瑟夫环问题起源于一个犹太故事。约瑟夫环问题的大意如下:
罗马人攻占了桥塔波特,41人藏在一个山洞中躲过了这场浩劫。这41个人中,包括历史学家Josephus(约瑟夫)和他的一个朋友。剩余的39个人为了表示不向罗马人屈服,决定集体自杀。大家决定了一个自杀方案,所有者41个人围成一个圆圈,由第1个人开始顺时针报数,每报数为3的人就立刻自杀,然后再由下一个人重新开始报数,仍然是每报数为3的人就立刻自杀,。。。。。。,直到所有人都自杀身亡为止。
约瑟夫和他的朋友并不想自杀,于是约瑟夫想到了一个计划,他们两个同样参与到自杀方案中,但是最后却躲过了自杀。请问,他们是怎么做到的?
简单约瑟夫环算法
我们先来分析一个约瑟夫环问题。其实,约瑟夫和他的朋友只要在一直报1或者2的位置即可,最后剩下3个人时,另一个人报3自杀后,剩下约瑟夫和他的朋友,即可不遵循自杀方案躲过自杀。
我们可以用数组来模拟环,数组的值为每个人的位置,用一个数作为标记,来模拟数1,2,3的过程,当标记为3时,对应位置的数组值赋值为0,表示这个人已经自杀。此时将标记赋值为0,没经过一个人,标记值加1,重复这个过程,当到达数组末尾后,从数组头继续。直到自杀了39个人位置,最后剩下的两个位置即为约瑟夫和其朋友的位置。
下面这部分是我的代码:
import java.util.Scanner;
public class JosephusProblem {
public static void main(String[] args) {
int sum=0;//自杀人的个数
int n,killMan;
boolean num=true;
//int flags = 0;
int flag = 0;
System.out.print("请输入约瑟夫环问题中的人数:");
Scanner input = new Scanner(System.in);
n = input.nextInt();//总人数
System.out.print("请输入自杀者的报数:");
killMan = input.nextInt();
int[] a = new int[n];
for(int i = 0; i < n;i++)
{
a[i]=i+1;
}
while(num)
{
int j;
for(j = 0;j<n;j++)
{
if(a[j]>0)
{
flag+=1;
if((flag%3)==0)//数到3的人
{
sum+=1;//统计自杀的人数
a[j]=0;//将自杀位置的人的值赋值为0,表明该人已不存在
System.out.println("第"+(j+1)+"位置的人会自杀!");
flag=0;//清零,方便下一个人从新计数
}
if((n-sum)<killMan)//输出没有自杀的人的位置
{
for(int k=0;k<n;k++)
{
if(a[k]>0)
{
System.out.println("第"+(k+1)+"位置的人不会自杀!");
}
}
num=false;//用于判断是否退出循环
break;
}
}
}
j=0;
}
}
}
分享到:
相关推荐
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
使用c语言中的循环链表及结构体实现约瑟夫环问题
多种方法解决约瑟夫环问题,1.顺序表2.循环链表3.循环队列4.普通一位数组
约瑟夫环问题描述:编号为1,2,…,n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将...
用循环队列解决约瑟夫环问题减少用顺序表在出对是循环移动带来的空间复杂度
用数据结构循环队列实现约瑟夫环问题,数据结构的一次实验;
数据结构中的约瑟夫环问题 C语言编写,已经测试通过
用顺序表实现约瑟夫环问题,并分析算法的时间和空间复杂性。
约瑟夫环问题(c++实现),包含设计文档,实现了8个功能: 1.要求在实现约瑟夫环的同时,应该满足以下要求: 2.完整的图形用户界面,可以配置程序的运行参数,如:n的值,k的值、m的值、执行动画的速度等; 3.算法...
java解决约瑟夫环问题
约瑟夫环问题,用循环链表实现,最后输出胜利者
约瑟夫环问题解析报告
用数据结构中的链表实现著名的约瑟夫环问题比较麻烦,这是用C语言编写的约瑟夫环问题,代码和截图。
首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质,考虑采用循环链表,为了统一对表中任意给定的操作,循环链表不带头结点。
用单向循环链表来实现约瑟夫环问题.自己做的数据结构课设,供大家参考!
汇编语言编写的猴子选美,及约瑟夫环,有一定注释~
约瑟夫环问题解决