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的人退出圈子，問最后留下的是原來第幾號的那位？  回復  更多評論   

謝謝分享！