2 a403071690 a403071690 于 2015.07.13 13:44 提问

java面试题约瑟芬环游戏

package java50ti;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class No10 {
//约瑟芬环 游戏:有n个人站成一个圈,标上号1-n:从第一个开始报数,数到m,就拖出去杀掉,下一位从一开始数,数到m杀掉,问最后一个人的标号是多少,
//下面有两个方法
//方法2是正确的,方法只能满足小数据,大一点的就异常了。求大神帮我改一下,看我的打印信息就知道我的思路了。
public static void main(String[] args) {
// TODO Auto-generated method stub
//经测试,输入: 6 3
//12 4都成功,输入大了就不行了,比如54 12就报错了,求帮我修改一下
Scanner scanner = new Scanner(System.in);

System.out.print("请输入总人数:");

int totalNum = scanner.nextInt();

System.out.print("请输入报数的大小:");

int cycleNum = scanner.nextInt();
yuesefu1(totalNum, cycleNum);

System.out.println("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
yuesefu2(totalNum, cycleNum);

}

public static void yuesefu1(int t ,int p)
{
    //首先我把这些人给放到数组里面,方便操作

    List l = new ArrayList();
    for(int i=1;i<=t;i++)
    { 
        l.add(i);
    }
    System.out.println(l.size());

    int wei =p;
    while(l.size()>1)
    {
        if(l.size()==p)
        {
            System.out.println("等于p");
            System.out.println("删掉"+l.get(p-1));
            l.remove(p-1);
        }if(l.size()<p)
        {
            System.out.println("小于p");
            System.out.println("删掉"+l.get(p-l.size()-1));
            l.remove(l.get(p-l.size()-1));
            System.out.println("---------------------------------");
            for(int k = 0;k<l.size();k++)
            {
                System.out.print(l.get(k)+".");
            }
            System.out.println("---------------------------------");

        }
        else{
        //先删除一个p位置的
        l.remove(p-1);
        //---------------------------------
        System.out.println("---------------------------------");
        for(int k = 0;k<l.size();k++)
        {
            System.out.print(l.get(k)+".");
        }
        System.out.println("---------------------------------");
        //---------------------------------
        for(int j=0;j<p-1;j++)
        {
            l.add(l.get(j));
        }
        //---------------------------------
        System.out.println("---------------------------------");
        for(int k = 0;k<l.size();k++)
        {
            System.out.print(l.get(k)+".");
        }
        System.out.println();
        System.out.println("---------------------------------");
        //---------------------------------
        for(int j=0;j<p-1;j++)
        {
            l.remove(0);
        }
        //---------------------------------
        System.out.println("---------------------------------");
        for(int k = 0;k<l.size();k++)
        {
            System.out.print(l.get(k)+".");
        }System.out.println();
        System.out.println("---------------------------------");
        }
    }

    System.out.println("最后的:"+l.get(0));
}

public static void yuesefu2(int t,int p)
{
    List list = new ArrayList();
    for(int i=1;i<=t;i++)
    {
        list.add(i);
    }
    int k=0;
    while(list.size()>0)
    {
        k = k+p; 
        k= k%(list.size())-1;
         System.out.print("k="+k+"值为:");
        if(k<0)
        {
            System.out.println(list.get(list.size()-1));
            list.remove(list.size()-1);
            k=0;
        }else
        {
            System.out.println(list.get(k));
            list.remove(k);
        }
    }

}

}

7个回答

Tiger_Zhao
Tiger_Zhao   Rxr 2015.07.13 14:33

l.remove(l.get(p-l.size()-1));这句
如果l.size()p的一半还小,算出来的下标超过l的范围了。

Tiger_Zhao
Tiger_Zhao 回复挨踢界小人物: 参考yuesefu2()k的计算,p-l.size()-1改成p%(l.size())-1
2 年多之前 回复
se7en_q
se7en_q 回复挨踢界小人物: 这样子,你的p无论是比l.size大几倍,都是没有关系的。
2 年多之前 回复
se7en_q
se7en_q 回复挨踢界小人物: 这个位置你应该去掉的是(p与l.size取余)的位置,如 l.size()=6 ,p=8 (8mod6)=2 那么你去掉就是第二个位置的数
2 年多之前 回复
a403071690
a403071690 对,我看到这点了,但是我不知道如何解决这个问题
2 年多之前 回复
tongyi55555
tongyi55555   2015.07.13 14:39

l.size()<p这个条件的处理方式不对,你每次删除时没有考虑1号是从第几个人开始报的,你这个是针对1号都是从第一个人开始报的处理的。

如果能计算到实际的下标就不存在下标越界的问题了。

a403071690
a403071690 对,对于>p的我都做了换位,但是小于p的情况比较特殊,所以我就混乱了,不知道小于p的这么解决
2 年多之前 回复
se7en_q
se7en_q   2015.07.13 14:50

从数学的角度来看就是求n与m的余数是多少,最后一个人就喊得多少。

se7en_q
se7en_q   2015.07.13 14:53

啊!没有审题,不要喷我。

a403071690
a403071690 帮我看看代码需要改进的地方
2 年多之前 回复
tongyi55555
tongyi55555   2015.07.13 16:06

昨天写的程序,参考下。

public class JosephDemo {

    private LinkedList<Integer> perList;
    private int start;
    private int scale;
    private int end;

    /**
     * @param num
     *            总人数,每个人的编号是从0开始的
     * @param start
     *            起始报数
     * @param scale
     *            报数为scale的整数倍时淘汰一个人,比如scale为3,则报数为3、6...的人会淘汰
     * @param end
     *            结束时剩余的人数
     */
    public JosephDemo(int num, int start, int scale, int end) {
        perList = new LinkedList<Integer>();
        for (int i = 0; i < num; i++) {
            perList.add(i);
        }
        this.start = start;
        this.scale = scale;
        this.end = end;
    }

    public static void main(String[] args) {
        int num = 10;
        int start = 1;
        int scale = 3;
        int end = 1;
        JosephDemo yd = new JosephDemo(num, start, scale, end);
        Integer[] index = yd.findEnd();
        System.out.println("剩下的编号为:");
        for (int i = 0; i < index.length; i++) {
            System.out.println(index[i]);
        }
    }

    /**
     * 找到剩下一个人时的起始编号
     * 
     * @return
     */
    private Integer[] findEnd() {
        int lastNum = perList.size();
        int _start = this.start;
        while (lastNum != this.end) {
            Integer head = perList.pop();
            if (_start % scale == 0) {
                lastNum--;
                System.out.println("数字为" + _start + "时,移除编号为" + head);
            } else {
                perList.addLast(head);
            }
            _start++;
        }
        Integer[] result = perList.toArray(new Integer[0]);
        return result;
    }
}
a403071690
a403071690 两个题目有些类似,我这个程序如何修改一下呢,我想了半天,不知道如何解决<p的情况
2 年多之前 回复
tongyi55555
tongyi55555   2015.07.14 13:17

我给你改了一下,主要针对小于p的问题,这里的主要解决如何确定下一个删除的index问题,需要引入一个变量来记录相关的位移,代码如下:


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class No10 {
    // 约瑟芬环 游戏:有n个人站成一个圈,标上号1-n:从第一个开始报数,数到m,就拖出去杀掉,下一位从一开始数,数到m杀掉,问最后一个人的标号是多少,
    // 下面有两个方法
    // 方法2是正确的,方法只能满足小数据,大一点的就异常了。求大神帮我改一下,看我的打印信息就知道我的思路了。
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // 经测试,输入: 6 3
        // 12 4都成功,输入大了就不行了,比如54 12就报错了,求帮我修改一下
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入总人数:");

        int totalNum = scanner.nextInt();

        System.out.print("请输入报数的大小:");

        int cycleNum = scanner.nextInt();
        long l = System.currentTimeMillis();
        yuesefu1(totalNum, cycleNum);
        System.out.println("方法1耗时:" + (System.currentTimeMillis() - l));

        System.out.println("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
        l = System.currentTimeMillis();
        yuesefu2(totalNum, cycleNum);
        System.out.println("方法2耗时:" + (System.currentTimeMillis() - l));

    }

    public static void yuesefu1(int t, int p) {
        // 首先我把这些人给放到数组里面,方便操作

        List l = new ArrayList();
        for (int i = 1; i <= t; i++) {
            l.add(i);
        }
        // System.out.println(l.size());

        int start = 0;
        while (l.size() > 1) {
            if (l.size() == p) {
                // System.out.println("等于p");
                // System.out.println("删掉" + l.get(p - 1));
                l.remove(p - 1);
            }
            if (l.size() < p) {
                // System.out.println("小于p");
                start = start + p;
                start = start % l.size() - 1;
                int index = (p % l.size() - 1 + start) % l.size();
                if (start < 0) {
                    index = l.size() - 1;
                    start = 0;
                } else {
                    index = start;
                }
                // System.out.println("删掉" + l.get(index));
                l.remove(l.get(index));
                // 原来的
                // System.out.println("删掉" + l.get(p - l.size() - 1));
                // l.remove(l.get(p - l.size() - 1));
                // System.out.println("---------------------------------");
                // for (int k = 0; k < l.size(); k++) {
                // System.out.print(l.get(k) + ".");
                // }
                // System.out.println("---------------------------------");

            } else {
                // 先删除一个p位置的
                l.remove(p - 1);
                // ---------------------------------
                // System.out.println("---------------------------------");
                // for (int k = 0; k < l.size(); k++) {
                // System.out.print(l.get(k) + ".");
                // }
                // System.out.println("---------------------------------");
                // ---------------------------------
                for (int j = 0; j < p - 1; j++) {
                    l.add(l.get(j));
                }
                // ---------------------------------
                // System.out.println("---------------------------------");
                // for (int k = 0; k < l.size(); k++) {
                // System.out.print(l.get(k) + ".");
                // }
                // System.out.println();
                // System.out.println("---------------------------------");
                // ---------------------------------
                for (int j = 0; j < p - 1; j++) {
                    l.remove(0);
                }
                // ---------------------------------
                // System.out.println("---------------------------------");
                // for (int k = 0; k < l.size(); k++) {
                // System.out.print(l.get(k) + ".");
                // }
                // System.out.println();
                // System.out.println("---------------------------------");
            }
        }

        System.out.println("方法1最后的:" + l.get(0));
    }

    public static void yuesefu2(int t, int p) {
        List list = new ArrayList();
        for (int i = 1; i <= t; i++) {
            list.add(i);
        }
        int k = 0;
        while (list.size() > 1) {
            k = k + p;
            k = k % (list.size()) - 1;
            // System.out.print("k=" + k + "值为:");
            if (k < 0) {
                // System.out.println(list.get(list.size() - 1));
                list.remove(list.size() - 1);
                k = 0;
            } else {
                // System.out.println(list.get(k));
                list.remove(k);
            }
        }
        System.out.println("方法2最后的:" + list.get(0));

    }
}

CSDNXIAOD
CSDNXIAOD   2015.07.16 15:25

{Java 面试题}
java面试题集锦
Java面试题全集(中)
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片