（奖励3分）约瑟夫经典循环算法问题 - 黑马程序员技术交流社区

import java.util.LinkedList;
import java.util.List;

复制代码

/**
* 约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数），
* 开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，
* 将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，
* 如此下去直到所有的人全部都出列为止。试设计程序实现，按照出列的顺序打印各人的编号。
* @author Administrator
*
*/
public class Question2 {
class person {
int password;
int number;
int state = 1;
public person(int password, int number) {
this.password = password;
this.number = number;
}
public person(int number){
this.number = number;
}
}
public int ListLength(List<person> list) {
int count = 0;
if (list != null) {
for (person p : list) {
if (p.state != 0) {
count++;
}
}
}
return count;
}
public void cacle() {
// 初始化数据
List<person> list = new LinkedList<person>();
list.add(new person(3,1));
list.add(new person(1,2));
list.add(new person(7,3));
list.add(new person(2,4));
list.add(new person(4,5));
list.add(new person(8,6));
list.add(new person(4,7));
int position = -1;//初始位置
int m = 20; //第一次报多少的人出来
int count = 0;//已经报了多少人
while (ListLength(list) != 0) {
position = (position + 1) % list.size();// 位置定位
if (((person) list.get(position)).state != 0) {
count++;
}
if (count == m) {
person p = list.get(position);
System.out.print(p.number+" ");
p.state = 0;
m = p.password;
list.set(position, p);
count = 0;
}
}
}
public static void main(String[] args) {
Question2 q= new Question2();
q.cacle();
}
}

复制代码

public class Test {
public static int[] Joshphus(int start,int step,int size){ //start:从第几个人开始,step:报多少数走一个,size:一共多少人
int[] arInt=new int[size];
//1.初始化数组,把每个人编上号
for(int i=0;i<size;i++)
arInt[i]=i;
//2.先把开始报数的人挪到最前面的位置,就是arInt[0]
for(int i=start;i!=0;i--){
int temp=arInt[0];
for(int j=0;j<size;j++){
if(j!=size-1)
arInt[j]=arInt[j+1];
else
arInt[j]=temp;
}
}
//3.开始报数
int currentSize=size; //还剩多少人
int p=0; //该第几个人报数了
int num=1; //报数报到几了
while(currentSize>0){
if(num==step){ //报到step,这哥们出列了
int temp=arInt[p]; //出列的哥们要放到数组最后,先把他存起来
for(int i=p;i<size-1;i++)
arInt[i]=arInt[i+1];
arInt[size-1]=temp;
num=1;
if(p==--currentSize) //这里p就不用前移了,因为后面的人已经自动顶上来了
p=0; //但是p指向最后一个的话,要把p挪到最前面去
}else{ //还没报到step
num++;
if(++p==currentSize)
p=0;
}
}
return arInt;
}
public static void main(String[] args){
int[] arInt=Joshphus(2,3,7);
for(int i:arInt)
System.out.print(i+" ");
}
}

复制代码

package cn.itcast.demo;
import java.util.*;
public class ThreePointDemo {
public static void main(String[] args)
{
int dropNumber=0;
int count=0;
List<String> list=new LinkedList<String>();
for(int number=1;number<=12;number++)//这里设置你要存入多少人；
{
list.add("person number:"+number);
}
while(list.size()!=0)//核心程序代码
{
if(count==4)//这里设置你要的报号的数字我设置的为4；
{
int midparam=--dropNumber;
if(midparam<0)
{
midparam=list.size()-1;
}
System.out.println("the drop number is : number"+list.remove(midparam));
count=0;
print(list);
System.out.println();
}
count++;
dropNumber++;
if(list.size()==0)break;
dropNumber=dropNumber%list.size();
}
}
public static void print(List<String> list)//为了打印方便做的函数print
{
for(Iterator it=list.iterator();it.hasNext();)
{
System.out.print(it.next());
}
}
}

复制代码

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;
}
}

复制代码