标题: 继续昨天 ,天平找坏小球的问题代码已补充完整 [打印本页] 作者: bestcaptain 时间: 2016-3-2 22:37 标题: 继续昨天 ,天平找坏小球的问题代码已补充完整 import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
//给你99个球，其中一个是坏的，再给你一个天平，用最少次数找出坏的球(用代码模拟)
/*思路:
* 1:定义一个长度99,98个元素为50,随机选取一个脚标存入一个随机数(0-100),用来模拟不知道哪个球坏了也不知道坏掉的球轻重的情况(或轻或重的概率相等)
* 2:每次讲数组分成三份,两两比较元素和,根据比较情况筛选出包含坏球的数组,并标记数组分割后脚标的更改.
* 3:因为不知道要操作多少次 ,所以用递归.
* */
public class BadBall {
public static void main(String[] args) {
int[] arr = getSimulateArray(99);
int z = getBad(arr,0,0);
System.out.println("通过\"天平\"找到问题小球脚标,脚标为:");
System.out.println(z);
}
private static int[] getSimulateArray(int num) {
int arr[] = new int[num];
ArrayList<Integer> list = new ArrayList<>();
while (list.size() != num) {
int x = (int) new Random().nextInt(num);
if (!list.contains(x)) {
list.add(x); // 定义一个集合存入99个不同的非负整数
}
}
for (Integer in : list) {
arr[in] = 1; //先将数组元素全部存为1
}
int p;
while(true)
{
if((p=(int) new Random().nextInt(3))!=1)
break;
}
arr[(int) new Random().nextInt(num)] = p; //在一个随机脚标的元素位置输入一个0或2的随机数
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[] copyArr(int[] arr,int start,int end)//自定义复制数组方法,返回一个新的数组
{
int [] arr1=new int [end-start+1];
for(int i=start;i<=end;i++)
{
arr1[i-start]=arr[i];
}
return arr1;
}
public static int getBad(int[] arr,int index,int count) { //index为脚标
int n = arr.length;
if (arr.length == 1) {
System.out.print("最多用"+count+"次能够");
return 0;
}
else if (n % 3 == 0) { //数组能被三整除的情况
int[] ar = new int[n / 3];
int[] br = new int[n / 3];
int[] cr = new int[n / 3];
ar = copyArr(arr, 0, n / 3 - 1); // 将数组三等分
br = copyArr(arr, n / 3, 2 * n / 3 - 1);
cr = copyArr(arr, 2 * n / 3, n - 1);
int a = getArraySum(ar);
int b = getArraySum(br);
int c = getArraySum(cr);
if (a == b) { //比较分割后的数组的元素和,让arr指向 有问题的数组
arr = cr;
index = 2 * ar.length; // 每次调用方法都加上数组等分之前的长度,下同
count+=2;
} else if (a == c) {
arr = br;
index = ar.length;
count+=2;