假设一共有N只猴子。从第一只猴子开始报数。其中报到数字n的猴子离开。然后下一只猴子仍然从一开始报起。。当报完最后一只猴子时。第一只猴子接着最后一只猴子报数。请问最后留下的猴子是第几只?
例如一共有4只猴子。报到3的猴子离开。
那么首先第3只猴子离开。第4只猴子报1。接着第一只猴子继续报2。第二只猴子报3离开。第四只猴子报1。第一只猴子报2。第四只猴子报3。
结果就是第一只猴子留下。这个问题很简单啊。。希望大家写出最简单的算法啊。。
例如一共有4只猴子。报到3的猴子离开。
那么首先第3只猴子离开。第4只猴子报1。接着第一只猴子继续报2。第二只猴子报3离开。第四只猴子报1。第一只猴子报2。第四只猴子报3。
结果就是第一只猴子留下。这个问题很简单啊。。希望大家写出最简单的算法啊。。
楼主列出的例子,在我的程序里面就是 numMonkey = 4,leaveSignal = 3;startPos=0
int numMonkey = 4, leaveSignal = 3, monkeyCount = numMonkey;
int[] monkeys = new int[numMonkey];
int startPos = 0;
while (true) {
int counter = 0, index = 0;
for (int i = 0; i < monkeys.length; i++) {
if (monkeys[i] == 0) {
counter++;
index = i;
}
}
if (counter == 1) {
System.out.println("第 " + (index + 1) + " 只猴子剩下了.");
break;
}
// kick one monkey out
for (int i = startPos, c = 0;; i = (i + 1) % monkeys.length) {
if (monkeys[i] == 0) {
c++;
if (c >= leaveSignal) {
monkeys[i] = 1;
for (int j = (i + 1) % monkeys.length;; j = (j + 1) % monkeys.length) {
if (monkeys[j] == 0) {
startPos = j;
break;
}
}
break;
}
}
}
}
public class Sandys{
public static String lastMonkey(int N,int n)
{
int pos=n;
Vector v=new Vector();
for(int i=0;i<N;i++)
{
v.addElement("monkey"+" "+(i+1));
}
while(v.size()>1)
{
v.removeElementAt(pos-1);
pos=(n<=(v.size()+1-pos))?(pos+n-1):
((n-v.size()+pos-1)<=v.size()?
(n-v.size()+pos-1):((n-v.size()+pos-1)%v.size()));
}
return (String)v.elementAt(0);
}
public static void main(String args[])
{
System.out.println(lastMonkey(8,4));
}
}
有问题请指正