Рубрики

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

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

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

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

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

#include <iostream>

using namespace std;

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

unsigned long int catalan(unsigned int n)

{

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

    if (n <= 1)

        return 1;

  

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

    unsigned long int res = 0;

    for (int i = 0; i < n; i++)

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

  

    return res;

}

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

int main()

{

    for (int i = 0; i < 10; i++)

        cout << catalan(i) << " ";

    return 0;

}

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

C ++

#include <iostream>

using namespace std;

  
// Функция на основе динамического программирования для поиска nth
// каталонский номер

unsigned long int catalanDP(unsigned int n)

{

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

    unsigned long int catalan[n + 1];

  

    // Инициализируем первые два значения в таблице

    catalan[0] = catalan[1] = 1;

  

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

    for (int i = 2; i <= n; i++) {

        catalan[i] = 0;

        for (int j = 0; j < i; j++)

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

    }

  

    // Возвращаем последнюю запись

    return catalan[n];

}

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

int main()

{

    for (int i = 0; i < 10; i++)

        cout << catalanDP(i) << " ";

    return 0;

}

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

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

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

0.00 (0%) 0 votes