12

Я новичок в Java (программировал в Pascal) и мне нужно написать программу для решения следующего задания (что-то вроде числового ребуса):

AB + CC = DC
CE * FB = CEB
FF * GC = GHC
AB - CE = FF
CC + FB = GC 
DC + CEB = GHC

П.С. Каждый символ одна цифра (от 0 до 9). Каждая цифра может использоваться только один раз.

Итак, я написал следующую программу:

public class javaapplication1 {

    public static void main(String[] args) {
        boolean bb=false;
        for (int h = 0; h < 10; h++) {
            for (int g = 0; g < 10; g++) {
                if (bb) {
                    break;
                }
                for (int f = 0; f < 10; f++) {
                    if (bb) {
                        break;
                    }
                    for (int e = 0; e < 10; e++) {
                        if (bb) {
                            break;
                        }
                        for (int d = 0; d < 10; d++) {
                            if (bb) {
                                break;
                            }
                            for (int c = 0; c < 10; c++) {
                                if (bb) {
                                    break;
                                }
                                for (int b = 0; b < 10; b++) {
                                    if (bb) {
                                        break;
                                    }
                                    for (int a = 0; a < 10; a++) {
                                        if (a*10 + b + c*10 + c == d*10 + c) {
                                            if ((c*10+e)*(f*10+b)==(c*100+e*10+b)) {
                                                if ((f*10+f)*(g*10+c)==g*100+h*10+c) {
                                                    if ((a*10+b)-(c*10+e) == f*10+f) {
                                                        if ((c*10+c)+(f*10+b) == g*10+c) {
                                                            if ((d*10+c)+(c*100+e*10+b) == g*100+h*10+c) {
                                                                if (a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h) {
                                                                    if (b!=c && b!=d && b!=e && b!=f && b!=g && b!=h) {
                                                                        if (c!=d && c!=e && c!=f && c!=g && c!=h) {
                                                                            if (d!=e && d!=f && d!=g && d!=h) {
                                                                                if (e!=f && e!=g && e!=h) {
                                                                                    if (f!=g && f!=h) {
                                                                                        if (g!=h) {
                                                                                            bb = true;
                                                                                            System.out.println(a);
                                                                                            System.out.println(b);
                                                                                            System.out.println(c);
                                                                                            System.out.println(d);
                                                                                            System.out.println(e);
                                                                                            System.out.println(f);
                                                                                            System.out.println(g);
                                                                                            System.out.println(h);
                                                                                            break;
                                                                                        }
                                                                                    }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }

                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Она работает и выдаёт правильные результаты, однако я уверен, что она написано неправильно, так как решение само по себе глупое - чистый подбор. Прошу показать мне, как можно оптимизировать данную программу. З.Ы. Большое количество if-ов писал в большей степени для большей понятности кода для себя лично.

14
  • Да, прошу прощение, опечатался. Условие обновил. Та строка выглядит следующим образом: FF * GC = GHC. И ещё: я знаю, что математическое (логическое) решение задачи есть - вопрос не в этом. Вопрос в том, как оптимизировать программу. 6 окт 2016 в 14:28
  • ну самая сильная оптимизация - решить задачу и выводить ответ )
    – pavel
    6 окт 2016 в 14:40
  • @pavel предположим, что список условий задаётся динамически )
    – Nick Volynkin
    6 окт 2016 в 14:41
  • Решать самому - это, конечно, хорошо. Но суть в проблемы в том, что заставить компьютер делать это максимально быстро и правильно, корректно использую его возможности и возможности языка. 6 окт 2016 в 14:42
  • 2
    первое, что я бы сразу оптимизировал, это проверка одинаковых цифр. Вы ее делаете в самую последнюю очередь, вынося тяжелые рассчеты в начало. А нужно наоборот. У Вас всего 8 цифр. это 10!/2! = 1814400. А в Вашем случае кол-во переборов сложно посчитать, и как следствие, это как максимум 10 в 8. я попробовал, перебирать только первые 4 цифры (a,b,c,d) и проверять самое первое условие. Как результат - осталось только 32 варианта.
    – KoVadim
    6 окт 2016 в 14:46

2 ответа 2

4
  1. Незачем делать сложный break через булеву переменную. Достаточно return, это прервёт все циклы.
  2. Условие "Каждая цифра может использоваться только один раз" нужно проверять не самым последним, а на этапе перебора. Так у вас будет всего 10!/2!=10*9*8*7*6*5*4*3 проверки, а не 10^8.
    1. Определяете множество всех цифр.
    2. Во внешнем цикле перебор по этому множеству.
    3. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле.
    4. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле... и так далее.
  3. Условия можно выделить и хранить как список методов (лямбд), а потом делать проверку в цикле.
6
  • Java же не позволяет положить метод в переменную? - а лямбды, не?
    – Grundy
    6 окт 2016 в 14:52
  • @Grundy точно, забыл что они там есть )
    – Nick Volynkin
    6 окт 2016 в 14:53
  • Спасибо за return, буду знать."Определяете множество всех цифр. Во внешнем цикле перебор по этому множеству. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле... и так далее." так делать и пытался, однако выдавало бред полный.. может и ошибка где была. Проверю позже. 6 окт 2016 в 14:54
  • я бы ещё в рекурсию лучше обернул, 10 циклов это слишком) И проверял условия на момент формирования (т.е. сразу когда можно вычислить выражение). Возможно добавил бы вычисление правил, типо если есть 2 слагаемых можно сразу вычислить сумму и не перебирать.
    – pavel
    6 окт 2016 в 14:57
  • 1
    break с меткой ещё можно.
    – Qwertiy
    7 окт 2016 в 9:35
4

Решение "джаст фор фан", но по производительности даже получше, учитывая распараллеливание:

IntFunction<Integer> a = x -> x / 10000000 % 10;
IntFunction<Integer> b = x -> x / 1000000 % 10;
IntFunction<Integer> c = x -> x / 100000 % 10;
IntFunction<Integer> d = x -> x / 10000 % 10;
IntFunction<Integer> e = x -> x / 1000 % 10;
IntFunction<Integer> f = x -> x / 100 % 10;
IntFunction<Integer> g = x -> x / 10 % 10;
IntFunction<Integer> h = x -> x % 10;

IntFunction<IntStream> fx =
    i -> IntStream.range(0, 10).filter(x -> {
        if (x == i) return false;
        for (int j = i; j > 0; j /= 10) {
            if (x == j % 10) {
                return false;
            }
        }
        return true;
    }).map(x -> 10 * i + x);

IntStream.range(0, 10).parallel()
    .flatMap(fx)
    .flatMap(fx)
    .flatMap(fx)
    .flatMap(fx)
    .flatMap(fx)
    .flatMap(fx)
    .flatMap(fx)
    .filter(x -> a.apply(x) * 10 + b.apply(x) + c.apply(x) * 10 + c.apply(x) == d.apply(x) * 10 + c.apply(x))
    .filter(x -> (f.apply(x) * 10 + f.apply(x)) * (g.apply(x) * 10 + c.apply(x)) == g.apply(x) * 100 + h.apply(x) * 10 + c.apply(x))
    .filter(x -> (a.apply(x) * 10 + b.apply(x)) - (c.apply(x) * 10 + e.apply(x)) == f.apply(x) * 10 + f.apply(x))
    .filter(x -> (c.apply(x) * 10 + e.apply(x)) * (f.apply(x) * 10 + b.apply(x)) == (c.apply(x) * 100 + e.apply(x) * 10 + b.apply(x)))
    .filter(x -> (c.apply(x) * 10 + c.apply(x)) + (f.apply(x) * 10 + b.apply(x)) == g.apply(x) * 10 + c.apply(x))
    .filter(x -> (d.apply(x) * 10 + c.apply(x)) + (c.apply(x) * 100 + e.apply(x) * 10 + b.apply(x)) == g.apply(x) * 100 + h.apply(x) * 10 + c.apply(x))
    .forEach(System.out::println);
1
  • 1
    А можете объяснить, что и как тут делается? 6 окт 2016 в 16:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.