算法小试牛刀

假设一共有N只猴子。从第一只猴子开始报数。其中报到数字n的猴子离开。然后下一只猴子仍然从一开始报起。。当报完最后一只猴子时。第一只猴子接着最后一只猴子报数。请问最后留下的猴子是第几只？
例如一共有4只猴子。报到3的猴子离开。
那么首先第3只猴子离开。第4只猴子报1。接着第一只猴子继续报2。第二只猴子报3离开。第四只猴子报1。第一只猴子报2。第四只猴子报3。
结果就是第一只猴子留下。

这个问题很简单啊。。希望大家写出最简单的算法啊。。

14 个解决方案

#1

又是数学题,搞竞赛的小学生都会做.

#2

不好意思,看错了题,跟约瑟夫环有点类似.

#3

mark

#4

就是约瑟夫环问题，可以用链表或者数组来实现；
你在网上搜索：约瑟夫环，会出来一大堆的

#5

一个地归算法

#6

numMonkey 是猴子的数量,leaveSignal是报数的数量,startPos 是开始报数的猴子的编号,我用的是数组的编号所以从零开始
楼主列出的例子,在我的程序里面就是 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;
}
}
}
}

#7

大家互相交流一下,如果有错误,希望大家指正,谢谢.

#8

import java.util.Vector;
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));
    }
}

#9

我的理解就是找出要离开的那只猴子的POS
有问题请指正

#10

好,我说tianwill,^_^

#11

我记得这是原来计算机二级的一道类似的题,我没什么长进,当时是那么做的,现在还是这么做,试题的答案是tianwill类似的做法,当时觉得那个好复杂就没看,现在引入了一个Vector就清晰多了,学习,谢谢.

#12

封装真好

#13

约瑟夫

java算法书上有的

#14

呵呵。。不错啊。。该给分了

#1