Читайте также:
|
|
Рассмотрим произвольное арифметическое выражение. Теперь сотрем в этом выражении всё кроме скобок. Получившуюся последовательность из скобок будем называть «правильной скобочной последовательностью». Любая правильная скобочная последовательность состоит из равного числа открывающихся и закрывающихся скобок. Но этого условия недостаточно: например, скобочная последовательность «(())» является правильной, а последовательность «)()(» -- нет.
Можно дать и точное определение правильной скобочной последовательности.
Обозначим количество правильных скобочных последовательностей длины 2 n (то есть содержащих n открывающихся и n закрывающихся скобок) через C n и решим задачу нахождения C n по заданной величине n.
Для небольших n значения C n несложно вычислить полным перебором. C 0 = 1 (правильная скобочная последовательность длины 0 ровно одна -- пустая), C 1 = 1 (последовательность «()»), C 2 = 2 (последовательности «(())» и «()()»), C 3 = 5 («((()))», «(()())», «(())()», «()(())», «()()()»).
Запишем рекуррентную формулу для C n. Пусть X -- произвольная правильная скобочная последовательность длины 2 n. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность X в виде:
X = (A) B,
где A и B -- тоже правильные скобочные последовательности. Если длина последовательности A равна 2 k, то последовательность A можно составить C k способами. Тогда длина последовательности B равна 2(n - k - 1) и последовательность B можно составить C n - k - 1 способами. Комбинация любого способа составить последовательность A с любым способом составить последовательность B даст новую последовательность X, а величина k может меняться от 0 до n - 1. Получили рекуррентное соотношение:
C n = C 0 C n - 1 + C 1 C n - 2 + C 2 C n - 3 +...+ C n - 2 C 1 + C n - 1 C 0.
Напишем функцию, вычисляющую значение C n по данному n:
int Catalan(int n)
{
int C[n+1];
// Создаем массив для хранения C[m]
C[0]=1;
for (int m=1; m<=n; ++m) // Вычисляем C[m] для m=1..n
{
C[m]=0;
for (int k=0; k<m; ++k)
C[m]+=C[k]*C[m-1-k];
}
return C[n];
}
Мы назвали функцию Catalan, поскольку значения C n называются числами Каталана в честь бельгийского математика XIX века Евгения Шарля Каталана. Начало ряда чисел Каталана выглядит следующим образом:
n | |||||||||||
C n |
Для чисел Каталана хорошо известна и нерекуррентная формула:
C n = = .
Наибольшая общая подпоследовательность (НОП, Longest Common Subsequence, LCS)
Дата добавления: 2014-11-24; просмотров: 50 | Поможем написать вашу работу | Нарушение авторских прав |