求解约瑟夫环问题(Java)

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(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()

}

}

跟这差不多的。

用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=0i<xi++){

            jo[i]=new Joseround(i+1)//创建对象数组

            length++

        }

    }

    void delete(int n){

        for(int i=ni<length-1i++){

            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=1i<=mi++){

                joseph.jo[x].setflag(i)

                if(joseph.jo[x].flagjo==m){

                  巧尺明  System.out.println(joseph.jo[x].sit)

                    joseph.delete(x)

                    x--

                }

                if(x<joseph.length-1) x++

                else x=0

            }

        }

         

    }

 

}

import java.util.*

public 闭笑渣class Sefu {

public static void main(String[] args) {

int N// 总人数

int M// 从第M个人开始

int S// 隔S个人出局

Scanner reader = new Scanner(System.in)

System.out.print("请输入N:")

N = reader.nextInt()

System.out.print("请输入M:")

M = reader.nextInt()

System.out.print("请输入S:")

S = reader.nextInt()

int[] a = new int[N]

for (int h = 1 h <= N h++) {

a[h - 1] = h

System.out.print(a[h - 1] + " ")

}

System.out.println()

int count

M = M - 1// 转成下标

for (int j = 1 j <= N j++) {

count = 1// 从1开始报数

while (count != S) {// 如果没有报到S就继续报数

if (a[M] != 0) {// 如果没出局就报数

count++//报数

for (int i = 1 i < N i++) {

//然后找下一个（从+1开始找）要报数的人

if (M + i < N) {

//如果M+i没到最后一位

if (a[M + i] != 0) {

//判断是否出局

M = M + i

//没出局就是从这个人开始了

break

//不要找了

}else{

continue

//出局了就i++，看下一个人有没有出局

}

}else{

if (a[M + i-N] != 0) {

//如果M+i过了最后一位，就-N，相当于转了一个圈回到前面

M = M + i-N

//没出局就从M+i-N开始报数

break

}else{

continue

}

}

}

} else {// 如果出局了就跳过找下一个要报数的人

if (M + 1 < N) {

M++

} else {

M = 0

// 如果M+1==N就从下标0开始找数组的值不是0的数

continue

}

continue// 如果是0就继续

}

}

// 如果报数报到S

System.out.print(a[M] + " ")// 出局

int out=M//下标为out的出局了

for (int i = 0 i < N i++) {//找下一个要报数的人

if (M + i < N) {//如果M+i没到最后一位

if (a[M + i] != 0) {//判断是否出局

M = M + i

break

}else{

continue//出局了就i++从下一个开始

}

}else{

if (a[M + i-N] != 0) {

//如果M+i过了最后一位，就-N，相当于转了一个圈回到前面

M = M + i-N

break

}else{

continue

}

}

}

a[out]=0//出局的设为0

}

}

}

//写完发现我定义的S和M和你定义的是反过来的，不是最好的算法。

//可以把找下一个轿悄人的方法抽出来，写成一个方法

//输入一个数组a，找第M个人的下一个人，输出下一个人升绝的下标。

import java.util.*

public class Sefu {

public static void main(String[] args) {

int N// 总人数

int M// 从第M个人开始

int S// 隔S个人出局

Scanner reader = new Scanner(System.in)

System.out.print("请输入N:")

N = reader.nextInt()

System.out.print("请输入M:")

M = reader.nextInt()

System.out.print("请输入S:")

S = reader.nextInt()

int[] a = new int[N]

for (int h = 1 h <= N h++) {

a[h - 1] = h

System.out.print(a[h - 1] + " ")

}

System.out.println()

int count

M = M - 1// 转成下标

for (int j = 1 j <= N j++) {

count = 1// 从1开始报数

while (count != S) {

// 如果没有报到S就继续报数

count++// 报数

M=getNext(a, M)

//找下一个没出局（不为0）的数

}

// 如果报数报到S

System.out.print(a[M] + " ")// 出局

a[M]=0

M=getNext(a, M)//找下一个没出局的数

}

}

/**

 * 得到下一个数的下标

 * @param a

 * @param M

 * @return

 */

public static int getNext(int[] a, int M) {

for (int i = 1 i < a.length i++) {

if (M + i < a.length) {

if (a[M + i] == 0) {

//如果下一个数的值为0就继续找

continue

} else {

M=M+i

return M

//如果下一个数的值不为0就是这个数。

}

}else{

if (a[M + i-a.length] == 0) {

//如果下一个数的值为0就继续找

continue

} else {

M=M+i-a.length

return M

//如果下一个数的值不为0就是这个数。

}

}

}

return -1

}

}

//一不小心又帮你改好了~

---