约瑟夫环的解法

解法一：顺序表ArrayList

代码语言：javascript复制

import java.util.ArrayList;
import java.util.Scanner;


public class Josephproblem {
    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        Scanner zs = new Scanner(System.in);
        //打印
        System.out.print("输入总人数：");
        int m = zs.nextInt();
        //打印
        System.out.print("输入剔除的序号：");
        int n = zs.nextInt();
        josephus(m, n);
    }

    public static void josephus(int n, int m) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 1; i <= n; i  ) {
            arrayList.add(i);
        }
        ArrayList<Integer> arr = new ArrayList<>();
        int count = 1;
        while (arrayList.size() >= 1) {
            if (count == m) {
                count = 1;
                arr.add(arrayList.remove(0));
            } else {
                arrayList.add(arrayList.remove(0));
                count  ;
            }
        }
        //打印
        System.out.print("输出的约瑟夫数是："   arr.toString());
    }
}

解法二：LinkedList

代码语言：javascript复制

import java.util.LinkedList;
import java.util.Scanner;

public class Joseph_problem {
    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        Scanner zs = new Scanner(System.in);
        //打印
        System.out.print("输入总人数：");
        int m = zs.nextInt();//
        //打印
        System.out.print("输入剔除的序号：");
        int n = zs.nextInt();
        josephus(m, n);
    }

    //判断是否为约瑟夫数
    public static void josephus(int m, int n) {
        //创建list集合存放人数的序号
        LinkedList list = new LinkedList();
        //创建list1集合存放约瑟夫数
        LinkedList list1 = new LinkedList();
        //把序号添加到list集合中
        for (int i = 1; i <= m; i  ) {
            list.add(i);
        }
        int count = 1;//报数，1开始报数
        //循环list集合是否还有元素
        while (list.size() >= 1) {
            if (count == n) {   //判断count==n时，做出记录操作
                count = 1;    //等于时就重新赋值为1
                list1.add(list.removeFirst()); //移除并返回此列表中的第一个元素，并且添加带辛几何中
//                continue;
            } else {
                list.add(list.removeFirst());///把不是约瑟夫数的序号往后添加
                count  ;//报数加1
            }
        }
        //打印，约瑟夫数
        System.out.print("输出的约瑟夫数是："   list1);
    }
}

解法三：

代码语言：javascript复制

import java.util.Scanner;

//顺序表实现约瑟夫数
public class sequence_table {
    private int initcapacity = 10;//初始容量
    private int size;//顺序表元素的长度
    private Object[] data;//存储数据
    Scanner zs = new Scanner(System.in);

    //重载构造器
    public sequence_table() {
        data = new Object[initcapacity];
        this.size = 0;
    }

    //扩容
    public void expansion(int new_capacity) {
        Object[] date1 = new Object[new_capacity];//定义新的顺序表存储数据
        //拷贝数据到原顺序表中
        for (int i = 0; i < size; i  ) {
            date1[i] = data[i];
        }
        //重新定义容量
        initcapacity = new_capacity;
        //把新顺序表赋给原顺序表
        data = date1;
    }

    //添加元素
    public void add() {
        //打印
        System.out.print("输入总人数：");
        int n = zs.nextInt();
        //打印
        System.out.print("原来排序的序号：");
        for (int i = 0; i < n; i  ) {
            if (size == initcapacity) {
                expansion(size * 2);
            }
            data[size  ] = i   1;
            System.out.print(data[i]   " ");
        }
        //打印
        System.out.println();
    }

    //判断约瑟夫数
    public void josephus() {
        int t = 0, m = 0;//t 为数组下标，m是需要出列的数字，比如数到3出列，
        //输入需要出列的数字
        //打印
        System.out.print("输入要求出列的序号：");
        m = zs.nextInt();
        if (m > size) {
            throw new IllegalArgumentException("要求出列的序号不在总人数内！");//提示错误！
        } else {
            System.out.print("出列顺序为: ");
            for (int k = size; k >= 1; k--) {
                t = (t   m - 1) % k; //通过数组下标查找出列的元素
                //打印
                System.out.print(data[t]   " ");//输出出队的元素
                for (int j = t   1; j <= k - 1; j  )//顺序表删除操作
                    data[j - 1] = data[j];
            }
        }
    }
}
//测试类
class Test {
    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        sequence_table l = new sequence_table();
        l.add();
        l.josephus();
    }
}

arraylist linkedlist

0 人点赞