Эта задачка была у нас на областной школьников. Мне понравилась тем, что если ее аккуратно проанализировать, то ответ находится в виде очень простой(хотя и рекурсивной) формулы.
Выражение состоит из символов 1, +, -, (, )
Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)"
Все сотальные выражения считаются неправильными.
Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.
Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.
Здравствуйте, mihoshi, Вы писали:
M>Выражение состоит из символов 1, +, -, (, ) M>Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)" M>Все остальные выражения считаются неправильными.
M>Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.
Насколько я помню, это числа Каталана.
M>Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.
Здравствуйте, Кодт, Вы писали:
M>>Дана строка, состоящая из 1, -, +. Найти, сколько в ней различных вариантов расстановки скобок, дающих правильное выражение.
К>В данной постановке ответ: ровно один: (-1)
OK.
... Дана строка, состоящая из некоторого числа символов 1, -, + ...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mihoshi, Вы писали:
M>>Выражение состоит из символов 1, +, -, (, ) M>>Выражение считается правильным (ПВ), если это "1" или "(-ПВ)" или "(ПВ+ПВ)" M>>Все остальные выражения считаются неправильными.
M>>Например, (-((1+1)+(-1))) — правильное выражение, -1 -неправильное, (1-1) тоже неправильное.
К>Насколько я помню, это числа Каталана.
По сути это задача из задачника Лаврова и Максимовой по мат. логике
(часть 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 []
Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму.
Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями
нерекурсивной формы вообще не существует).
Здравствуйте, leaf, Вы писали:
L>По сути это задача из задачника Лаврова и Максимовой по мат. логике L>(часть 2, параграф 1, задача 2 (страница 52))
L>-- можно записать и короче, применив функции высшего порядка, L>-- но это первое, что пришло в голову.
<>
prolog? refal?
L>Предлагаю народу усложненный вариант задачи: нужно найти её нерекурсивную форму. L>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями L>нерекурсивной формы вообще не существует).
Первое. Унарное отрицание не влияет на количество скобок.
(можно, я не буду доказывать?)
Следовательно, достаточно выбросить все знаки "-", убедившись только, что в строке не было последовательностей "-+" и "-." (где "." — конец строки).
Второе. Убедиться, что получилась строка "1" [{ "+" "1" }]
Число расстановок скобок для нее — это функция от количества цифр|плюсов.
Здравствуйте, 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>нерекурсивной формы вообще не существует).
Для одной операции + получалось действительно нерекурсивная фромула, вот только сейчас я ее уже не вспомню...
Здравствуйте, 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>Для одной операции + получалось действительно нерекурсивная фромула, вот только сейчас я ее уже не вспомню...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mihoshi, Вы писали:
M>>3. Открывающие скобки могут стоять только в конце и перед плюсом.
К>закрывающие.
M>>4. Открывающих скобок в каждой позиции может быть не более, чем кол-во операци1 левее минус кол-во закр. скоб. левее.
К>закрывающих.
Спасибо, разумеется.
К>оценка времени: O(n^2)
Скорее куб.
L>>>Хотя бы только для одной бинарной операции '+' (я уверен, что с двумя операциями L>>>нерекурсивной формы вообще не существует).
К>Какая принципиальная разница между одной и множеством бинарных операций?
Разница в том, что при различных операциях роляет их взаимное расположение. +- — один вариант, -+ — два.
Здравствуйте, mihoshi, Вы писали:
К>>оценка времени: O(n^2)
M>Скорее куб.
Таки квадрат. При каждой итерации (N штук) нужно вычислить сумму K[n] = K[1]K[n-1]+K[2]K[n-2]... (цикл из ]n/2[ итераций). Итого асимптотика N^2. (Сумма арифметической прогрессии).
К>>Какая принципиальная разница между одной и множеством бинарных операций?
M>Разница в том, что при различных операциях роляет их взаимное расположение. +- — один вариант, -+ — два.
Перекуём баги на фичи!
