Рубрики

Программа Python для n-го каталонского номера

Каталонские числа представляют собой последовательность натуральных чисел, которая встречается во многих интересных проблемах подсчета, таких как следующие.

1) Подсчитайте количество выражений, содержащих n пар скобок, которые правильно сопоставлены. Для n = 3 возможными выражениями являются ((())), () (()), () () (), (()) (), (() ()).

2) Подсчитайте количество возможных деревьев бинарного поиска с n ключами (см. Это )
Смотрите это для других приложений.

Первые несколько каталонских чисел для n = 0, 1, 2, 3,… являются 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…

# Рекурсивная функция для поиска n-го каталонского числа

def catalan(n):

    # Базовый вариант

    if n <= 1 :

        return 1 

  

    # Каталанский (n) - сумма каталанского (i) * каталонского (ni-1)

    res = 0 

    for i in range(n):

        res += catalan(i) * catalan(n-i-1)

  

    return res

  
Программа # Driver для проверки вышеуказанной функции

for i in range(10):

    print catalan(i),

# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

Выход:

1 1 2 5 14 42 132 429 1430 4862

Решение для динамического программирования
Мы можем заметить, что вышеописанная рекурсивная реализация выполняет много повторяющихся операций (мы можем сделать то же самое, рисуя дерево рекурсии). Поскольку существуют перекрывающиеся подзадачи, мы можем использовать для этого динамическое программирование. Ниже приводится реализация, основанная на динамическом программировании на C ++.

питон

# Функция на основе динамического программирования, чтобы найти nth
# Каталонский номер

def catalan(n):

    if (n == 0 or n == 1):

        return 1

  

    # Таблица для хранения результатов подзадач

    catalan = [0 for i in range(n + 1)]

  

    # Инициализировать первые два значения в таблице

    catalan[0] = 1

    catalan[1] = 1

  

    # Заполните записи в каталонском [], используя рекурсивную формулу

    for i in range(2, n + 1):

        catalan[i] = 0

        for j in range(i):

            catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]

  

    # Вернуть последнюю запись

    return catalan[n]

  
# Код драйвера

for i in range (10):

    print (catalan(i))

# Этот код предоставлен Адити Шарма

Выход:

1
1
2
5
14
42
132
429
1430
4862

Пожалуйста, обратитесь к полной статье о программе для n-го каталонского номера для более подробной информации!

Рекомендуемые посты:

Программа Python для n-го каталонского номера

0.00 (0%) 0 votes