面试题是来自一个具有一定规模的IT公司面试题真题，现分享给大家，供大家学习交流，探讨解题思路！
题目：
      现有50个数字，放在一个数组中，a[0],a[1],a[2],a[3]..............a[49]，将他们绕城一个圈排列，从1开始，每到第3个数字，即去除，这样循环往复，一直到最后，现在要求通过一段程序，来求出最后一个剩下的数字是多少?

这道题利用LinkedList比较方便
public class Test {
/**
  * @param args
  */
public static void main(String[] args) {
  Integer[]arr=new Integer[50];
  for(int i=0;i<50;i++){
   arr[i]=i+1;
  }
  System.out.println("最后一个剩余的位置："+test(arr,3));
  
}
public static int test(Integer[]arr,int k){
  //然后把这个数组编程一个链表集合
  LinkedList<Integer>list=new LinkedList<Integer>(Arrays.asList(arr));
  //定义一个整形
  int n=-1;
  while(list.size()>1){
   n=(n+k)%list.size();
   list.remove(n--);
  }
  return list.get(0).intValue();
}
}

这个就是循环套循环，理清思路画画图应该能解出来！

这个就是循环套循环，理清思路画画图应该能解出来！

//此题为经典的约瑟夫环问题，没有用LinkedList
public class x
{
        static int josephus(int N,int K)
        {
            int alive=0;//1个人的话，最后活下的编号是0号
            for (int i=2;i<=N;i++)//从第2个人开始循环
                alive=(alive+K)%i;
            return alive;
        }
        public static void main(String []args)
        {
               
                Integer[]arr=new Integer[50];
                for(int i=0;i<50;i++)
                {
                        arr[i]=i+1;
                }
                System.out.println(arr[josephus(50,3)]);
        }
}

针对你这个题，50个人，数到3退出，最后剩下编号为11号的人。即数组中第10号元素。

许晓华 发表于 2012-12-15 23:51
针对你这个题，50个人，数到3退出，最后剩下编号为11号的人。即数组中第10号元素。 ...

你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i<=N;i++)//从第2个人开始循环
                 alive=(alive+K)%i;
是在做什么呢？望解答:loveliness:

张辉2012 发表于 2012-12-16 12:57
你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i ...

约瑟夫环问题(Josephus)
•编号为0~N-1的N个人围成一个圈，从0开始数到k-1的被杀，求最后留下来的一个人的最初编号。

•设N个人的约瑟夫环问题的解是f(N)，即最后活下来的人的编号。以N=10，k=3为例

•  0  1   2   3  4  5  6  7  8  9  

• 7  8    ☻  0  1  2  3  4  5  6

•第一个数到k-1的人其编号(k-1)%N

•从编号为k%N的人开始，剩下的N-1个人又组成了一个新的f(N-1)的约瑟夫环问题：即

•f(N)=(f(N-1)+k%N)%N

•即f(N)=(f(N-1)+k)%N(递归表达式)

•已知f(1)=0

•根据递归表达式可知：

•f(2) =(f(1)+k)%2

•f(3) =(f(2)+k)%3

•f(4)=(f(3)+k)%4

•……

•可得出我程序中的递推公式

java是面向对象的，为什么用面向对象呢.....
//面对对象，先不考虑算法，先考虑这个问题中有哪些类，类中有哪些属性和算法
//把每个数看成一个对象（Kid)，一个圈（双向链表，KidCircle）
public class Count3Quit2 {
   public static void main(String args[]){
           KidCircle kc=new KidCircle(50);
           int countNum=0;
           Kid k=kc.first;
           while(kc.count>1){
                   countNum++;
                   if(countNum==3){
                           countNum=0;
                           kc.delete(k);
                           
                   }
                   k=k.right;
           }
           System.out.println(kc.first.id);
   }
}
class Kid{
        int id;//每一个孩子给一个id
        Kid left;//这个孩子的左边和右边那个孩子
        Kid right;
}
class KidCircle{
        int count=0;
        Kid first,last;//开始的一个孩子，和结束的一个孩子
        KidCircle(int n){//构建一个有n个数的圈
                for(int i=0;i<n;i++){
                        add();
                }
               
        }
        void add(){//添加一个孩子
        Kid k=new Kid();
        k.id=count;
        if(count<=0){
                first=k;
                last=k;
                k.left=k;
                k.right=k;
               
        }else {
                last.right=k;//最后一个孩子右手等于新添加的孩子
                k.left=last; //这个孩子的左手等最后那个孩子
                k.right=first;//这个孩子的右手等第一个孩子
                first.left=k;//第一个孩子 的左手等刚添加的这个孩子
                last=k;//这个上孩子变成了最后一个孩子
        }
        count ++;
        
        }
        void delete(Kid k){//删除一个孩子
                if(count <=0){
                        return;
                }else if(count==1){
                        first=last=null;
                }else{
                        k.left.right=k.right;//k左边这个孩子的右手拉住了k右边个人
                        k.right.left=k.left;//k右边个孩子的左手拉住了k左边这个人
               
                        if(k==first){//如果k为第一孩子
                                first=k.right;//K右边那孩子为变为第一个孩子
                        }else if(k==last){//如果K为最后一个人
                                last=k.left;//K左边那个孩子变为最后一个
                        }
                        
                }
                count--;
        }
}

张辉2012 发表于 2012-12-16 12:57
你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i ...

这是不是高数呀

熊永标 发表于 2012-12-25 11:34
这是不是高数呀

呵呵 不太清楚啊 貌似上学的时候不记得高数中有约瑟夫环

学习一下，感谢分享！

这是我遇到的类似的题分享下

package com.itheima;
import java.util.*;
/**
* 第十题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
* 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中
* 的第几个人？
*/
public class Test10 {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub                        
                    ArrayList first = new ArrayList();     //定义集合为first
                int number = 14;                        //每次报数的点
                for (int i=1;i<=100 ;i++ )  //在集合加入1~100
                {
                        first.add(i);
                }
                sop(first);
                sop(first.size());
                Count(first,number);                //开始计算
                sop(first);
                sop(first.size());
        }
        private static ArrayList Count(ArrayList arl,int num)
        {
                for (int x=arl.size(); x>=num; x--)//一次一次报数
                {
                        arl.remove(num-1);                                //每到14时踢掉一个
                        ArrayList changeCollection = new ArrayList();//定义另一个集合用来装下first中的前13个数
                        for (int a = 0;a<num-1 ;a++ )  //把first中的前13个数装在changeCollection中，并且删掉first内部的前13个数
                        {
                                changeCollection.add(arl.get(0));
                                arl.remove(0);
                        }
                        for (int a =0;a<num-1 ; a++)//把changeCollection中的数重新放入first中，并且放在最后
                        {
                                arl.add(changeCollection.get(a));
                        }
                }
                return arl;
         }
        public static void sop(Object obj){
                System.out.println(obj);
        }
}
                        // 输出结果：
                        // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
                        // , 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                        // 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
                        // 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77,
                        // 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96,
                        // 97, 98, 99, 100]
                        // 100
                        // [16, 29, 36, 39, 47, 55, 72, 74, 75, 80, 90, 91, 92]
                        // 13
                        // 最终剩下的人：16, 29, 36, 39, 47, 55, 72, 74, 75, 80, 90, 91, 92

加油。好好奋斗。加油

考虑考虑考虑考虑考加减

public class x
{
        static int josephus(int N,int K)
        {
            int alive=0;//1个人的话，最后活下的编号是0号
            for (int i=2;i<=N;i++)//从第2个人开始循环
                alive=(alive+K)%i;
            return alive;
        }
        public static void main(String []args)
        {
               
                Integer[]arr=new Integer[50];
                for(int i=0;i<50;i++)
                {
                        arr[i]=i+1;
                }
                System.out.println(arr[josephus(50,3)]);
        }
}

在java面试宝典上看到过这个题。

呵呵 不太清楚啊 貌似上学的时候不记得高数中有约瑟夫环

学习了，呵呵