Рубрики

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

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

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

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

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

<?php
// PHP программа для nth
// каталонский номер

  
// Рекурсивная функция для
// найти номер каталонца

function catalan($n)

{

      

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

    if ($n <= 1)

        return 1;

  

    // каталонский (n) является суммой

    // каталанский (i) * каталанский (ni-1)

    $res = 0;

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

        $res += catalan($i) * 

                catalan($n - $i - 1);

  

    return $res;

}

  

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

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

        echo catalan($i), " ";

  
// Этот код добавлен aj_36
?>

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

PHP

<?php
// PHP-программа для n-го каталонского номера

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

function catalanDP( $n)

{

      

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

    // подзадач

    $catalan= array();

  

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

    // значения в таблице

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

  

    // Заполняем записи в каталонском []

    // используя рекурсивную формулу

    for ($i = 2; $i <= $n; $i++)

    {

        $catalan[$i] = 0;

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

            $catalan[$i] += $catalan[$j] * 

                   $catalan[$i - $j - 1];

    }

  

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

    return $catalan[$n];

}

  

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

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

        echo catalanDP($i), " ";

  
// Этот код предоставлен anuj_67.
?>

Выход:

1 1 2 5 14 42 132 429 1430 4862

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

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

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

0.00 (0%) 0 votes