约瑟夫环的解法

分手后的思念是犯贱 2023-10-05 22:21 4阅读 0赞

解法一：顺序表ArrayList

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

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

解法三：

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