java具体代码实现假币问题_减治法解决假币问题

以下是 Java 代码实现假币问题的减治法解决方法：

import java.util.*;

public class FakeCoin {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入硬币的数量：");
        int n = sc.nextInt();
        int[] coins = new int[n];
        System.out.println("请依次输入每枚硬币的重量：");
        for (int i = 0; i < n; i++) {
            coins[i] = sc.nextInt();
        }
        int fakeCoin = findFakeCoin(coins, 0, n-1);
        System.out.println("假币的位置是：" + (fakeCoin+1));
    }

    // 递归查找假币位置
    private static int findFakeCoin(int[] coins, int left, int right) {
        if (left == right) {
            return left;
        }
        int mid = (left + right) / 2;
        int leftSum = sum(coins, left, mid); // 左边硬币总重量
        int rightSum = sum(coins, mid+1, right); // 右边硬币总重量
        if (leftSum < rightSum) { // 假币在左边
            return findFakeCoin(coins, left, mid);
        } else if (leftSum > rightSum) { // 假币在右边
            return findFakeCoin(coins, mid+1, right);
        } else { // 左右两边重量相等，假币在剩下的那一枚硬币里
            return left;
        }
    }

    // 计算硬币的总重量
    private static int sum(int[] coins, int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += coins[i];
        }
        return sum;
    }
}

以上代码实现了假币问题的减治法解决方法，其中 `findFakeCoin` 方法采用递归方式查找假币的位置，`sum` 方法用于计算硬币的总重量。