Sport programming
Programming
Java
Algorithms
7 April 2015

12 шаров

Совершенно случайно узнал об интересной задаче, которая очень даже может взбодрить.

Задача:
На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).
Перед тем, как решить задачу за 5 минут, внимательно прочтите условие.
У меня на всё ушло 6 часов (долго, не претендую на гениальность).
Математическое обоснование решения и краткая история задачи

Мое решение на языке Java с тестами
LINK — для проверки online
public class Balls {

    private static final int A = 10;
    private static final int B = 11;

    private static final int LEFT_BIGGER = 1;
    private static final int RIGHT_BIGGER = 2;
    private static final int SAME = 4;

    public static void printTest() {
        System.out.println(Balls.test(true));
        System.out.println(Balls.test(false));
    }

    public static String test(boolean weight) {
        int[] array = new int[12];
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < array.length; ++i) {
            for (int w = 0; w < array.length; ++w) {
                array[w] = 5;
            }
            array[i] += weight ? 2 : -2;

            Balls balls = new Balls(array);

            builder.append("pos   = 0123456789AB\n");
            builder.append("array = ");
            for (int w : array) {
                builder.append(w);
            }
            builder.append('\n');
            builder.append("res   = ");
            balls.calculateNumber();
            int number = balls.getResultPosition();
            for (int w = 0; w < array.length; ++w) {
                builder.append(w == number ? '*' : ' ');
            }
            builder.append(" // number = ");
            builder.append(number);
            builder.append("; steps = ");
            builder.append(balls.getStepsCount());
            builder.append('\n');
        }
        return builder.toString();
    }

    private int[] in;
    private int steps;
    private int number = -1;

    public Balls(int[] in) {
        this.in = in;
    }

    public void calculateNumber() {
        this.steps = 0;

        int step1 = compare(sum(0, 1, 2, 3), sum(4, 5, 6, 7));

        switch (step1) {
            case SAME: {
                int step2 = compare(sum(0, 1), sum(8, 9));
                switch (step2) {
                    case SAME: {
                        number = compare(in[0], in[B]) == SAME ? A : B;
                        break;
                    }
                    default: {
                        number = compare(in[0], in[9]) == SAME ? 8 : 9;
                        break;
                    }
                }
                break;
            }
            case LEFT_BIGGER: {
                int step2 = compare(sum(0, 1, 4), sum(2, 3, 5));
                switch (step2) {
                    case LEFT_BIGGER: {
                        int tempState = compare(in[0], in[1]);
                        number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 0 : 1;
                        break;
                    }
                    case RIGHT_BIGGER: {
                        int tempState = compare(in[2], in[3]);
                        number = tempState == SAME ? 4 : tempState == LEFT_BIGGER ? 2 : 3;
                        break;
                    }
                    case SAME: {
                        number = compare(in[6], in[7]) == LEFT_BIGGER ? 7 : 6;
                        break;
                    }
                }
                break;
            }
            case RIGHT_BIGGER: {
                int step2 = compare(sum(0, 1, 4), sum(2, 3, 5));
                switch (step2) {
                    case LEFT_BIGGER: {
                        int newState = compare(in[2], in[3]);
                        number = newState == SAME ? 4 : newState == LEFT_BIGGER ? 3 : 2;
                        break;
                    }
                    case RIGHT_BIGGER: {
                        int tempState = compare(in[0], in[1]);
                        number = tempState == SAME ? 5 : tempState == LEFT_BIGGER ? 1 : 0;
                        break;
                    }
                    case SAME: {
                        number = compare(in[6], in[7]) == LEFT_BIGGER ? 6 : 7;
                        break;
                    }
                }
                break;
            }
        }
    }

    public int getResultPosition() {
        return number;
    }

    public int getStepsCount() {
        return steps;
    }

    private int compare(int l, int r) {
        ++steps;
        return l > r ? LEFT_BIGGER : l < r ? RIGHT_BIGGER : SAME;
    }

    private int sum(int... array) {
        int result = 0;
        for (int i : array) {
            result += in[i];
        }
        return result;
    }
}


-19
21.6k 30
Comments 59