关于约瑟夫杀人问题的算法—java语言描述（蕴含java思想）

关于约瑟夫杀人问题的算法—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测试结果

点击链接到我的简书 我的简书