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

}

}

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

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

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

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

啊！没有审题，不要喷我。

昨天写的程序，参考下。

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

我给你改了一下，主要针对小于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));

    }
}