约瑟夫环

约瑟夫环是一个数学的应用问题：已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。

def josephus(seq, k, m):
    k , m = k-1, m-1
    if k > len(seq) or k < 0:
        raise ValueError("The argument k error.")
    result = []
    for i in range(len(seq)):
        k = (k + m) % len(seq)
        result.append(seq.pop(k))
    return result

a = [1,2,3,4,5,6]
print josephus(a,1,3)

 

 

 

package com.tim4lover.test.service;

import java.util.ArrayList;
import java.util.List;

class Node {
	private int index;
	private Node next;
	public Node(int index) {
		this.index = index;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	@Override
	public String toString() {
		return String.valueOf(index);
	}
}

public class Josephus {
	private List<Node> nodes = new ArrayList<Node>();
	public Josephus(int n) {
		for(int i=1; i<=n; i++) {
			Node node = new Node(i);
			push(node);
		}
	}
	public void push(Node node) {
		if(nodes.size()== 0) {
			node.setNext(node);
			nodes.add(node);
		}else {
			nodes.get(nodes.size()-1).setNext(node);
			node.setNext(nodes.get(0));
			nodes.add(node);
		}
	}
	public void pull(Node node) {
		if(nodes.size()>1) {
			int pre = nodes.indexOf(node);
			if(pre==0) {
				pre = nodes.size();
			}
			Node node_pre = nodes.get(pre-1);
			node_pre.setNext(node.getNext());
			nodes.remove(node);
		}else {
			nodes.remove(node);
		}
		System.out.println(nodes);
		System.out.println(node);
	}
	public List<Integer> output(int m) {
		List<Integer> result = new ArrayList<Integer>();
		Node node = null;
		if(nodes.size()!=0) {
			node = nodes.get(0);
		}
		while(nodes.size()!= 0) {
			for(int i=0; i<m; i++) {
				node = node.getNext();
			}
			pull(node);
			result.add(node.getIndex());
		}
		return result;
	}
	public static void main(String[] args) {
		Josephus jos = new Josephus(10);
		List<Integer> result = jos.output(2);
		System.out.println(result);
	}
}