当前位置: 萬仟网 > IT编程>软件设计>面向对象 > 编程题:约瑟夫问题---面向对象版

编程题:约瑟夫问题---面向对象版

2021年01月15日  | 萬仟网IT编程  | 我要评论
/** * 约瑟夫问题是个有名的问题: * N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。 */public class Josephus { public static void main(String[] args) { Game.create(10, 3, 1).start(); } /** * 游戏 */ static class.

约瑟夫问题有很多变种,我们就选择其中一种吧,其它都是类似的。

N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。

咋一看,这不就是算法题嘛,搞个环形链表啥的。但是,如果使用面向对象的思维,就很简单了~~~ 

废话不说,我们抽象模型:整体上,这是一个游戏,有围圈人、最大叫号数、开始叫号人编号3个属性和开始游戏的行为。具体上,每个人有编号、左边的人、右边的人3个属性和叫号的行为。

1、围圈人

先看围圈的人,有编号、左边的人和右边的人三个属性,还有一个叫号的行为。重点是叫号,入参是叫号数和最大叫号数。逻辑是:

  • 如果右边的人是自己,说明只剩一个人了,游戏结束;
  • 如果叫号数是最大叫号数,那么出圈,修改左邻居右边的人和右邻居左边的人,并让右边的人从1开始叫号;
  • 否则,让右边的人叫下一个号。
    /**
     * 围圈人
     */
    static class Person {

        // 编号
        private int no;
        // 左边的人
        private Person leftPerson;
        // 右边的人
        private Person rightPerson;

        /**
         * 叫号
         *
         * @param callNum 叫号数
         * @param maxCallNum 最大叫号数
         */
        public void callNumber(int callNum, int maxCallNum) {
            if (rightPerson == this) {
                System.out.println("我是" + no + "号,只剩我了!");
                return;
            }
            if (callNum == maxCallNum) {
                // 出圈
                System.out.println("我是" + no + "号,我出圈了!");
                leftPerson.setRightPerson(rightPerson);
                rightPerson.setLeftPerson(leftPerson);
                rightPerson.callNumber(1, maxCallNum);
            } else {
                // 右边的人叫下一个号
                rightPerson.callNumber(callNum + 1, maxCallNum);
            }
        }

        public void setNo(int no) {
            this.no = no;
        }

        public void setLeftPerson(Person leftPerson) {
            this.leftPerson = leftPerson;
        }

        public void setRightPerson(Person rightPerson) {
            this.rightPerson = rightPerson;
        }
    }

2、游戏

现在来看游戏,属性有围圈人数组、最大叫号数int值、开始叫号人编号int值,并提供一个全参构造器。

此外,还有一个开始游戏的行为,执行时让指定编号的人叫1。

    /**
     * 游戏
     */
    static class Game {
        // 围圈人
        private Person[] people;
        // 最大叫号数
        private int maxCallNum;
        // 开始叫号人编号
        private int beginPersonNo;

        public Game(Person[] people, int maxCallNum, int beginPersonNo) {
            this.people = people;
            this.maxCallNum = maxCallNum;
            this.beginPersonNo = beginPersonNo;
        }

        /**
         * 开始游戏
         */
        public void start() {
            people[beginPersonNo - 1].callNumber(1, maxCallNum);
        }
    }

当然,这只是一个游戏模型,怎么新建一个游戏呢?我们提供一个游戏工厂,由它来负责创建游戏,很合理吧?

拥有一个创建游戏的行为大家没有意见吧。传入几个游戏参数,然后校验、构造围圈人并且维护环形的关系。

    /**
     * 游戏工厂
     */
    static class GameFactory {
        /**
         * 创建游戏
         *
         * @param personCount 围圈人数量
         * @param maxCallNum 最大叫号数
         * @param beginPerson 开始喊号人
         * @return 游戏
         */
        public static Game createGame(int personCount, int maxCallNum, int beginPerson) {
            // 校验参数
            if (beginPerson > personCount) {
                throw new IllegalArgumentException("开始号数不能大于人数");
            }
            // 创建围圈人数组
            Person[] people = new Person[personCount];
            for (int i = 0; i < personCount; i++) {
                people[i] = new Person();
            }
            // 设置围圈人关系
            for (int i = 0; i < personCount; i++) {
                Person person = people[i];
                person.setNo(i + 1);
                person.setLeftPerson(i == 0 ? people[personCount - 1] : people[i - 1]);
                person.setRightPerson(i == personCount - 1 ? people[0] : people[i + 1]);
            }
            return new Game(people, maxCallNum, beginPerson);
        }
    }

3、测试

来到最兴奋的环节了,就用文章开头那个例子吧,走你!

/**
 * 约瑟夫问题是个有名的问题:
 * N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
 */
public class Josephus {
    public static void main(String[] args) {
//        GameFactory.createGame(10, 3, 1).start();
        GameFactory.createGame(6, 5, 1).start();
    }
}

结果是对的。唉,就很舒服。

下面附上一个类装下的全部代码,当然实际别这么干🙂

/**
 * 约瑟夫问题是个有名的问题:
 * N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
 */
public class Josephus {
    public static void main(String[] args) {
        GameFactory.createGame(10, 3, 1).start();
        System.out.println("------------------我是最完美的分割线------------------");
        GameFactory.createGame(6, 5, 1).start();
    }

    /**
     * 游戏
     */
    static class Game {
        // 围圈人
        private Person[] people;
        // 最大叫号数
        private int maxCallNum;
        // 开始叫号人编号
        private int beginPersonNo;

        public Game(Person[] people, int maxCallNum, int beginPersonNo) {
            this.people = people;
            this.maxCallNum = maxCallNum;
            this.beginPersonNo = beginPersonNo;
        }

        /**
         * 开始游戏
         */
        public void start() {
            people[beginPersonNo - 1].callNumber(1, maxCallNum);
        }
    }

    /**
     * 游戏工厂
     */
    static class GameFactory {
        /**
         * 创建游戏
         *
         * @param personCount 围圈人数量
         * @param maxCallNum 最大叫号数
         * @param beginPerson 开始喊号人
         * @return 游戏
         */
        public static Game createGame(int personCount, int maxCallNum, int beginPerson) {
            // 校验参数
            if (beginPerson > personCount) {
                throw new IllegalArgumentException("开始号数不能大于人数");
            }
            // 创建围圈人数组
            Person[] people = new Person[personCount];
            for (int i = 0; i < personCount; i++) {
                people[i] = new Person();
            }
            // 设置围圈人关系
            for (int i = 0; i < personCount; i++) {
                Person person = people[i];
                person.setNo(i + 1);
                person.setLeftPerson(i == 0 ? people[personCount - 1] : people[i - 1]);
                person.setRightPerson(i == personCount - 1 ? people[0] : people[i + 1]);
            }
            return new Game(people, maxCallNum, beginPerson);
        }
    }

    /**
     * 围圈人
     */
    static class Person {

        // 编号
        private int no;
        // 左边的人
        private Person leftPerson;
        // 右边的人
        private Person rightPerson;

        /**
         * 叫号
         *
         * @param callNum 叫号数
         * @param maxCallNum 最大叫号数
         */
        public void callNumber(int callNum, int maxCallNum) {
            if (rightPerson == this) {
                System.out.println("我是" + no + "号,只剩我了!");
                return;
            }
            if (callNum == maxCallNum) {
                // 出圈
                System.out.println("我是" + no + "号,我出圈了!");
                leftPerson.setRightPerson(rightPerson);
                rightPerson.setLeftPerson(leftPerson);
                rightPerson.callNumber(1, maxCallNum);
            } else {
                // 右边的人叫下一个号
                rightPerson.callNumber(callNum + 1, maxCallNum);
            }
        }

        public void setNo(int no) {
            this.no = no;
        }

        public void setLeftPerson(Person leftPerson) {
            this.leftPerson = leftPerson;
        }

        public void setRightPerson(Person rightPerson) {
            this.rightPerson = rightPerson;
        }
    }
}

 

本文地址:https://blog.csdn.net/qq_31142553/article/details/112625232

如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!

相关文章:

  • 2019 OO第一单元总结(表达式求导)

    2019 OO第一单元总结(表达式求导)

    一. 基于度量的程序结构分析 1. 第一次作业 这次作业是我上手的第一个java程序,使用了4个类来实现功能。多项式采用两个arraylist来存,... [阅读全文]
  • __str__,__repr__

    __str__,__repr__

    [TOC] \_\_str\_\_ 打印时触发 {'a': 1} obj和dic都是实例化的对象,但是obj打印的是内存地址,而dic打印的是有用的... [阅读全文]
  • 依赖倒置原则——面向对象设计原则

    一、定义依赖倒置原则的原始定义为:高层模块不应该依赖低层模块,两者都应该依赖其抽象;抽象不应该依赖细节,细节应该... [阅读全文]
  • Java基础学习总结——super关键字

    一、什么是super? 它是一个指代变量,是直接父类对象的引用,用于在子类中指代父类对象。 二、应用 2.1 应用范围 只能用于子类的构造函数和实例方法... [阅读全文]
  • fastRPC服务使用

    现在出现了很多中间件解决跨语言问题,使用RPC远程调用;但是庞大是个问题,而且要按照格式使用。尤其是源码量比较庞大。 为了简单易用,我采用订阅发布模... [阅读全文]
  • Python 环境搭建

    Python 环境搭建

    当前环境:Windows 7 64位 ps:本博客都是基于Windows,Linux请绕行~ 1.下载Python 安装包 官网地址 选择适合自己的... [阅读全文]
  • springmvc注解@Controller和@RequestMapping

    Spring从2.5版本引入注解,从而让开发者的工作变得非常的轻松 springmvc注解Controller org.springframewor... [阅读全文]
  • C#:继承过程中的静态成员

    C#:继承过程中的静态成员

    在知乎上看到一个关于“泛基“的实现,感觉挺有意思,想试试效果,代码如下: 先忽略这段代码的作用,重点是运行后控制台没有任何输出。跟踪一下发现根本没有... [阅读全文]
  • 个人博客

    个人博客:www.gorpeln.com Github上的代码添加Cocoapods支持 短信验证码防刷机制 Chrome插件 整站下载工具httr... [阅读全文]
  • 1.ESP8266-简单的类和对象

    ESP8266面向对象编程之简单的类和对象创建一个类(class)的方法:class Led // ... [阅读全文]
验证码:
Copyright © 2017-2021  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com