• ,

Скобки

Одна из трех задачек заданных мне как домашнее задание перед собеседованием.

]Существует корректно записанное арифметического выражение, содержащее числа, знаки операций, открывающие и закрывающие круглые скобки. Если выбросить числа и знаки операций, а затем записать оставшиеся в выражении скобки без пробелов между ними, то полученный результат будет правильным скобочным выражением [скобочное выражение "(()(()))" — правильное, а "()(" и "())(" — нет].

Задача найти число правильных скобочных выражений, содержащих N открывающихся и N закрывающихся скобок. N вводится с клавиатуры.

N неотрицательное целое число.

Пример:
N = 1 (по одной скобке открывающейся и закрывающеся) — ответ 1
()
)(
))
((
Только один правильный вариант

Для введенного числа 2 — 2:
()()
(())
То есть только два варианта, когда все открытые скобки правильно открываются/закрываются.
И так далее.

">

11 комментариев

Joysi
  • Joysi
  • +1
  • Комментарий отредактирован 2017-02-09 09:36:42 пользователем Joysi
Это задача на комбинаторику, а не программирование.
Посмотрите числа Каталана.
Если необходимо их генерировать — то рекурсивно.
JuriMik
Да не вопрос. Но это задание, наряду с несколькими другими, имело место быть на позицию Trainee Developer в одну из харьковских компаний.
Antonbeast
Сорри не в Никс ли часом?
JuriMik
нет. в никс тестовых заданий вроде как нет
Joysi
Просто кажется, что это больше тест на понимание математики (в данном случае комбинаторики), а не программирования. Пример еще одной задачи из той же серии (которые решаются «на бумажке»): число счастливых автобусных билетов.

P.S. Антипример. Вспомнилась школьная олимпиадная задача — определить количество всевозможных партий в крестики-нолики на поле 3x3. Те кто ответили 9! сразу в пролете оказались…
astraboomer
Не оптимизировано, конечно, но работает:
public class Brackets {
    public static void main (String[] args) throws Exception
    {
        BufferedReader text = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(text.readLine());
        int arrSize = 2 * n;  // размер массива битов числа
        int count = 0;        // количество правильных скобочных выражений
        int nullFlag = 0, oneFlag = 0; // счетчики битов со значениями 0 и 1 (0 - открыв. скобка, 1 - закрыв.)
        byte[] bitArray = new byte[arrSize]; // массив битов целого числа
        int num = (int) Math.pow(2, arrSize) - 1; // макс. число, помещающееся в массив битов

        for (int k = num; k > 0; k--) { // перебор всех целых чисел
            int start = k;
            for (int i = 0; i < arrSize; i++) { // преобразуем целое число в массив битов (перевод в двоич. тип)
                bitArray[arrSize - 1 - i] = (byte) (start % 2);
                start = start / 2;
            }
            if (bitArray[0] == 0 && bitArray[arrSize - 1] == 1) { // крайние биты массивы должны быть 0 и 1 соотв.
                                                                  // т.е. крайн. левая скобка должна быть открывающей
                                                                  // и крайн. правая закрывающей
                for (int j = 1; j < arrSize - 1; j++) {
                    if (bitArray[j] == 0)
                        nullFlag++;
                    else
                        oneFlag++;
                }
                if (nullFlag == oneFlag) {
                    count++;
                    BracketOut(bitArray);
                }
                nullFlag = 0;
                oneFlag = 0;
            }
        }
        System.out.println(count);
    }

    public static void BracketOut (byte[] bitArray) // вывод массива в виде скобок
    {
        String result = "";
        for (byte bit: bitArray) {
            if (bit == 0) result = result.concat("("); else
                result = result.concat(")");
        }
        System.out.println(result);
    }
}
tonyloner
У тебя не хватает одной проверки :)

Вывод твоей задачи для n = 3:
3
())(()
()()()
()(())
(())()
(()())
((()))
6
astraboomer
Спасибо. Исправил.
public class Brackets {
    public static void main (String[] args) throws Exception
    {
        BufferedReader text = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(text.readLine());
        long startTime = new Date().getTime();
        int arrSize = 2 * n;  // размер массива битов числа
        int count = 0;        // количество правильных скобочных выражений
        int nullFlag = 0, oneFlag = 0; // счетчики битов со значениями 0 и 1 (0 - открыв. скобка, 1 - закрыв.)
        byte[] bitArray = new byte[arrSize]; // массив битов целого числа
        int num = (int) Math.pow(2, arrSize) - 1; // макс. число, помещающееся в массив битов

        l :for (int k = num / 2; k > 0; k--) { // перебор второй половины всех целых чисел, т.к. первая всегда
            int start = k;                      // в двоичном виде начинается с 1
            for (int i = 0; i < arrSize; i++) { // преобразуем целое число в массив битов (перевод в двоич. тип)
                bitArray[arrSize - 1 - i] = (byte) (start % 2);
                start = start / 2;
            }
            if (bitArray[0] == 0 && bitArray[arrSize - 1] == 1) { // крайние биты массивы должны быть 0 и 1 соотв.
                                                                  // т.е. крайн. левая скобка должна быть открывающей
                                                                  // и крайн. правая закрывающей
                for (int j = 1; j < arrSize - 1; j++) {           // считаем скобки.
                    if (bitArray[j] == 0)
                        nullFlag++;
                    else
                        oneFlag++;
                    if (nullFlag + 1 < oneFlag )                   // На любой итерации открывающих скобок должно
                    {                                              // быть не меньше закр-х (с учетом первой откр-щей)
                        nullFlag = 0;
                        oneFlag = 0;
                        continue l;
                    }
                }
                if (nullFlag == oneFlag) {
                    count++;
                    //BracketOut(bitArray);
                }
                nullFlag = 0;
                oneFlag = 0;
            }
        }
        long countTime = new Date().getTime() - startTime;
        System.out.println("Количество скобок для n = " + n + " : " + count + ". Затрачено мс времени на поиск : " +
                countTime);
    }

    public static void BracketOut (byte[] bitArray) // вывод массива в виде скобок
    {
        String result = "";
        for (byte bit: bitArray) {
            if (bit == 0) result = result.concat("("); else
                result = result.concat(")");
        }
        System.out.println(result);
    }
}
astraboomer
  • astraboomer
  • +1
  • Комментарий отредактирован 2017-02-10 15:29:08 пользователем astraboomer
Идея в том, чтоб представить скобки в виде набора битов. Как и бит скобка может принимать 2 значения:
открывающая и закрывающая. У меня 0 — это открывающая и 1 — закрывающая скобки. Пара скобок представляет собой 2 бита: 00 "((", 01 "()", 10 ")(" или 11 „))“.
4 скобки (2 пары) — это уже 4 бита и 2^4 = 16 вариантов различного расположения. И т.д.
При этом скобочное выражение правильное только тогда, когда крайняя левая скобка открывающая и
крайняя правая — закрывающая.

Пусть N=2. т.е. 2 пары скобок. Это 16 вариантов расположения скобок вообще.
Крайняя левая скобка всегда открывающая и крайняя правая — закрывающая. Значит
нужно перебрать все скобки (биты) между крайними и если их количество совпадет, то
это правильное скобочное выражение.
tonyloner
Сделал двумя способами. Узнав от Joysi , что задача про числа Каталана, реализовал рекуррентное выражение. А так же сделал так, как стал бы делать сам (получилось так же как у astraboomer ). Сравнил время — конечно же Каталан победил :)
Catalan:n=13 -> 742900 during 1ms
Me: 	n=13 -> 742900 during 2295ms


public class Brackets {

    public static void main(String[] args) {
        int n = 13;
        long startTime;
        startTime = new Date().getTime();
        System.out.printf("Catalan:n=%d -> %d during %dms\n", n, recursion(n), (new Date().getTime() - startTime));
        startTime = new Date().getTime();
        System.out.printf("Me: \tn=%d -> %d during %dms\n", n, myBrackets(n), (new Date().getTime() - startTime));
    }

    //Catalan number
    public static int recursion(int n) {
        if (n == 0)
            return 1;
        double result = 2d*(2*n - 1)/(n + 1)*recursion(n - 1);
        return (int) result;
    }

    public static int myBrackets(int n) {
        int cnt = 0;
        int[] array = new int[2*n];
        array[array.length-1] = 1;
        array[0] = 0;
        for(int i = 0; i < Math.pow(2, 2*n-2); i++) {
            for(int j = 1; j < array.length-1; j++) {
                if((i & (1 << (j-1))) == (1 << (j-1)))
                    array[j] = 1;
                else
                    array[j] = 0;
            }
            if(check(array))
                cnt++;
        }

        return cnt;
    }

    public  static boolean check(int[] array) {
        int open = 0;
        int close = 0;
        boolean error = false;
        for(int i = array.length-1; i >= 0; i--) {
            if(array[i] == 1)
                open++;
            else
                close++;
            if(close > open) {
                error = true;
                break;
            }
        }
        if(open == close && !error)
            return true;
        return  false;
    }

}
JuriMik
Да, я тоже делал через числа Каталана. Математика, конечно рулит, но теряется спортивный интерес, после того, как понимаешь, что проблема решается математической формулой :-D
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.