日期:2014-05-20  浏览次数:20674 次

菜鸟“约瑟夫环问题”的不解之处,恳请各位高人能对小弟给予指点,拜谢!~~
题目的意思:设有N个人围坐一圈并按顺时针方向从1到N编号,从第S个人开始进行1到M报数,报数到第M的人出圈,再从他的下一个人重新开始从1到M报数,如此进行下去,每次报数到M的人就出圈,知道所有人都出圈为止。给出这N个人的出圈顺序。
代码如下:
public class Count5Quit1 {
public static void main(String[] args) {
final int N = 13;         //总人数N
final int S = 3;          //从第S个人开始报数
final int M = 5;          //报数到M的人出圈
int[] p = new int[N];
int i,w,s,j;
for(i=1; i<=N; i++)
p[i-1] = i;            //对每个人进行编号
s = S;
for(i=N; i>=1; i--){       //总人数为N,一次减1
s = (s + M - 1) % i;   //计算下一个开始报数人的位置
if(s == 0)
s = i;             //最后一个人出圈的位置存入变量s中
w = p[s - 1];          //讲出圈人的编号保存到变量w中
for(j=s; j<=i-1; j++)  //从s位置开始,数组的内容依次前移
p[j-1] = p[j];
p[j-1] = w;            //讲w存入到空的位置中
}
System.out.print("出圈人的顺序为:");
for(i=p.length-1; i>=0; i--)
    System.out.print(p[i]+"  ");
}
}
以上:在p[j-1] = w行中,小弟看不懂,j这个变量没有进行初始化,为什么还能进行j-1操作。在调试的时候,将j-1换成i-1,输出结果和j-1的结果一致。
疑问:p[j-1] = w 和 p[i-1] = w有什么区别,困扰了好久依然不懂,希望各位高人能给小弟指点迷津。谢谢

------解决方案--------------------
引用:
……
以上:在p[j-1] = w行中,小弟看不懂,j这个变量没有进行初始化,为什么还能进行j-1操作。在调试的时候,将j-1换成i-1,输出结果和j-1的结果一致。
疑问:p[j-1] = w 和 p[i-1] = w有什么区别,困扰了好久依然不懂,希望各位高人能给小弟指点迷津。谢谢


第一个问题
j这个变量初始化了,在这行
         for(j=s; j<=i-1; j++)  //从s位置开始,数组的内容依次前移
j初始化为s;

第二个问题:
for (j = s; j <= i - 1; j++) // 
  p[j - 1] = p[j];

// 这里注意 for 的条件 j<=i-1;
// 这意味着for循环执行的结果,j 等于 i;

p[j - 1] = w; 


所以你的观察不错,p[j-1] = w 和 p[i-1] = w没有区别