feezh

# re: [java經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

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


/**
* 遞歸算法實(shí)現(xiàn),改為非遞歸也非常easy
* @author 李佳
*
*/
public class E
{
// 存儲(chǔ)人員編號(hào) 1....N和報(bào)號(hào) (1,2,3)的對(duì)應(yīng)關(guān)系
private static TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>();
// 初始化 ,假設(shè)有100人
public static void inint()
{
for(int i=1;i<=300;i++)
{
// 直接模3后會(huì)是1,2,0,將0改為3.
tm.put(i, i%3==0?3:i%3);
}
}

/**
* 算法如下:
*
* 1 移除報(bào)號(hào)為3的人
* 2 如果只剩兩人,則結(jié)束
* 3 根據(jù)tm中最后一個(gè)人的報(bào)號(hào)M,重新計(jì)算每個(gè)人的報(bào)號(hào)
* 即第一個(gè)人為(M+1)%3,第二個(gè)人為(M+2)%3
* 4 重復(fù)第一步.
*
* 當(dāng)然最后剩下的兩人的報(bào)號(hào)肯定為1和2,若繼續(xù)下去的話,就是報(bào)號(hào)為2的那個(gè)人最終剩下.這一步我沒有寫
*/
public static void compute()
{
// 1 移除報(bào)號(hào)為3的人
Iterator<Map.Entry<Integer , Integer>> it = tm.entrySet().iterator();
while(it.hasNext())
{
if(it.next().getValue().equals(3))
{
it.remove();
}
}
// 2 如果只剩兩人,則結(jié)束
if(tm.size()<=2)
{
return;
}
// 3 根據(jù)tm中最后一個(gè)人的報(bào)號(hào)M,重新計(jì)算每個(gè)人的報(bào)號(hào)
// 即第一個(gè)人為(M+1)%3,第二個(gè)人為(M+2)%3
resort();
// 4 重復(fù)第一步.
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經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

@walnutprince
謝謝，學(xué)習(xí)了

# re: [java經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

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經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

@walnutprince
和我的想法完全一樣

# re: [java經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

下面那個(gè)遞歸resort方法有問題，如果剛好去除最后一個(gè)數(shù)，剩下的最后一個(gè)數(shù)的value是2的話，本來是1的第一個(gè)數(shù)會(huì)變成3被去除；需要加一個(gè)判斷在resort方法里。輸入的數(shù)大于等于7就會(huì)跟上一題不同的答案

# re: [java經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

@website design jp nagar
SB

# re: [java經(jīng)典算法題]有n個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù)（從1到3報(bào)數(shù)），凡報(bào)到3的人退出圈子，問最后留下的是原來第幾號(hào)的那位？  回復(fù)  更多評(píng)論   

謝謝分享！