@Wolfbethowen

Проблема со скобками)))))))?

В сборниках занимательных математических задач встречается такой тип задач, когда надо из заданных чисел и арифметических знаков составить выражение, дающее какое-то заданное число. Пример такой задачи: "Составьте из чисел 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

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

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]  );
 
 
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
 
 
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
  • Вопрос задан
  • 486 просмотров
Пригласить эксперта
Ответы на вопрос 2
dollar
@dollar
Делай добро и бросай его в воду.
Я не специалист по Java, но ответ - рекурсия.
Можно и без неё, с эмуляцией стека в массиве, но это по сути то же самое.
Это решает проблему огромной вложенности одинаковых циклов.

Также очень советую изучить формат RPN - он вам значительно упростит как перебор вариантов, так и вычисления. Например, ваш ответ (8-4) * (7-1) будет выглядеть, как массив 8, 4, -, 7, 1, -, *. Скобки исчезают. Задача сводится к перестановке 4 цифр в 7 позициях и перебору операций в оставшихся. Не все варианты валидны, но как именно оптимизировать, и надо ли оно вам или просто чтоб работало - решайте уже сами.
Ответ написан
Комментировать
longclaps
@longclaps
Я не специалист по Java, но ответ - python.
from itertools import permutations, product
from operator import add, sub, mul, truediv

def f(data):
    oops, res = (add, sub, mul, truediv), {}
    sign = {add: '+', sub: '-', mul: '*', truediv: '/'}
    for t in permutations(data):
        for order in product([0, 1, 2], [0, 1], [0]):
            for ops in product(oops, repeat=3):
                try:
                    ll, ss = list(map(float, t)), list(map(str, t))
                    for i, op in zip(order, ops):
                        ll[i:i + 2] = [op(*ll[i:i + 2])]
                        ss[i:i + 2] = [f'({ss[i]}{sign[op]}{ss[i + 1]})']
                    if ll[0].is_integer():
                        res[int(ll[0])] = ss[0][1:-1]
                except ZeroDivisionError:
                    pass
    return res

for x, s in sorted(f([4, 1, 8, 7]).items()):
    print(f'{x:>4} : {s}')

Фрагмент вывода (там слишком много):
20 : 7+(8+(1+4))
21 : 7*(8-(1+4))
22 : ((7/4)+1)*8
23 : ((7-4)*8)-1
24 : (7-1)*(8-4)
25 : ((7-4)*8)+1
26 : (8*4)-(7-1)
27 : (7*(8-4))-1
28 : 7*(8-(1*4))
29 : (7*(8-4))+1
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽
29 мар. 2024, в 15:11
50000 руб./за проект
29 мар. 2024, в 15:06
50000 руб./за проект