A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 张辉2012 中级黑马   /  2012-12-15 21:35  /  3964 人查看  /  18 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

评分

参与人数 1技术分 +1 收起 理由
邵天强 + 1 这好像是n年前的题吧,不过还是鼓励一下.

查看全部评分

18 个回复

倒序浏览
这道题利用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();
}
}

点评

程序我测试了一下,不管多少结果都为11,并且可能有异常抛出  发表于 2012-12-15 23:43

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
这个就是循环套循环,理清思路画画图应该能解出来!
回复 使用道具 举报
这个就是循环套循环,理清思路画画图应该能解出来!
回复 使用道具 举报
//此题为经典的约瑟夫环问题,没有用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)]);
        }
}

点评

不错 学习了  发表于 2012-12-25 11:51

评分

参与人数 1技术分 +1 收起 理由
邵天强 + 1 赞一个!

查看全部评分

回复 使用道具 举报
针对你这个题,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-12-16 17:55 编辑
张辉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
•……
•可得出我程序中的递推公式





评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 Attacker_P 于 2012-12-18 13:07 编辑

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--;
        }
}

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
张辉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面试宝典上看到过这个题。
回复 使用道具 举报
呵呵 不太清楚啊 貌似上学的时候不记得高数中有约瑟夫环
回复 使用道具 举报
学习了,呵呵
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马