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的随机数
System.out.println("该模拟数组的实际情况:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ","); // 打印数组
}
System.out.println();
System.out.println("小球个数"+arr.length);
System.out.println("通过遍历数组找出有问题小球的脚标:");
for(int i=0;i<arr.length;i++) //用遍历的方法找到有问题的小球,作为代码效果的对比,可以省略
{
if(arr[i]==1)
continue;
else
System.out.print(i);;
}
System.out.println();
return arr;
}
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;
} else {
arr = ar;
index=0;
}
} else if (n % 3 != 0) { //数组不能被3整除的时候分成短短长的三个数组,比如长度为11则分割成3,3,5
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 = copyArr(arr, 0, (n - n % 3) / 3 - 1);
br = copyArr(arr, (n - n % 3) / 3,
2 * (n - n % 3) / 3 - 1);
cr = copyArr(arr, 2 * (n - n % 3) / 3, n - 1);
int a = getArraySum(ar);
int b = getArraySum(br);
int c = getArraySum(copyArr(cr, 0, ar.length - 1));
if (a == b) {
arr = cr;
if(arr.length==2) //如果第三个数组长度为2,则用这个数组两个元素和好球比较,返回新的脚标标记
{
if(arr[0]==ar[0])
{
System.out.print("一共用了"+(++count+1)+"次");
return 3;
}
else if(arr[1]==ar[0])
{
System.out.print("一共用了"+(++count+1)+"次");
return 2;
}
}
else
index = 2 * ar.length;
count+=2;
} else if (a == c) {
arr = br;
index = ar.length;
count+=2;
} else {
arr = ar;
index=0;
}
}
return index + getBad(arr,index,count); //递归
}
}
|
|
收藏
淘帖
踩
