`

约瑟夫环问题

阅读更多
约瑟夫环问题起源于一个犹太故事。约瑟夫环问题的大意如下:
   
    罗马人攻占了桥塔波特,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;
		}
	}

}
分享到:
评论

相关推荐

    循环队列和约瑟夫环问题

    循环队列和约瑟夫环问题 循环队列是一种特殊的队列结构,它的特点是队列的末尾元素连接着队列的开头元素,形成一个环形结构。这种数据结构可以用来解决约瑟夫环问题。 约瑟夫环问题是一个经典的问题,它是由古罗马...

    敢死队问题课程设计(约瑟夫环问题的应用)

    【敢死队问题(约瑟夫环问题的应用)】是一个经典的计算机科学问题,它涉及到数据结构和算法的设计。在这个问题中,M个敢死队员通过循环计数的方式决定执行任务的顺序,每数到5的人将执行任务并退出,直至只剩下一个...

    用循环链表实现约瑟夫环问题

    使用c语言中的循环链表及结构体实现约瑟夫环问题

    数据结构约瑟夫环问题

    数据结构中的约瑟夫环问题是一种经典的编程问题,它涉及到链表这一数据结构的应用。在本文中,我们将深入探讨约瑟夫环问题的背景、原理以及如何使用链表来求解这一问题,同时分析给定代码的具体实现细节。 ### ...

    约瑟夫环问题算法描述和程序实现(C#)

    约瑟夫环问题,也称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史上的一个故事。在这个问题中,人们围成一个圈,并按照一定的规则依次淘汰,最后留下来的人被称为“幸存者”。具体规则是:从...

    约瑟夫环问题用C++代码实现

    约瑟夫环问题,也称为约瑟夫问题,是一个经典的理论问题,源于古罗马时期的传说。问题描述了一群人围坐成一个圆圈,按照一定的规则进行报数,每数到特定数字的人会被排除,直到所有人都被排除。在这个场景中,我们...

    c++多种方法解决约瑟夫环问题

    多种方法解决约瑟夫环问题,1.顺序表2.循环链表3.循环队列4.普通一位数组

    约瑟夫环问题(C++)

    约瑟夫环问题,也被称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史上的一个故事。在这个问题中,人们站成一个圈,并按顺时针方向编号。从某个人开始,每隔特定的人数,这个人就会被排除出圈,...

    详细介绍约瑟夫环问题解析.docx

    约瑟夫环问题解析 约瑟夫环问题是计算机科学和数学中一个著名的问题,它是指在一个圆圈中的人按照一定的规则依次出列的问题。该问题的解析报告将从以下几个方面进行讲解: 一、问题描述 约瑟夫环问题可以用以下...

    约瑟夫环问题的编程实现

    约瑟夫环问题,也称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史的一个故事。在数学和计算机科学中,它通常被用来演示各种算法,特别是循环移位和递归算法。这个问题描述如下:假设有一群人围...

    用C语言实现约瑟夫环问题

    《C语言实现约瑟夫环问题详解》 约瑟夫环问题,又称约瑟夫环序列,是一个著名的理论问题,源自古罗马的一个传说。在这个问题中,人们围成一个圈,按照一定的规则逐个淘汰,直到剩下最后一个人为止。这个问题在...

    约瑟夫环问题实验报告

    约瑟夫环问题实验报告 约瑟夫环问题,这个名字起源于公元一世纪的犹太历史学家约瑟夫·弗拉维乌斯,在计算机科学领域,它已经演变成为了一个极具挑战性的数据结构问题。该问题描述了一个假想的场景:一群人围成一圈...

    约瑟夫环问题用循环队列解决

    用循环队列解决约瑟夫环问题减少用顺序表在出对是循环移动带来的空间复杂度

    1模拟轮盘抽奖游戏2模拟报数游戏(约瑟夫环问题)_抽奖轮盘_模拟报数游戏_模拟轮盘抽奖游戏_游戏_用python实现_

    在本项目中,我们将探讨如何使用Python编程语言来实现两种有趣的数学和计算机科学相关的游戏:模拟轮盘抽奖游戏和模拟报数游戏,也称为约瑟夫环问题。这两个游戏不仅有趣,而且能帮助我们理解循环、列表操作以及算法...

    约瑟夫环问题,C语言编写

    数据结构中的约瑟夫环问题 C语言编写,已经测试通过

    约瑟夫环问题的源代码(c++)

    约瑟夫环问题的源代码分析 约瑟夫环问题是计算机科学中的一种经典问题,描述的是10个小孩围坐在一圈,并给他们依次编号,指定从第s个小孩开始报数(从1~n报数),报到n的小孩出列,然后依次重复下去,直到所有的...

    C语言编写的关于约瑟夫环问题的程序

    标题中的“C语言编写的关于约瑟夫环问题的程序”指的是使用C编程语言实现的一个经典算法问题——约瑟夫环(Josephus Problem)。约瑟夫环问题是一个理论上的问题,通常在计算机科学和数学中被用作示例,以讨论和解决...

Global site tag (gtag.js) - Google Analytics