Рубрики

PHP-программа для подсчета способов достижения н / й лестницы

Есть n лестниц, человек, стоящий внизу, хочет достичь вершины. Человек может подняться на 1 или 2 ступеньки одновременно. Подсчитайте количество способов, которыми человек может достичь вершины.

Рассмотрим пример, показанный на диаграмме. Значение n равно 3. Есть 3 способа достичь вершины. Диаграмма взята из пазлов Легче Фибоначчи

PHP

<?php
// PHP-программа для подсчета
// количество способов достичь
// н ая ступенька, когда человек
// можем подняться на 1, 2, ..м ступеньки
// вовремя.

  
// Простая рекурсивная
// функция для поиска n
// число Фибоначчи

function fib($n)

{

if ($n <= 1)

    return $n;

return fib($n - 1) + 

       fib($n - 2);

}

  
// Возвращает количество
// способы добраться до лестницы

function countWays($s)

{

    return fib($s + 1);

}

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

$s = 4;

echo "Number of ways = "

           countWays($s);

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

Выход:

Number of ways = 5

Временная сложность вышеописанной реализации является экспоненциальной (золотое сечение повышено до степени n). Он может быть оптимизирован для работы за время O (Logn) с использованием ранее обсужденных оптимизаций функции Фибоначчи .

PHP

<?php
// PHP-программа для подсчета
// количество способов достичь
// н ая ступенька, когда человек
// может подняться либо на 1, либо на 2
// лестницы за один раз

  
// рекурсивная функция
// используется countWays

function countWaysUtil($n, $m)

{

    if ($n <= 1)

        return $n;

    $res = 0;

    for ($i = 1; $i <= $m && 

                 $i <= $n; $i++)

        $res += countWaysUtil($n - $i, $m);

    return $res;

}

  
// Возвращает количество способов
// чтобы добраться до лестницы

function countWays($s, $m)

{

    return countWaysUtil($s + 1, $m);

}

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

$s = 4; $m = 2;

echo "Nuber of ways = ",

      countWays($s, $m);

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

Выход:

Nuber of ways = 5

PHP

<?php
// PHP-программа для подсчета числа
// способов добраться до лестницы, когда
// человек может подняться на 1, 2, ..м
// лестницы за один раз

  
// Рекурсивная функция, используемая countWays

function countWaysUtil($n, $m)

{

    $res[0] = 1; $res[1] = 1;

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

    {

        $res[$i] = 0;

        for ($j = 1; $j <= $m && $j <= $i; $j++)

        $res[$i] += $res[$i - $j];

    }

    return $res[$n - 1];

}

  
// Возвращает количество способов
// чтобы добраться до лестницы

function countWays($s, $m)

{

    return countWaysUtil($s + 1, $m);

}

  

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

    $s = 4; 

    $m = 2;

    echo "Nuber of ways = ", countWays($s, $m);

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

Выход:

Nuber of ways = 5

Пожалуйста, обратитесь к полной статье о способах подсчета, чтобы добраться до n-й ступени, чтобы узнать больше!

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

PHP-программа для подсчета способов достижения н / й лестницы

0.00 (0%) 0 votes