Можно ли построить из заданного набора выражение, равное числу N

@wolfbethowen · Регистрация: 09.01.2018

Студворк — интернет-сервис помощи студентам

В сборниках занимательных математических задач встречается такой тип задач, когда надо из заданных чисел и арифметических знаков составить выражение, дающее какое-то заданное число. Пример такой задачи: "Составьте из чисел 4, 1, 8, 7 и арифметических знаков выражение, равное 24". Ответом может служить такое выражение: "(8-4) * (7-1)". К сожалению, некоторые авторы допускают ошибки и предлагают нерешаемую задачу, поэтому их начальник обратился к программистам.

Необходимо написать такую программу, которая определяет, можно ли построить из заданного набора выражение, равное числу N или нет. Так как это только прототип, то достаточно написать программу, которая работает только с наборами из 4-х чисел, а число N всегда равно 24.

Допустимые арифметические операторы: сложение, вычитание, умножение, деление, скобки.

На входе: массив из 4-х целых чисел от 1 до 9.

На выходе: true (если из заданного набора можно построить выражение, равное 24) или false (если из заданного набора такого выражения построить нельзя).

Пример 1.

На входе: [4, 1, 8, 7]

На выходе: true

Пояснение: (8-4) * (7-1) = 24

начал писать.... вроде как что-то да и получалось, но тут возник с подставлением скобок. и никак не могу придумать как правильно их ставить. ведь если она открывается или закрывается, то и расположение относительно арифм.знака меняется. вот код который получился, но не работает. подскажите как поступить. и можно ли как-то упростить эту гору циклов:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
     int a, b, c, d;
     char x, y, z, e, q, w;
     a = 1;
     b = 2;
     c = 3;
     d = 4;
     int[] arr = new int[4];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 4;
     char[] charr = new char[6];
        charr[0] = '+';
        charr[1] = '-';
        charr[2] = '/';
        charr[3] = '*';
        charr[4] = '(';
        charr[5] =  ')';
 
            for (int i = 0; i < 4; i++) {
                a = arr[i];
                for (int j = 0; j < 4; j++) {
                    if (i != j) {
                        b = arr[j];
                        for (int k = 0; k < 4; k++) {
                            if (k != j & k != i) {
                                c = arr[k];
                                for (int l = 0; l < 4; l++) {
                                    if (l != j & l != k & l != i) {
                                        d = arr[l];
                                        for (int m = 4; m < 5; m++) {  // цикл символов
                                            for (int n = 0; n < 6; n++) {
                                                if (n != m ) {
                                                    for (int o = 0; o < 6; o++) {
                                                        if (o != n & o != m) {
                                                            for (int p = 0; p < 6; p++) {
                                                                if (p != o & p != n & p != m) {
                                                                    for (int r = 0; r < 6; r++) {
                                                                        if (r != m & r != n & r != o & r != p) {
                                                                            for (int s = 0; s < 6; s++) {
                                                                                if (s != m & s != n & s != o & s != p & s != r) {
                                                                                    System.out.println (charr[s] + a + charr[m]  );
 
 
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
 
 
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

@Dmitry_Barynov · 05.04.2019, 23:19

У кого работает подскажите сколько точно всего вариантов

@LektorIn · 05.04.2019, 23:32

Сообщение от Dmitry_Barynov

У кого работает подскажите сколько точно всего вариантов

5804 варианта.
имейте в виду,написанный ранее код на java9 считает не совсем верно(проверено,пропускает некоторые правильные варианты если быть точным то 47 вариантов) количество естественно указано для комбинаций цифр, на каждую еще 64 комбинации знаков если не ошибаюсь ..

Добавлено через 1 минуту

Сообщение от wolfbethowen

спасибо)

всегда пжалста.

@vcrop · 06.04.2019, 00:23

Ладно, признаю косяк )))

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    public static boolean valid(List<List<Double>> list) {
        final List<DoubleBinaryOperator> operators = List.of(
                (a, b) -> a + b, (a, b) -> a - b,
                (a, b) -> a * b, (a, b) -> a / b
        );
        final int size = list.get(0).size();
        return (size > 1) ? valid(list.stream()
                .flatMap(l -> IntStream.range(0, size)
                        .boxed()
                        .flatMap(i -> IntStream.range(0, size)
                                .filter(j -> i != j)
                                .boxed()
                                .flatMap(j -> operators.stream()
                                        .map(op -> op.applyAsDouble(l.get(i), l.get(j)))
                                        .filter(Double::isFinite)
                                        .map(res -> IntStream.range(0, size)
                                                .filter(n -> n != i && n != j)
                                                .mapToObj(l::get)
                                                .collect(collectingAndThen(toList(), r -> {
                                                    r.add(res);
                                                    return r;
                                                }))
                                        )))).collect(toList()))
                : list.stream().anyMatch(i -> Math.abs(i.get(0) - 24.) < 0.001);
    }

5804 варианта

@Dmitry_Barynov · 06.04.2019, 10:56

Всем спасибо и за количество вариантов и за пробные варианты. Вроде наконец то доделал. конечный вариант выглядит так:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
    
public class Laba6 {
    public static boolean canBeEqualTo24(int[] nums) {
        if (nums.length < 4) return false;
        final int RESULT = 24;
        if (nums[0] + nums[1] + nums[2] + nums[3] == RESULT) return true;
        if (nums[0] * nums[1] * nums[2] * nums[3] == RESULT) return true;
 
        int[][] shuffle = {
                {0, 1, 2, 3},
                {0, 1, 3, 2},
                {0, 2, 1, 3},
                {0, 2, 3, 1},
                {0, 3, 2, 1},
                {0, 3, 1, 2},
 
                {1, 0, 2, 3},
                {1, 0, 3, 2},
                {1, 2, 0, 3},
                {1, 2, 3, 0},
                {1, 3, 2, 0},
                {1, 3, 0, 2},
 
                {2, 0, 1, 3},
                {2, 0, 3, 1},
                {2, 1, 0, 3},
                {2, 1, 3, 0},
                {2, 3, 0, 1},
                {2, 3, 1, 0},
 
                {3, 0, 1, 2},
                {3, 0, 2, 1},
                {3, 1, 0, 2},
                {3, 1, 2, 0},
                {3, 2, 0, 1},
                {3, 2, 1, 0},
        };
        for (int i = 0; i < 24; i++) {
            int a = nums[shuffle[i][0]];
            int b = nums[shuffle[i][1]];
            int c = nums[shuffle[i][2]];
            int d = nums[shuffle[i][3]];
 
 
            if (a + b + c - d == RESULT) return true;
            if (a + b - c - d == RESULT) return true;
            if (a + b + c * d == RESULT) return true;
            if (a + b + c * d == RESULT) return true;
            if (a + b * c * d == RESULT) return true;
            if (a - b + c * d == RESULT) return true;
            if (-a + b * c - d == RESULT) return true;
            if (a * b * c - d == RESULT) return true;
            if (a + b * (c + d) == RESULT) return true;
            if (a - b * (c + d) == RESULT) return true;
            if (a + b * (c - d) == RESULT) return true;
            if (a * b * (c + d) == RESULT) return true;
            if (a * b * (c - d) == RESULT) return true;
            if (-a + b * (c - d) == RESULT) return true;
            if (a * (b + c + d) == RESULT) return true;
            if (a * (b + c - d) == RESULT) return true;
            if (a * (b - c - d) == RESULT) return true;
            if (-a + (b * (c + d)) == RESULT) return true;
            if ((a + b) * (c + d) == RESULT) return true;
            if ((a - b) * (c + d) == RESULT) return true;
            if ((a - b) * (c - d) == RESULT) return true;
            if ((a * b) + (c * d) == RESULT) return true;
            if ((a * b) - (c * d) == RESULT) return true;
            if (a * (b * c - d) == RESULT) return true;
            if (a * (b * c + d) == RESULT) return true;
 
            if (d != 0) {
                if (a * b - c / d == RESULT && c % d == 0) return true;
                if (a + b - c / d == RESULT && c % d == 0) return true;
                if ((a * b) / d + c == RESULT && (a * b) % d == 0) return true;
                if (((a + b) * c) / d == RESULT && ((a + b) * c) % d == 0) return true;
                if (((a - b) * c) / d == RESULT && ((a - b) * c) % d == 0) return true;
                if (((a * b) - c) / d == RESULT && ((a * b) - c) % d == 0) return true;
                if (((a * d + c) * b) / d == RESULT && ((a * d + c) * b) % d == 0) return true;
                if (((a * d - c) * b) / d == RESULT && ((a * d - c) * b) % d == 0) return true;
            }
            if (d * c != 0) {
                if ((a * b) / (d * c) == RESULT && (a * b) % (d * c) == 0) return true;
            }
            if (c - d != 0) {
                if ((a * b) / (c - d) == RESULT && (a * b) % (c - d) == 0) return true;
            }
            if (c + d != 0) {
                if ((a * b) / (c + d) == RESULT && (a * b) % (c + d) == 0) return true;
            }
            if ((a * c - b) != 0) {
                if ((d * c) / (a * c - b) == RESULT && (d * c) % (a * c - b) == 0) return true;
            }
        }
        return false;
    }
}

@Timoved · 06.04.2019, 18:43

Есть уже те, кто успешно прошёл собеседование? Вот, все 5798 вариантов комбинаций чисел, из которых можно получить число 24. Если кому надо. Если кто работает со скобками, не забывайте, что они могут быть двойные. Например: (A/(B-C))*D.

@Timoved · 06.04.2019, 23:13

В этом архиве все 5804 комбинации. В прошлом - на 6 меньше было.

@wolfbethowen · 07.04.2019, 22:26 **[ТС]**

Timoved, по поводу (A/(B-C))*D. это тоже самое, что и (B-C)*D/A. так что ты просто впустую загружаешь систему ненужными вычислениями. поэтому и код медленно работает, скорее всего. если брать цикл перебора, то надо аккуратно подойти к этому, чтобы не было повторений. у меня также реализована проверка, чтобы не было ненужных операций. к примеру если а+б+в+г, то к такому выражению скобки не применяю, ну и т.д. ну, ИМХО

@Timoved · 07.04.2019, 22:53

wolfbethowen, к сожалению, не то же самое. Но смысл понятен. Одни скобки можно просто убрать. Не совсем удачный пример привел.(A/(B-C))*D !=(B-C)*D/A. (A/(B-C))*D = A*D/(B-C). Хотя, может, и не нужны двойные скобки. Медленно считает не из-за этого. Там причина в другом

@wolfbethowen · 07.04.2019, 23:20 **[ТС]**

Timoved, ну да, промахнулся. но суть та же. так поделись в чем причина.

@wolfbethowen · 08.04.2019, 22:38 **[ТС]**

Timoved, ну еще бы. Каждый сам за себя)

@Timoved · 08.04.2019, 22:41

wolfbethowen, это ты о чём?

@Dmitry_Barynov · 09.04.2019, 20:05

Сказали что всё правильно позвали на собес

@wolfbethowen · 09.04.2019, 21:11 **[ТС]**

Dmitry_Barynov, клёво,че! удачи! мне ничего не ответили :-(

@wolfbethowen · 10.04.2019, 18:15 **[ТС]**

LektorIn, как ты и просил, скидываю свое решение:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
    public static boolean ccanBeEqualTo24(int[] nums) throws ScriptException {
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("js");
        int a, b, c, d;
        char q, w, e;
        boolean answer = false;
        char[] arch = new char[4];
        arch[0] = '-';
        arch[1] = '+';
        arch[2] = '/';
        arch[3] = '*';
        one:
        {
            for (int i = 0; i < 4; i++) {
                a = nums[i];
                for (int j = 0; j < 4; j++) {
                    if (j != i) {
                        b = nums[j];
                        for (int k = 0; k < 4; k++) {
                            if (k != i & k != j) {
                                c = nums[k];
                                for (int l = 0; l < 4; l++) {
                                    if (l != i & l != j & l != k) {
                                        d = nums[l];
                                        for (int m = 0; m < 4; m++) {
                                            q = arch[m];
                                            for (int n = 0; n < 4; n++) {
                                                w = arch[n];
                                                for (int o = 0; o < 4; o++) {
                                                    e = arch[o];
 
 
                                                    String arstr;
                                                    arstr = "" + a + q + b + w + c + e + d;
                                                    Object result = engine.eval(arstr);
                                                    Double tre = new Double(result.toString());
 
 
                                                    if ( tre > 23.99 & tre < 24.001) {
                                                        answer = true;
                                                        System.out.println(answer);
                                                        System.out.println("" + arstr + " = 24;");
                                                        break one;
                                                    } else if (q != w || q != e || e != w) {
                                                        if (q != w) {
                                                            arstr = "" + '(' + a + q + b + w + c + ')' + e + d;
                                                            result = engine.eval(arstr);
                                                             tre = new Double(result.toString());
 
 
                                                            if (tre > 23.99 & tre < 24.001) {
                                                                answer = true;
                                                                System.out.println(answer);
                                                                System.out.println("" + arstr + " = 24;");
                                                                break one;
                                                            }
                                                        }
                                                        if (q != '*') {
                                                            arstr = "" + '(' + a + q + b + ')' + w + c + e + d;
                                                            result = engine.eval(arstr);
                                                             tre = new Double(result.toString());
 
 
                                                            if (tre > 23.99 & tre < 24.001) {
                                                                answer = true;
                                                                System.out.println(answer);
                                                                System.out.println("" + arstr + " = 24;");
                                                                break one;
                                                            }
                                                        }
 
 
                                                        arstr = "" + '(' + a + q + b + ')' + w + '(' + c + e + d + ')';
                                                        result = engine.eval(arstr);
                                                         tre = new Double(result.toString());
 
 
                                                        if (tre > 23.99 & tre < 24.001) {
                                                            answer = true;
                                                            System.out.println(answer);
                                                            System.out.println("" + arstr + " = 24;");
                                                            break one;
                                                        }
 
 
                                                        arstr = "" + a + q + '(' + b + w + c + e + d + ')';
                                                        result = engine.eval(arstr);
                                                        tre = new Double(result.toString());
 
 
                                                        if (tre > 23.99 & tre < 24.001) {
                                                            answer = true;
                                                            System.out.println(answer);
                                                            System.out.println("" + arstr + " = 24;");
                                                            break one;
 
                                                        }
 
                                                        if ((q != '-' || q != '+') & (e != '+' || e != '-')) {
                                                            arstr = "" + a + q + '(' + b + w + c + ')' + e + d;
                                                            result = engine.eval(arstr);
                                                            tre = new Double(result.toString());
 
 
                                                            if (tre > 23.99 & tre < 24.001) {
                                                                answer = true;
                                                                System.out.println(answer);
                                                                System.out.println("" + arstr + " = 24;");
                                                                break one;
                                                            }
                                                        }
                                                        if (w != e) {
                                                            arstr = "" + a + q + b + w + '(' + c + e + d + ')';
                                                            result = engine.eval(arstr);
                                                            tre = new Double(result.toString());
 
 
                                                            if (tre > 23.99 & tre < 24.001) {
                                                                answer = true;
                                                                System.out.println(answer);
                                                                System.out.println("" + arstr + " = 24;");
                                                                break one;
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
 
            if (!answer)
                System.out.println(answer);
            System.out.print("Пояснение: из данного набора чисел невозможно составить выражение, равное 24.");
        }
        return answer;
    }
}

@JavaDoc · 11.04.2019, 20:24

Сообщение от Dmitry_Barynov

Я как ещё один соискатель отправил вот эту дичь

соискатель? это за решение таких задач на работу могут взять? и сколько предлагают за эти знания? куда решение отправить?

Сообщение от ArtemFM

Последний вариант свой скину. Доработал сегодня...

я думаю универсальный вариант можно в два раза короче написать даже с комментариями уложусь в строчек 190 , если без комментарий то в строчек 150 - 160 это без лямбд

@Timoved · 11.04.2019, 20:38

JavaDoc, теоретически могут взять. Но этапы отбора надо продлить. А вообще можно многое. Хоть в одну строчку. Ограничений по количеству строк ведь в задании нет.

@ArtemFM · 11.04.2019, 20:45

JavaDoc, так напиши, а пока это слова

@wolfbethowen · 11.04.2019, 21:01 **[ТС]**

JavaDoc, да у меня как бы 140 строк со всяким шлаком. можно до 100 уменьшить. но здесь не меряются длиной кода, к счастью. есть идеи, покажи.

Добавлено через 56 секунд
Dmitry_Barynov, когда пойдешь на собеседование?

@ArtemFM · 11.04.2019, 21:02

универсальная программа, где не будет магических чисел и магических символов и строк в методах в 160 строк без лямбд и где будет не всё в одном методе... хмм... С радостью посмотрю на код

@JavaDoc · 11.04.2019, 21:08

Сообщение от ArtemFM

одном методе... хмм...

два приватных метода, ошибся сказав про лямбды, т.к. я думал использовать функциональный интерфейс а может два, по этому без -> стрелочки не обойтись,то что стримами не буду пользоваться это точно. просто решение будет другое. т.е. я так понял это на какой - то московский курс набирают?

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

@Dmitry_Barynov 0 / 0 / 0 Регистрация: 02.04.2019 Сообщений: 9
	05.04.2019, 23:19
	У кого работает подскажите сколько точно всего вариантов 0

@wolfbethowen 6 / 4 / 2 Регистрация: 09.01.2018 Сообщений: 59
	07.04.2019, 22:26 [ТС]
	Timoved, по поводу (A/(B-C))D. это тоже самое, что и (B-C)D/A. так что ты просто впустую загружаешь систему ненужными вычислениями. поэтому и код медленно работает, скорее всего. если брать цикл перебора, то надо аккуратно подойти к этому, чтобы не было повторений. у меня также реализована проверка, чтобы не было ненужных операций. к примеру если а+б+в+г, то к такому выражению скобки не применяю, ну и т.д. ну, ИМХО 0

@Timoved 0 / 0 / 0 Регистрация: 29.03.2019 Сообщений: 61
	07.04.2019, 22:53
	wolfbethowen, к сожалению, не то же самое. Но смысл понятен. Одни скобки можно просто убрать. Не совсем удачный пример привел.(A/(B-C))D !=(B-C)D/A. (A/(B-C))D = AD/(B-C). Хотя, может, и не нужны двойные скобки. Медленно считает не из-за этого. Там причина в другом 0

@wolfbethowen 6 / 4 / 2 Регистрация: 09.01.2018 Сообщений: 59
	07.04.2019, 23:20 [ТС]
	Timoved, ну да, промахнулся. но суть та же. так поделись в чем причина. 0

@wolfbethowen 6 / 4 / 2 Регистрация: 09.01.2018 Сообщений: 59
	08.04.2019, 22:38 [ТС]
	Timoved, ну еще бы. Каждый сам за себя) 0

@Timoved 0 / 0 / 0 Регистрация: 29.03.2019 Сообщений: 61
	08.04.2019, 22:41
	wolfbethowen, это ты о чём? 0

@Dmitry_Barynov 0 / 0 / 0 Регистрация: 02.04.2019 Сообщений: 9
	09.04.2019, 20:05
	Сказали что всё правильно позвали на собес 0

@wolfbethowen 6 / 4 / 2 Регистрация: 09.01.2018 Сообщений: 59
	09.04.2019, 21:11 [ТС]
	Dmitry_Barynov, клёво,че! удачи! мне ничего не ответили :-( 0

@Timoved 0 / 0 / 0 Регистрация: 29.03.2019 Сообщений: 61
	11.04.2019, 20:38
	JavaDoc, теоретически могут взять. Но этапы отбора надо продлить. А вообще можно многое. Хоть в одну строчку. Ограничений по количеству строк ведь в задании нет. 0

@ArtemFM 746 / 493 / 285 Регистрация: 10.09.2015 Сообщений: 1,530
	11.04.2019, 20:45
	JavaDoc, так напиши, а пока это слова 0

@wolfbethowen 6 / 4 / 2 Регистрация: 09.01.2018 Сообщений: 59
	11.04.2019, 21:01 [ТС]
	JavaDoc, да у меня как бы 140 строк со всяким шлаком. можно до 100 уменьшить. но здесь не меряются длиной кода, к счастью. есть идеи, покажи. Добавлено через 56 секунд Dmitry_Barynov, когда пойдешь на собеседование? 0

@ArtemFM 746 / 493 / 285 Регистрация: 10.09.2015 Сообщений: 1,530
	11.04.2019, 21:02
	универсальная программа, где не будет магических чисел и магических символов и строк в методах в 160 строк без лямбд и где будет не всё в одном методе... хмм... С радостью посмотрю на код 0