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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© bestcaptain 中级黑马   /  2016-3-1 19:05  /  353 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

已到面试题,用代码写出来了,但是运行总出问题,改了好久没改好,递归没学好,求大神帮我看一下...感激不尽


//给你99个球,其中一个是坏的,再给你一个天平,用最少次数找出坏的球
/*思路:
* 1定义一个长度99,98个元素为50,随机选取一个脚标存入一个随机数,用来模拟不知道哪个球坏了也不知道坏掉的球轻重的情况
* 2每次讲数组分成三份,两两比较元素和,根据比较情况筛选出包含坏球的数组,并标记数组分割后脚标的更改.
* 3因为不知道要操作多少次 ,所以用递归(这里出问题了,搞不懂...)
*
*
*
* */
public class ___________BadBall {
        public static void main(String[] args) {
                int arr[] = new int[99];
                ArrayList<Integer> list = new ArrayList<>();
                while (list.size() != 99) {
                        int x = (int) new Random().nextInt(99); // 定义一个集合存入99个不同的正整数
                        if (!list.contains(x)) {
                                list.add(x);
                        }
                }

                for (Integer in : list) {
                        System.out.print(in + ","); // 遍历集合,并打印观察效果,顺便将数组全部存入整数50
                        arr[in] = 50;
                }
                System.out.println();
                // 生成一个随机脚标存入一个随机数,这样就能用该数组模拟99个球不知道哪个坏了
                arr[(int) new Random().nextInt(99)] = (int) new Random().nextInt(101);
                for (int i = 0; i < arr.length; i++) {
                        System.out.print(arr[i] + ",");// 打印数组
                }
                System.out.println();
                int z = getBad(arr);
                System.out.println(z);

        }

        public static int getArraySum(int[] arr) {// 定义一个获取数组元素和的方法

                int sum = 0;
                for (int i = 0; i < arr.length; i++) {
                        sum += arr[i];
                }
                return sum;
        }

        public static int getBad(int[] arr) {
                int index = 0;
                int n = arr.length;

                if (arr.length == 1) {
                        return 1;
                }

                else if (n % 3 == 0) {
                        int[] ar = new int[n / 3];
                        int[] br = new int[n / 3];
                        int[] cr = new int[n / 3];
                        ar = Arrays.copyOfRange(arr, 0, n / 3 - 1);// 将数组三等分
                        br = Arrays.copyOfRange(arr, n / 3, 2 * n / 3 - 1);
                        cr = Arrays.copyOfRange(arr, 2 * n / 3, n - 1);
                        int a = getArraySum(ar);
                        int b = getArraySum(br);
                        int c = getArraySum(cr);
                        if (a == b) {
                                arr = cr;
                                index = 2 * ar.length;// 每次调用方法都加上数组等分之前的长度,下同

                                // count += 2 * n / 3 - 1;

                        } else if (a == c) {
                                arr = br;
                                index = ar.length;

                                // count += n / 3 - 1;
                        } else {
                                arr = ar;

                        }
                } else if (n % 3 != 0) {

                        int[] ar = new int[(n - n % 3) / 3];
                        int[] br = new int[(n - n % 3) / 3];
                        int[] cr = new int[n / 3 + n % 3];
                        ar = Arrays.copyOfRange(arr, 0, (n - n % 3) / 3 - 1);
                        br = Arrays.copyOfRange(arr, (n - n % 3) / 3,
                                        2 * (n - n % 3) / 3 - 1);
                        cr = Arrays.copyOfRange(arr, 2 * (n - n % 3) / 3, n - 1);
                        int a = getArraySum(ar);
                        int b = getArraySum(br);
                        int c = getArraySum(Arrays.copyOfRange(cr, 0, ar.length - 1));
                        if (a == b) {
                                arr = cr;
                                index = 2 * ar.length;

                                // count += 2 * (n - n % 3) / 3 - 1;

                        } else if (a == c) {
                                arr = br;
                                index = ar.length;

                                // count += (n - n % 3) / 3 - 1;
                        } else {
                                arr = ar;

                        }
                }
                return index + getArraySum(arr);// 递归?????????

        }
}


0 个回复

您需要登录后才可以回帖 登录 | 加入黑马