算法-经典趣题-寻找假银币

一、问题

寻找假银币是一个非常有趣的智力题目,寻找假银币的大意如下:现在有8枚银币,其中有一枚是假币。但是,从外观和做工上无法分辨哪枚是真币哪枚是假币,只知道假币的重量要比真币稍轻。则要求仅使用一个天平,如何以最少的步骤寻找到假银币?

二、分析

我们来分析下寻找假银币问题。其实寻找假银币并不难,一种最基本的方法便是首先给硬币编上序号(1~8),然后通过天平进行两两比较,操作步骤如下:

(1)首先比较第1枚银币和第2枚银币的重量,如果天平两边平衡,则进行下一步操作,否则较轻的一边的硬币为假币;

(2)接着比较第3枚银币和第4枚银币的重量,如果天平两边平衡,则进行下一步操作,否则较轻的一边的硬币为假币;

……

重复上述步骤,直到8枚银币都比较完为止,便可以找到假银币。这种两两比较的方法简单,但是效率不高,需要的步骤比较多。这里需要寻找最少的操作步骤。

可以采用递归分治的思想来求解这个问题,操作步骤如下:

(1)首先为每个银币编号,然后可以将所有的银币等分为两份,放在天平的两边。

(2)因为假银币的分量较轻,因此天平较轻的一侧中一定包含假银币。

(3)再将较轻的一侧中的硬银币等分为两份,重复上述做法。

(4)直到剩下两枚硬银币,可用天平直接找出假银币来。

这种方法在银币个数比较多的时候便显示出了优势。可以按照此思路来编写相应的寻找假银币问题的求解算法。

三、编程

package com.joshua317;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n;
        int position;
        System.out.println("分治算法求解假币问题");
        System.out.println("请输入银币的总个数");
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] coin = new int[n];
        System.out.println("请输入银币的真假,有且只能有一个假币,,2代表真,1代表假");
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            coin[i] = scanner.nextInt();//接收银币的真假
            if (coin[i] == 1) {
                flag = true;
            }
        }
        if (!flag) {
            System.out.println("必须得有一个假币");
            return;
        }
        position = FindFakeCoin.getFakeCoin(coin, 0, n-1);
        System.out.println("在上述" + n + "个银币中,第" + position + "个银币是假的!");
    }
}

class FindFakeCoin {
    public static int getFakeCoin(int coin[], int low, int high) {
        int i, sum1, sum2, sum3;
        int re = 0;
        sum1 = sum2 = sum3 = 0;

        //最后两枚
        if (low + 1 == high) {
            if (coin[low] < coin[high]) {
                re = low + 1;
                return re;
            } else if (coin[low] > coin[high]) {
                re = high+1;
                return re;
            } else {
                return re;
            }
        }
        //硬币是偶数
        if ((high - low + 1) % 2 == 0) {
            //前半断的和
            for (i = low; i <= low  + (high - low) / 2; i++) {
                sum1 += coin[i];
            }
            //后半断的和
            for (i = low + (high - low) / 2 + 1; i <= high; i++) {
                sum2 += coin[i];
            }
            if (sum1 < sum2) {
                re = getFakeCoin(coin, low, low  + (high - low) / 2);
                return re;
            } else if (sum1 > sum2) {
                re = getFakeCoin(coin, low + (high - low) / 2 + 1, high);
                return re;
            } else {

            }
        } else {
            //前半断的和
            for (i = low; i <= low  + (high - low) / 2 - 1; i++) {
                sum1 += coin[i];
            }
            //后半断的和
            for (i = low + (high - low) / 2 + 1; i <= high; i++) {
                sum2 += coin[i];
            }
            sum3 = coin[low+(high-low)/2];
            if (sum1 < sum2) {
                re = getFakeCoin(coin, low, low  + (high - low) / 2 - 1);
                return re;
            } else if (sum1 > sum2) {
                re = getFakeCoin(coin, low + (high - low) / 2 + 1, high);
                return re;
            } else {

            }

            if (sum1 + sum3 == sum2 + sum3) {
                re = low + (high - low) / 2 + 1;
                return re;
            }

        }
        return re;
    }
}

joshua317博客
请先登录后发表评论
  • latest comments
  • 总共0条评论