编程题：约瑟夫问题---面向对象版
程序员文章站
2022-06-10 15:06:03
/** * 约瑟夫问题是个有名的问题： * 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