已到面试题,用代码写出来了,但是运行总出问题,改了好久没改好,递归没学好,求大神帮我看一下...感激不尽
//给你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);// 递归?????????
}
}
|
|
收藏
淘帖
踩
