约瑟夫环问题

写了个约瑟夫环的实现，下边把代码分享出来，欢迎大家指点，或者有什么更好的设计思路欢迎提出。

 

我的设计思路是：定义一个linkedlist，删掉数到4的人，讲最后的余数放到链表的头部，然后再次对链表进行删除，这样不断的递归调用，完成谁是最后一个留下的！

 

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

/**
 * FileName ：LinkedListHigh.java
 * 
 * @CreateTime ：2011-5-16上午11:51:46
 * @author ： artemis
 * @function：
 */
public class LinkedListHigh {
	private static LinkedList<People> list = new LinkedList<People>();
	private static List<People> listxx = new ArrayList<People>();//存放被取出人员的顺序
	private final static int peopleNum = 4;//数到几出来
	int surplus = 0;//余数

	public static void main(String[] args) {
		addEntity();//向链表中加入人
		People people = getPeople(peopleNum);//得到最后出来的人
		System.out.println(people.getId() + "---" + people.getName());
		System.out.println("出队的顺序：");
		int i = 1;
		for (People p : listxx) {
			if (i < 7) {//只显示前6个出列人的顺序
				System.out.println("编号：" + p.getId() + "--------" + "姓名："
						+ p.getName());
				i++;
			} else {
				break;
			}
		}
	}

	private static People getPeople(int peopleNum) {
		int surplus;
		int removeNum;
		if (peopleNum == 1) {
			return list.getLast();
		}
		if (list.size() >= peopleNum) {//判断链表长度是否大于要取出的数
			surplus = list.size() % peopleNum;//求余
			removeNum = list.size() / peopleNum;//求整
			for (int i = 1; i <= removeNum; i++) {
				addList(peopleNum * i - 1);//把取出的人放进list中
			}
			for (int i = removeNum; i >= 1; i--) {
				list.remove(peopleNum * i - 1);//把取出的人从链表中删除
			}
			if (surplus != 0) {//如果有余数
				for (int j = 0; j < surplus; j++) {
					list.addFirst(list.pollLast());//把余下的放到链表的头部去
				}
			}
			getPeople(peopleNum);//递归自己，开始下一轮的删除链表的人员
		}
		list = getSurplusLink();//链表的长度小于要取出的数据
		return list.get(0);
	}

	private static LinkedList<People> getSurplusLink() {//删除剩下的数据
		if (list.size() > 1) {
			int yy = peopleNum % list.size();
			if (yy != 0) {
				addList(yy - 1);
				list.remove(yy - 1);

			} else {
				addList(list.size() - 1);
				list.remove(list.size() - 1);
			}
			getSurplusLink();
		}
		return list;
	}

	private static void addList(int index) {
		listxx.add(list.get(index));
	}

	private static void addEntity() {
		list.add(new People(1, "a"));
		list.add(new People(2, "b"));
		list.add(new People(3, "c"));
		list.add(new People(4, "d"));
		list.add(new People(5, "e"));
		list.add(new People(6, "f"));
		list.add(new People(7, "g"));
		list.add(new People(8, "h"));
		list.add(new People(9, "i"));
		list.add(new People(10, "j"));
		list.add(new People(11, "k"));
		list.add(new People(12, "l"));
		list.add(new People(13, "m"));
	}
}

class People {

	private int id;
	private String name;

	public People() {
	}

	public People(int id, String name) {
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
}