关于约瑟夫杀人问题的算法—java语言描述(蕴含java思想)
前言:约瑟夫问题是一个经典的算法问题,它的大致描述是这样的,约瑟夫将军抓住N个俘虏,让他们排成一个圈,从第一个开始报数到第M开始杀掉,最后只剩下一个幸存者,问题的详情请看 百度百科详解 。
1.数据结构部分:
我们将问题抽象提取一下,首先我们需要一个节点来储存单个俘虏的信息,然后我们需要一个环状来表示所有的俘虏,然后再写算法,
2.算法部分:
算法具体实现:可以先用一个计数器,从开始遍历环开始计数,到计数器等于M时,进行删除节点。
3.代码构建:
由于是运用java语言描述,所以单独将节点和算法分别抽象成一个类
3.1构建节点类
public class Node {
//定义为私有属性便于便方法调用时好管理
private int value;//节点的值
private Node nextNode;//节点的指向(递归思想)
public Node(int value) {
this.value=value;
}
public Node() {
super();
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
}
3.2具体算法类
public class Joseph {
private static int MAXNUM;//俘虏总人数
private static int NUM;//从那个开始杀(M)
//提供有参构造方法方便用户自定义俘虏总人数,和M
public Joseph(int MAXNUM,int NUM) {
this.MAXNUM=MAXNUM;
this.NUM=NUM;
}
//算法的主要实现部分
public void kill() {
//构造链表(初始化链表)
Node head=new Node(1);
Node x=head;
for(int i=2;i<=MAXNUM;i++){
x.setNextNode(new Node(i));
x=x.getNextNode();
}
//使链表为循环链表
x.setNextNode(head);
while(x!=x.getNextNode()){
for(int i=1;i<NUM;i++){
x=x.getNextNode();
}
System.out.println("宝贝你被杀了哟:"+x.getNextNode().getValue());
//删除节点
x.setNextNode(x.getNextNode().getNextNode());
}
System.out.println("宝贝已经杀完了!!!你是最后的幸运儿哟:"+x.getValue());
}
}
3.3测试类
import java.util.Scanner;
public class TextMain {
public static void main(String[] args) {
System.out.println("请输入俘虏的总人数");
Scanner scanner=new Scanner(System.in);
int MAXNUM=scanner.nextInt();
System.out.println("请输入从第几个开始杀");
int NUM=scanner.nextInt();
Joseph joseph=new Joseph(MAXNUM,NUM);
joseph.kill();
}
}
3.4测试结果
点击链接到我的简书 我的简书
转载:https://blog.csdn.net/qq_41648647/article/details/102169947
查看评论