Скобки
От: mihoshi Россия  
Дата: 24.01.03 08:38
Оценка:
Эта задачка была у нас на областной школьников. Мне понравилась тем, что если ее аккуратно проанализировать, то ответ находится в виде очень простой(хотя и рекурсивной) формулы.

Выражение состоит из символов 1, +, -, (, )
Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)"
Все сотальные выражения считаются неправильными.

Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.

Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.
Re: Скобки
От: Кодт Россия  
Дата: 24.01.03 08:56
Оценка:
Здравствуйте, mihoshi, Вы писали:

M>Выражение состоит из символов 1, +, -, (, )

M>Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)"
M>Все остальные выражения считаются неправильными.

M>Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.


Насколько я помню, это числа Каталана.

M>Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.


В данной постановке ответ: ровно один: (-1)
Перекуём баги на фичи!
Re[2]: Скобки
От: mihoshi Россия  
Дата: 24.01.03 09:09
Оценка:
Здравствуйте, Кодт, Вы писали:

M>>Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.


К>В данной постановке ответ: ровно один: (-1)


OK.

... Дана строка, состоящая из некоторого числа символов 1, -, + ...
Re[2]: Скобки
От: mihoshi Россия  
Дата: 24.01.03 09:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, mihoshi, Вы писали:


M>>Выражение состоит из символов 1, +, -, (, )

M>>Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)"
M>>Все остальные выражения считаются неправильными.

M>>Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.


К>Насколько я помню, это числа Каталана.


Похоже, но не совсем.
Re: Скобки
От: leaf  
Дата: 31.01.03 12:46
Оценка: 20 (2)
По сути это задача из задачника Лаврова и Максимовой по мат. логике
(часть 2, параграф 1, задача 2 (страница 52))

-- можно записать и короче, применив функции высшего порядка,
-- но это первое, что пришло в голову.
-- грубо говоря, строка разбивается по знаку '+' (вроде дерева разбора)
-- первый аргумент — конечная часть строки,
-- второй — начальная часть строки.
-- рекурсия по первому аргументу.
-- вызывать так: count "1+-1+1+1"
-- пробелы не допускаются
skobki [] _ = 0
skobki ['1'] [] = 1
skobki ('-':t) [] = skobki t [] + skobki t ['-']
skobki ('+':t) leftpart = skobki t (leftpart ++ ['+']) +
count leftpart * count t
skobki (h:t) leftpart = skobki t (leftpart ++ [h])

count l = skobki l []


Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.
Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями
нерекурсивной формы вообще не существует).
Re[2]: Скобки
От: Кодт Россия  
Дата: 31.01.03 13:31
Оценка: 33 (2)
Здравствуйте, leaf, Вы писали:

L>По сути это задача из задачника Лаврова и Максимовой по мат. логике

L>(часть 2, параграф 1, задача 2 (страница 52))

L>-- можно записать и короче, применив функции высшего порядка,

L>-- но это первое, что пришло в голову.
<>
prolog? refal?

L>Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.

L>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями
L>нерекурсивной формы вообще не существует).

Первое. Унарное отрицание не влияет на количество скобок.
(можно, я не буду доказывать?)
Следовательно, достаточно выбросить все знаки "-", убедившись только, что в строке не было последовательностей "-+" и "-." (где "." — конец строки).

Второе. Убедиться, что получилась строка "1" [{ "+" "1" }]
Число расстановок скобок для нее — это функция от количества цифр|плюсов.

1 == 1 === 1
11 == (11) === 1
111 == (11)1, 1(11) === 2
1111 == (111)1, 1(111), (11)(11) === 2+2+1 == 5
11111 == (1111)1, (111)(11), (11)(111), 1(1111) === 5+2+2+5 == 14
111111 == (11111)1, (1111)(11), (111)(111), (11)(1111), 1(11111) == 14+5+2*2+5+14 == 42

Эта последовательность (1,1,2,5,14,42...) -- числа Каталана.
http://www.combinatorics.by.ru/katalan.htm
K[1] = 1
K[n] = K[1]K[n-1] + K[2]K[n-2] + ... + K[n-2]K[2] + K[n-1]K[1]

K[n] = (4n-2)!!!!/(n+1)!
(где !!!! — обобщенный факториал: n!!!! = 1*(1+4)*(1+4*2)*(1+4*3)*...*n', n' <= n)

Очевидно, есть простой итерационный способ вычислить это значение.
Перекуём баги на фичи!
Re[2]: Скобки
От: mihoshi Россия  
Дата: 31.01.03 13:36
Оценка:
Здравствуйте, leaf, Вы писали:

L>По сути это задача из задачника Лаврова и Максимовой по мат. логике

L>(часть 2, параграф 1, задача 2 (страница 52))
...
L> count leftpart * count t
L>skobki (h:t) leftpart = skobki t (leftpart ++ [h])

L>count l = skobki l []


Даа... Спасибо, но все гораздо проще.

1. Единицы не несут информации. Вычеркиваем.

2. Открывающие скобки не несут информации (из можно восстановить по закрывающим). Вычеркиваем.

3. Открывающие скобки могут стоять только в конце и перед плюсом.

4. Открывающих скобок в каждой позиции может быть не более, чем кол-во операци1 левее минус кол-во закр. скоб. левее.

5. Любое расположение скобок,удовлетворяющих 3. и 4. соответствует ровно одной правильному выражению.

Итого имеем некоторое количество позиций (кол-во плюсов+1). Для каждой позиции записываем кол-во операций левее. Получаем строку чисел, скажем, M(n).

Кол-во вариантов размещения k скобок (закрывающих, вестимо) в позициях до n включительно обозначим F(n,k)

F(n,k) = sum{n'<n, k'<=k, k'<=M(n')} (F(n', k'))

F(1,k) = 1, если k<=M(1)

Как видим очень простая реализация, без всяких деревьев и лексического анализа строки

L>

L>Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.
L>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями
L>нерекурсивной формы вообще не существует).

Для одной операции + получалось действительно нерекурсивная фромула, вот только сейчас я ее уже не вспомню...
Re[3]: Скобки
От: Кодт Россия  
Дата: 31.01.03 14:24
Оценка:
Здравствуйте, mihoshi, Вы писали:

M>1. Единицы не несут информации. Вычеркиваем.


ок.

M>2. Открывающие скобки не несут информации (из можно восстановить по закрывающим). Вычеркиваем.


ок.

M>3. Открывающие скобки могут стоять только в конце и перед плюсом.


закрывающие.

M>4. Открывающих скобок в каждой позиции может быть не более, чем кол-во операци1 левее минус кол-во закр. скоб. левее.


закрывающих.

M>5. Любое расположение скобок,удовлетворяющих 3. и 4. соответствует ровно одной правильному выражению.


M>Итого имеем некоторое количество позиций (кол-во плюсов+1). Для каждой позиции записываем кол-во операций левее. Получаем строку чисел, скажем, M(n).


оценка расхода памяти: O(n)

M>Кол-во вариантов размещения k скобок (закрывающих, вестимо) в позициях до n включительно обозначим F(n,k)


M>F(n,k) = sum{n'<n, k'<=k, k'<=M(n')} (F(n', k'))


M>F(1,k) = 1, если k<=M(1)


оценка времени: O(n^2)

M>Как видим очень простая реализация, без всяких деревьев и лексического анализа строки


L>>Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.


Эйлер, а затем Каталан, сделали это еще в 18 веке.

L>>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями

L>>нерекурсивной формы вообще не существует).

Какая принципиальная разница между одной и множеством бинарных операций?

Обозначим "местоимение" операции знаком *.
Количество расстановок скобок вокруг цифр и * -- мы умеем вычислять.

Осталось заменить * на реальные операции. В зависимости от условий задачи...
  • каждая операция произвольна — получаем V = b^n (где b — мощность ассортимента, n — число мест)
  • каждая операция зафиксирована на своем месте — получаем 1
  • имеются n1 знаков "+", n2 знаков "-" и т.д., общим числом n.
    V = C(n1,n)*C(n2,n-n1)*C(n3,n-n1-n2) ... * C(n[b],n[b])
    (факториалы сокращаются... сокращаются факториалы... в элегантные шорты).
    Для ассортимента из 2 операций V = C(n1,n1+n2) == C(n2,n1+n2).

    M>Для одной операции + получалось действительно нерекурсивная фромула, вот только сейчас я ее уже не вспомню...


    См. мое предыдущее письмо.
  • Перекуём баги на фичи!
    Re[4]: Скобки
    От: mihoshi Россия  
    Дата: 31.01.03 15:54
    Оценка:
    Здравствуйте, Кодт, Вы писали:

    К>Здравствуйте, mihoshi, Вы писали:


    M>>3. Открывающие скобки могут стоять только в конце и перед плюсом.


    К>закрывающие.


    M>>4. Открывающих скобок в каждой позиции может быть не более, чем кол-во операци1 левее минус кол-во закр. скоб. левее.


    К>закрывающих.


    Спасибо, разумеется.

    К>оценка времени: O(n^2)


    Скорее куб.

    L>>>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями

    L>>>нерекурсивной формы вообще не существует).

    К>Какая принципиальная разница между одной и множеством бинарных операций?


    Разница в том, что при различных операциях роляет их взаимное расположение. +- — один вариант, -+ — два.
    Re[5]: Скобки
    От: Кодт Россия  
    Дата: 31.01.03 16:17
    Оценка:
    Здравствуйте, mihoshi, Вы писали:

    К>>оценка времени: O(n^2)


    M>Скорее куб.


    Таки квадрат. При каждой итерации (N штук) нужно вычислить сумму K[n] = K[1]K[n-1]+K[2]K[n-2]... (цикл из ]n/2[ итераций). Итого асимптотика N^2. (Сумма арифметической прогрессии).

    К>>Какая принципиальная разница между одной и множеством бинарных операций?


    M>Разница в том, что при различных операциях роляет их взаимное расположение. +- — один вариант, -+ — два.


    1+(-1)
    (-1)+1, -(1+1)

    Дааа... Думаем дальше.
    Перекуём баги на фичи!
     
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.