面接プログラミング問題収集
1:N人が1周して、最初の人は1から数えて、Mに報告した人が列を出して、最後の列を出した人を求めて、ジョセフ環の問題.
最も簡単ですが、最も分かりにくい方法:
f(1,m)=0 f(n,m)=(f(n-1,m)+m)%n
public void testTest() {
String[] people = { "1", "2", "3", "4", "5" };
int M = 10;
int length;
int m;
while ((length = people.length) != 1) {
// 5 ， 9，
if (M > length) {
// ，
m = M % length == 0 ? length : M % length;
} else {//
m = M;
}
String[] temp = new String[length - 1];
// m ， m 1 ,
// m-1 0 ， 1 , m
// 5 ， 4 ， 5 1， 4 1， 1
System.arraycopy(people, m, temp, 0, length - m);
// 5 ，4 ， 5 ， 1，2，3
System.arraycopy(people, 0, temp, length - m, m - 1);
// ，
people = temp;
}
System.out.println(people[0]);
}最も簡単ですが、最も分かりにくい方法:
f(1,m)=0 f(n,m)=(f(n-1,m)+m)%n
public int find(int n, int m)
{
int r = 0;
for (int i = 2; i <= n; i++) {
r = (r + m) % i;
}
return r + 1;
}