java算法《丢硬币、最近点对》
程序员文章站
2024-03-16 12:50:46
...
用分治法解决如下问题:
- 已知给定n个硬币中有一个是假币,鉴别方式为假币重量比真币轻,请找出n个硬币中的这个假币。用分治策略设计算法解决此问题,并测试算法的正确性,要求输出假币所在的位置以及重量。
- 最近点对问题。已知一条直线上有n个点,请找出这条直线上距离最近的点对。用分治策略设计算法解决此问题,并测试算法的正确性,要求输出最近的点对距离为多少,对应的是哪对点,如(d1,d2)表示一对点,d1,d2分别表示两点的坐标。
提示:直线上的点可以转换成x轴上的点,每个点有相应的坐标值(整数),点d1与点d2之间的距离可以用两点的坐标值之差的绝对值来表示。
//第1题
public class yingbi {
public static int sta;
public static void main(String[] args) {//此程序局限:需要三个以上的硬币
int[] A = {10, 10, 10, 1, 10};
int a = num_s(A);//真币的质量
System.out.println(a);
int left = 0;
int right = A.length - 1;
finds(A, a, left, right);//判断左边还是右边
find(A, a, left, right);//开始找
}
//查找假币在左还是右
private static void finds(int[] A, int a, int left, int right) {//如果从左边到中间的和大于中间到右边的和,那么假币在右边
int middle = (left + right) / 2;
int sum = 0;
int sum1 = 0;
int sum_ou = 0;
int sum_ou1 = 0;
//偶数硬币数执行以下程序
if (A.length % 2 == 0) {
int L_ou = (A.length / 2) - 1;//偶数硬币的左边最后一位
for (int num2 = 0; num2 <= L_ou; num2++) {
sum_ou = sum_ou + A[num2]; //左边求和
}
for (int num3 = L_ou; num3 <= A.length - 1; num3++) {
sum_ou1 = sum_ou1 + A[num3];//右边求和
}
if (sum_ou > sum_ou1) {//假币在右边
sta = 1;
} else {
sta = 0;
}//假币在左边
} else {
//奇数硬币数执行以下程序
if (A[middle] == a) {//如果中间那个不是假币,就执行以下操作
for (int num = 0; num <= middle; num++) {
sum = sum + A[num];//左边求和
}
for (int num1 = middle; num1 <= right; num1++) {
sum1 = sum1 + A[num1];//右边求和
}
//假币的位置
if (A[middle] != a) {
System.out.println("重量是:" + A[middle]);
System.out.println("位置是:" + middle);
} else if (sum < sum1) {//假币在左边
sta = 1;
} else {
//假币在右边
sta = 0;
}
} else {//如果中间的是那个硬币即返回
System.out.println("重量是:" + A[middle]);
System.out.println("位置是:" + middle);
}
}
}
//寻找出现最多的那个元素
private static int num_s(int[] A) {
if (A[0] == A[1] || A[0] == A[2]) {
return A[0];
}
return A[1];
}
//寻找假币的位置以及质量
private static void find(int[] A, int a, int left, int right) {
int middle = (left + right) / 2;
int num = 0;
if (A[middle] != a) {
System.out.println("重量是:" + A[middle]);
System.out.println("位置是:" + middle);
num = 1;
} else if (sta == 1) {//假币在左边
find(A, a, 0, middle);
} else if (sta == 0) {
//假币在右边
find(A, a, middle + 1, right);
}
}
}
//第2题
import java.util.Arrays;
public class dianDui {
public static void main(String[] args) {//注意是一条直线上
int[][] xy = {{1, 1}, {1, 3}, {1, 5}, {1, 7}, {1, 9}, {1, 10}};
cel(xy);
//计算所有点的距离。输出一个距离数组
}
public static void cel(int[][] A) {
int sum[] = new int[A.length - 1];//定义距离数组
for (int x = 0; x < A.length - 1; x++) {//计算两点距离
int distances = ((A[x + 1][0] - A[x][0]) * (A[x + 1][0] - A[x][0])) + ((A[x + 1][1] - A[x][1]) * (A[x + 1][1] - A[x][1]));
sum[x] = (int) Math.sqrt(distances);//先开根再化整数
}
System.out.println("所有点的距离为:" + Arrays.toString(sum));
int left = 0;
int right = A.length - 1;
int middle = (left + right) / 2;
int a = (int) dianDui.find(sum, left, middle, right);//跳入查找方法,a输出的是最小值的位置
//先将double转变成int
System.out.println("第一个坐标:" + Arrays.toString(A[a]) + "第二个坐标:" + Arrays.toString(A[a + 1]));
}
//寻找
public static double find(int[] A, int left, int middle, int right) {
int position_l = 0;//位置
int position_r = 0;//位置
int min_l = A[middle - 1];//值
int min_r = 0;//值
double[][] pos = new double[2][2];
for (int i = middle; i > 0; i--) {//左边
if (A[i] < A[i - 1]) {
if (A[i] < min_l) {
min_l = A[i];//最小位的值
position_l = i;//最小位的位
}
} else {
if (A[i - 1] < min_l) {
min_l = A[i - 1];//最小位的值
position_l = i - 1;//最小位的位置
}
}
}
pos[0][0] = min_l;
pos[0][1] = position_l;
//System.out.println("左边最小位的值"+min_l);
//System.out.println("左边最小位的位置"+position_l);
if (middle + 1 != A.length - 1) {//遇到最后一位了
for (int is = middle + 1; is < A.length - 1; is++) {//右边
if (A[is] < A[is + 1]) {
min_r = A[is];//最小位的值
position_r = is;//最小位的位
//System.out.println("右边最小位的位置"+position_r+"!!!!");
} else {
min_r = A[is + 1];//最小位的值
position_r = is + 1;//最小位的位置
//System.out.println("右边最小位的位置"+position_r+"!!!!");
}
}
pos[1][0] = min_r;
pos[1][1] = position_r;
//System.out.println("右边最小位的值"+min_r);
//System.out.println("右边最小位的位置"+position_r);
} else {
pos[1][0] = A[middle + 1];
pos[1][1] = middle + 1;
//System.out.println("右边最小位的值"+A[middle+1]);
// System.out.println("右边最小位的位置"+middle+1);
}
//System.out.println(Arrays.deepToString(pos));
if (pos[0][0] > pos[1][0]) {
System.out.println("最短长度为:" + pos[1][0]);
return pos[1][1];//返回的是位置
} else {
System.out.println("最短长度为:" + pos[0][0]);
return pos[0][1];
}
}
@Override
public String toString() {
return "dianDui{}";
}
}