Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Числа Каталана

Читайте также:
  1. CTR — показатель эффективности интернет-рекламы, измеряемый как отношение числа нажатий на рекламное объявление (кликов) к числу показов этого объявления.
  2. Алгебраические формы представления целых знаковых двоичных чисел в компьютере и операции с этими числами
  3. Арифметические операции над числами.
  4. Арифметические операции с числами в формате с плавающей запятой.
  5. Атом водорода согласно квантовой механики. Квантовые числа электрона в атоме
  6. Болезни, связанные с нарушением числа половых хромосом
  7. В зависимости от числа альтернатив в разделительной посылке, условно-разделительные силлогизмы делятся на дилеммы, трилеммыи полилеммы.
  8. В следующих примерах поставьте в форме родительного падежа множественного числа существительные, помещенные в скобках.
  9. Вимагати заміни товару на такий же товар або на аналогічний, з числа наявних у продавця (виробника), товар.
  10. Выбор типа, числа и мощности генераторных агрегатов

Рассмотрим произвольное арифметическое выражение. Теперь сотрем в этом выражении всё кроме скобок. Получившуюся последовательность из скобок будем называть «правильной скобочной последовательностью». Любая правильная скобочная последовательность состоит из равного числа открывающихся и закрывающихся скобок. Но этого условия недостаточно: например, скобочная последовательность «(())» является правильной, а последовательность «)()(» -- нет.

Можно дать и точное определение правильной скобочной последовательности.

  1. Пустая последовательность (то есть не содержащая ни одной скобки) является правильной скобочной последовательностью.
  2. Если «A» -- правильная скобочная последовательность, то «(A)» (последовательность A, взятая в скобки) -- правильная скобочная последовательность.
  3. Если «A» и «B» -- правильные скобочные последовательности, то «AB» (подряд записанные последовательности A и B) -- правильная скобочная последовательность.

Обозначим количество правильных скобочных последовательностей длины 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 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав