Страницы

Поиск по вопросам

суббота, 30 ноября 2019 г.

Как оптимизировать мой код?

#java #алгоритм #инспекция_кода


Я новичок в 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-ов писал в большей степени для большей понятности кода
для себя лично.
    


Ответы

Ответ 1



Незачем делать сложный break через булеву переменную. Достаточно return, это прервёт все циклы. Условие "Каждая цифра может использоваться только один раз" нужно проверять не самым последним, а на этапе перебора. Так у вас будет всего 10!/2!=10*9*8*7*6*5*4*3 проверки, а не 10^8. Определяете множество всех цифр. Во внешнем цикле перебор по этому множеству. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле. В следующем цикле перебор по множеству из предыдущего цикла без той цифры, которая выбрана в предыдущем цикле... и так далее. Условия можно выделить и хранить как список методов (лямбд), а потом делать проверку в цикле.

Ответ 2



Решение "джаст фор фан", но по производительности даже получше, учитывая распараллеливание: IntFunction a = x -> x / 10000000 % 10; IntFunction b = x -> x / 1000000 % 10; IntFunction c = x -> x / 100000 % 10; IntFunction d = x -> x / 10000 % 10; IntFunction e = x -> x / 1000 % 10; IntFunction f = x -> x / 100 % 10; IntFunction g = x -> x / 10 % 10; IntFunction h = x -> x % 10; IntFunction 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);

Комментариев нет:

Отправить комментарий