feezh

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;


/**
* 递归算法实现,改为非递归也非常easy
* @author 李佳
*
*/
public class E
{
// 存储人员编号 1....N和报号 (1,2,3)的对应关系
private static TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>();
// 初始化 ,假设有100人
public static void inint()
{
for(int i=1;i<=300;i++)
{
// 直接模3后会是1,2,0,将0改为3.
tm.put(i, i%3==0?3:i%3);
}
}

/**
* 算法如下:
*
* 1 移除报号为3的人
* 2 如果只剩两人,则结束
* 3 根据tm中最后一个人的报号M,重新计算每个人的报号
* 即第一个人为(M+1)%3,第二个人为(M+2)%3
* 4 重复第一步.
*
* 当然最后剩下的两人的报号肯定为1和2,若继续下去的话,就是报号为2的那个人最终剩下.这一步我没有写
*/
public static void compute()
{
// 1 移除报号为3的人
Iterator<Map.Entry<Integer , Integer>> it = tm.entrySet().iterator();
while(it.hasNext())
{
if(it.next().getValue().equals(3))
{
it.remove();
}
}
// 2 如果只剩两人,则结束
if(tm.size()<=2)
{
return;
}
// 3 根据tm中最后一个人的报号M,重新计算每个人的报号
// 即第一个人为(M+1)%3,第二个人为(M+2)%3
resort();
// 4 重复第一步.
compute();
}
public static void resort()
{
// resort
int last = tm.lastEntry().getValue();
Iterator<Map.Entry<Integer , Integer>> it = tm.entrySet().iterator();

while(it.hasNext())
{
last++;
it.next().setValue(last%3==0?3:last%3);
}
}
public static void display()
{
System.out.println(tm);
}
public static void main(String[] adfafd)
{
inint();
compute();
display();
}

}

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

@walnutprince
谢谢，学习了

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

Valuable information ..I am delighted to read this article..thank you for giving us this useful information. Great walk-through. I value this post.!!

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

@walnutprince
和我的想法完全一样

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

下面那个递归resort方法有问题，如果刚好去除最后一个数，剩下的最后一个数的value是2的话，本来是1的第一个数会变成3被去除；需要加一个判断在resort方法里。输入的数大于等于7就会跟上一题不同的答案

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

@website design jp nagar
SB

# re: [java经典算法题]有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？  回复  更多评论   

谢谢分享！