用java数组实现约瑟夫环
十年专注成都网站制作，成都定制网页设计，个人网站制作服务，为大家分享网站制作知识、方案，网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于成都定制网页设计,高端网页制作,对花箱等多个行业，拥有丰富的网站推广经验。
package Josephround;
public class Joseround {
int sit;
int flagjo=0;
Joseround(){};
Joseround(int x){
sit=x;
}
void setflag(int x){
flagjo=x;
}
}
package Josephround;
public class Inijose {
Joseround jo[];
static int length=0;
Inijose(){};
Inijose(int x){
jo=new Joseround[x];
for(int i=0;ix;i++){
jo[i]=new Joseround(i+1);//创建对象数组
length++;
}
}
void delete(int n){
for(int i=n;ilength-1;i++){
jo[i]=jo[i+1];
}
length--;
}
}
package Josephround;
import java.util.Scanner;
public class Text {
public static void main(String[] args) {
int m,n;
System.out.println("input m");
Scanner m1=new Scanner(System.in);
m=m1.nextInt();
System.out.println("input n");
Scanner n1=new Scanner(System.in);
n=n1.nextInt();
int temp=0;
int x=0;
Inijose joseph=new Inijose(n);
while(joseph.length!=0){
for(int i=1;i=m;i++){
joseph.jo[x].setflag(i);
if(joseph.jo[x].flagjo==m){
System.out.println(joseph.jo[x].sit);
joseph.delete(x);
x--;
}
if(xjoseph.length-1) x++;
else x=0;
}
}
}
}
public class TestJosephus {
public static void main(String[] args) {
//留几个人
int alive = 2;
//总人数
int total = 41;
//自杀者报数
int killMan = 3;
Josephus(alive, total, killMan);
}
/**
* @param alive 存活的人初始位置序号//留几个人
* @param total 总人数
* @param killMan 自杀者报数
*/
public static void Josephus(int alive, int total, int killMan) {
int []man = new int[total];
int count = 1;
int i = 0;
int pos = -1;
while (count = total) {
do {
pos = (pos+1)%total;
if (man[pos] == 0) {
i++;
}
if (i == killMan) {
i = 0;
break;
}
} while (true);
man[pos] = count;
System.out.print("第 " + (pos+1) + " 个人自杀！约瑟夫环编号为：" + man[pos]);
if (count % 2 != 0) {
System.out.print(" - ");
}else {
System.out.println(" -= ");
}
count++;
}
System.out.println();
System.out.println("这 " + alive +" 个需要存活的人初始位置应排在以下序号：");
alive = total - alive;
for (i = 0; i total; i++) {
if (man[i] alive) {
System.out.println("初始编号：" + (i+1) + "，约瑟夫环编号：" + man[i]);
}
}
System.out.println();
}
}
package 约瑟夫环;
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(Listperson list) {
int count = 0;
if (list != null) {
for (person p : list) {
if (p.state != 0) {
count++;
}
}
}
return count;
}
public void cacle() {
// 初始化数据
Listperson list = new LinkedListperson();
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();
}
}
跟这差不多的。
首先，这个代码输出的是，约瑟夫环到达的最后位置。输出结果是15。
//把iostream这个文件中的内容复制到这个地方。
#includeiostream
using namespace std;
int main()
{
//定义一个常量的整形100，表示人的个数。
const int n=100;
//定义约瑟夫环的参数。
int m=30;
//定义一个数组，用于计算约瑟夫环的位置。
int a[n];
//给数组赋值，让数组的每个值就是这个元素的编号。
for(int j=0;jn;j++)
a[j]=j+1;
//定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。
int k=1;
int i=-1;
while(1)
{
for(int j=0;jm;)
{
//不停的取数组的下一个元素。
i=(i+1)%n;
//如果这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下一个循环
if(a[i]!=0)
j++;
}
//如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。
if(k==n)
break;
//否则，把这个位置的元素设为零，标志它被排除。
a[i]=0;
//标志+1。
k++;
}
//输出约瑟夫环到达的最后一个位置。
couta[i]endl;
return 0;
}
