「约瑟夫思路java」约瑟夫环数据结构java
今天给各位分享约瑟夫思路java的知识，其中也会对约瑟夫环数据结构java进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
约瑟夫环java实现报错，菜鸟求解
问题原型：
传说在很久很久以前，有一架搭载着n个人的飞机出现了故障，迫降在了一个荒岛上。飞机彻底报废后，这些人用飞机的残骸建成了一艘只能容纳一个人乘坐的小船，那么怎么去确定这n个人中哪个人有资格上船呢？于是，这n个人采用了下面的方式来解决这个困境。
问题描述：
假设有N个人围成一圈，每个人都有从1到N的唯一顺序编号。接下来从编号为1的人开始顺序报数。报到M号的人退出这个圈。然后由下一个人重新由1开始进行报数，如此循环往复，那么最终留下来的是编号为多少的那个人呢？
java编程代码实现：
import java.util.Scanner;
public class countMethod {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
//接收用户输入，获得总人数N
System.out.println("请输入参与的总人数：");
int N=sc.nextInt();
//接收用户输入，获得出列人员的编号M
System.out.println("请输入出列的人的编号：");
int M=sc.nextInt();
//建立布尔型的数组，长度为总人数
Boolean rs[]=new Boolean[N];
//初始化布尔型数组，初始值均为true
for(int i=0;iN;i++){
rs[i]=true;
//System.out.println(rs[i]);
}
int n=N;//剩余的人数
int m=0;//报数的编号
while(n1){
for(int j=0;jN;j++){
if(rs[j]){
m++;
if(m==M){
m=0;
rs[j]=false;
n--;
//System.out.println(rs[j]);
}
}
}
}
//打印出最后留下来的人员的编号
for(int k=0;kN;k++){
if(rs[k]){
System.out.println("最后留下的是第"+(k+1)+"号。");
break;
}
}
}
}
用java解决约瑟夫问题
Java约瑟夫问题： n个人（不同id）围成一个圈，从startId(任意数)个开始报数m(任意数)个数，数m的人出列排成新队列，m清零，然后又从下一个人开始数m个数开始，数到m就出列接在新队列尾部，如此重复，知道所有人都出列为止。
package list;
import java.util.ArrayList;
* 打印 出列后的新队列
*
* eg
* int n = 10;//总人数
* int m = 3; //报数个数
* int startIndex = 1; //起点位置
* @author Hulk 2014 03 20
*
*/
public class JosephListTest {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
JosephListTest test = new JosephListTest();
int n = 10; //总人数
int m = 3; //报数个数
int startIndex = 12; //起点位置
System.out.println("JosephListTest: n= " + n + ", m= " + m +
", startIndex= " + startIndex + "\n\nQUEUE RESULT:");
ArrayListPerson queueList = test.queuePreson(n, m, startIndex);
for (Person person : queueList) {
System.out.println("OUT person: " + person);
}
System.out.println("use time= " +
(System.currentTimeMillis() - startTime));
}
private ArrayListPerson queuePreson(int n, int m, int startIndex) {
ArrayListPerson queueList = null;
PersonList list = createList(n);
//list.search();
if ((list != null) (list.head != null)) {
queueList = new ArrayListJosephListTest.Person();
PNode pNode = list.head;
if (startIndex 0) {
startIndex = startIndex % n;
pNode = list.getNode(startIndex);
} else {
pNode = list.head;
}
int count = 1;
while (list.size 0) {
Person outPerson = null;
//find
if (count == (m - 1)) {
//delete next node
Person prev = pNode.person;
outPerson = list.remove(prev);
queueList.add(outPerson);
//System.out.println("OUT person: " + outPerson + ", size= " + list.size);
count = 0;
}
pNode = pNode.next;
count++;
}
}
return queueList;
}
private PersonList createList(int n) {
PersonList list = new PersonList();
for (int i = 0; i n; i++) {
Person person = new Person(i, "name_" + (i + 1));
list.add(i, person);
}
return list;
}
public class PersonList {
PNode head = null;
int size = 0;
public PersonList() {
}
public PersonList(Person person) {
head = new PNode(person, head);
size++;
}
public PersonList(PNode head) {
this.head = head;
head.setNext(head);
size++;
}
public PNode getHead() {
return head;
}
public void setHead(PNode head) {
this.head = head;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public void size(int size) {
this.size = size;
}
public boolean isEmpty() {
return this.size = 0;
}
public void initHead(Person person) {
if (size == 0) {
head = new PNode(person, head);
} else {
PNode no = head;
head = new PNode(person, no);
}
size++;
}
public void add(int index, Person person) {
if (size == 0) {
head = new PNode(person, head);
head.setNext(head);
//System.out.println("head: " + head);
} else {
if (index 0) {
index = 0;
}
if (index size) {
index = size;
}
PNode no = head;
for (int i = 0; i (index - 1); i++) {
no = no.next;
}
PNode newNode = new PNode(person, no.next);
no.next = newNode;
}
size++;
}
public Person delete(int index) {
PNode pNode = remove(index);
if ((pNode != null) (pNode.next != null)) {
return pNode.next.person;
}
return null;
}
public PNode remove(int index) {
if (size == 0) {
return null;
} else {
if ((index 0) || (index = size)) {
return null;
}
}
PNode no = head;
for (int i = 0; i (index - 1); i++) {
no = no.next;
}
no.next = no.next.next;
size--;
if ((no != null) (no.next != null)) {
return no.next;
}
return null;
}
/**
* remove next node of person node, and return the deleted person
* @param prePerson
* @return removed Person
*/
public Person remove(Person prePerson) {
if (prePerson == null) {
return null;
}
if (size == 0) {
return null;
}
PNode preNode = head;
int index = -1;
for (int i = 0; i size; i++) {
if (preNode.person.id == prePerson.id) {
index = i;
break;
} else {
preNode = preNode.next;
}
}
Person remPerson = null;
if (size = 1) {
//only one node, get its person and set it as null
remPerson = preNode.person;
preNode = null;
} else {
//preNode.next.person is dest one
remPerson = preNode.next.person;
preNode.next = preNode.next.next;
}
size--;
//System.out.println("deleteing index= " + index + " : " + remPerson + ", size= " + size);
return remPerson;
}
public int update(Person src, Person dest) {
if (src == null) {
return -1;
}
int index = -1;
PNode no = head;
for (int i = 0; i size; i++) {
if (src.id == no.person.id) {
no.person = dest;
break;
} else {
no = no.next;
}
}
return index;
}
public boolean set(int index, Person person) {
if (person == null) {
return false;
}
if (size == 0) {
return false;
} else {
if ((index 0) || (index = size)) {
return false;
}
}
PNode no = head;
for (int i = 0; i index; i++) {
no = no.next;
}
no.person = person;
return true;
}
public Person get(int index) {
PNode no = getNode(index);
if (no != null) {
return no.person;
}
return null;
}
public PNode getNode(int index) {
if (size == 0) {
return null;
} else {
if ((index 0) || (index = size)) {
return null;
}
}
PNode no = head;
for (int i = 0; i index; i++) {
no = no.next;
}
return no;
}
public void search() {
int sizeLong = size;
PNode no = head;
for (int i = 0; i sizeLong; i++) {
System.out.println("search index= " + i + ", " + no);
no = no.next;
}
}
}
public class PNode {
Person person;
PNode next = null;
public PNode() {
}
public PNode(Person person) {
this.person = person;
}
public PNode(Person person, PNode next) {
this.person = person;
this.next = next;
}
@Override
public String toString() {
return "PNode [person=" + person.id + ", next=" + next.person.id +
"]";
}
public Person getPerson() {
return person;
}
public void setPerson(Person person) {
this.person = person;
}
public PNode getNext() {
return next;
}
public void setNext(PNode next) {
this.next = next;
}
}
public class Person {
int id = 0;
String name = "";
public Person() {
}
public Person(int id, String name) {
super();
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Person [id=" + id + ", name=" + name + "]";
}
}
}
Java约瑟夫经典循环算法
下面是我用c#写的，其实原理都一样，楼主自己研究下吧
Console.WriteLine("请输入参与游戏的人数：");
int numPerson = int.Parse(Console.ReadLine());
Console.WriteLine("请输入游戏退出的规则数：");
int ruleNum = int.Parse(Console.ReadLine());
bool[] person = new bool[numPerson]; //定义每个人是否退出开关，默认为否
int callNum = 0; //报数
int total = 0; //记录已经退出的人数
int index = -1; //报数的循环游标
while (true) {
index++; //从第一个人开始
index %= numPerson; //确保数组不越界，当游标指向最后一个数组元素以后，从头开始
if (!person[index]) { //第index个人没有退出时，则进行报数
callNum++;
}
if (callNum == ruleNum) { //当第index个人报数的数字与规则数相同时，则开关打开，退出报数
person[index] = true;
total++; //退出的总人数更新
callNum = 0; //为下一个人报数更新数据
Console.WriteLine("玩家{0}退出",index+1);
}
if ((numPerson - total) == 1) { //当游戏玩家只剩下一个的时候结束游戏
for (int i = 0; i person.Length; i++) {
if (person[i] == false) { // 判断退出开关依然是否的玩家
Console.WriteLine("最后剩下的玩家是第：{0}位",i + 1); //输出实际的玩家号
break;
}
}
break;
}
}
关于约瑟夫思路java和约瑟夫环数据结构java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。