约瑟夫环问题-LinkedList+HashMap实现

题目：


据说著名犹太历史学家 约瑟夫有过以下的故事：
在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫 和他的朋友并不想遵从，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

我的答案：

import java.util.*;

/**
 * 约瑟夫环问题
 *
 * @author user
 *
 */
public class Test {
 public static void main(String[] args) {
  LinkedList people = new LinkedList();

 

  // 添加数据
  for (int i = 1; i <= 41; i++) {
   people.add(i);
  }

 

  // 遍历输出
  while (people.size() > 2) {
   Map mp = new HashMap(); // 存放临时数据
   int m = people.size() % 3; // 取余

 

   int k; // 循环次数
   if (people.size() % 3 == 0) {
    k = people.size() / 3;
   } else {
    k = people.size() / 3 + 1;
   }

 

   // 以3个数据单位分割，不足三时算另外的
   for (int i = 0; i < k; i++) {
    List ls = new LinkedList();
    if (i * 3 + 3 <= people.size()) {
     ls = people.subList(i * 3, i * 3 + 3);
    } else {
     ls = people.subList(i * 3, i * 3 + people.size() % 3);
    }
    mp.put(i, ls);
   }

 

   // 移除集合大小为3的最后一项
   for (int i = 0; i < mp.size(); i++) {
    List mList = new LinkedList();
    mList = (List) mp.get(i);
    if (mList.size() == 3) {
     System.out.println("自杀：" + mList.get(mList.size() - 1));
     // mList.remove(mList.size() - 1); //remove方法在此不好用，会出错
     mList = mList.subList(0, mList.size() - 1);
     mp.put(i, mList);
    }
   }

 

   people = new LinkedList(); // 初始化数据

 

   //重新组合数据
   for (int i = 0; i < mp.size(); i++) {
    List mList = new LinkedList();
    mList = (List) mp.get(i);
    for (int j = 0; j < mList.size(); j++) {
     people.add(mList.get(j));
    }
   }

 

   //排列数据，以便下次执行
   for (int i = 0; i < m; i++) {
    Object obj = people.getLast();
    people.remove(people.getLast());
    people.addFirst(obj);
   }

 

   System.out.println("活下来的人数：" + people.size());
   System.out.println(people + "\n");
  }
 }
}

http://hi.baidu.com/wuxyy/blog/item/464471f03802fcafa40f523c.html

public class Live{
 public static void main(String[] args){
  int n = 41;
  int[] ary = new int[41];
  int i = 1;
  int j = 1;
  while(n>2){
   j = 1;
   while(j<4){
    if(ary[i-1] == 0){
     if(j == 3){
      ary[i-1] = 1;
      System.out.println("编号为" + i + "的人自杀");
     }
     j++;
    }
    if(i == 41){
     i = 1;
    }else{
     i++;
    }
   }
   n--;
  }
  //最后结果
  String result = "";
  for(i = 1; i <= 41; i++){
   if(ary[i-1] == 0)
    result += i + "和";
  }
  System.out.println("最后存活的人编号为" + result.substring(0,result.length()-1));
 }
}

这个算法的实际应用领域是什么？可否举几个例子呢？

兄台的代码 比较好 学习了