Професионална програма
Loading...
+ Нов въпрос
TodorKMitov avatar TodorKMitov 2 Точки

4. Tribonacci Sequence - hint моля

Здравейте! Някой решил ли е 4. Tribonacci Sequence от Functions More Exercises, и ако ДА, моля да сподели стартегия за решаване на тази задача. Не ми трябва код, просто подход към решението. Благодаря предварително!

Тагове:
0
Python Fundamentals
willystyle avatar willystyle 2417 Точки

Здрасти Тоше,

за задачите от този тип с редици за които n-тия член е някаква функция на предходните (най-често използвания пример е с редицата на Фибоначи) може да се подходи по два начина:
1) Итеративно (с цикли)

2) Рекурсивно, тук задължително се ползва мемоизация (пазене в речник(мап) на изчислените вече членове), понеже иначе е неефективно и ще излезеш от лимита за време.

Твърдиш, че не ти трябва код, но погледни на решенията като на псевдо код, понеже не ползвам Питон, ти пускам на JS и PHP (с двата вида подход), ако направиш рекурсивното решение на Питон, тъкмо ще разучиш и как се ползва там кложър :)

function solveIteractive(n) {
    let tribs = [1, 1, 2];
    if (n <= 3) {
        tribs = tribs.slice(0, n - 1);
    } else {
        for (let index = 3; index < n; index++) {
            tribs.push(tribs[index - 1] + tribs[index - 2] + tribs[index - 3]);
        }
    }
    console.log(tribs.join(' '));
}

function solveRecursive(n) {
    let tribs = [1, 1, 2];
    let result = [];
    for (let i = 0; i < n; i++) {
        result.push(findNth(i));

    }
    console.log(result.join(' '));

    function findNth(n) {
        if (n in tribs) return tribs[n];
        tribs[n] = findNth(n - 1) + findNth(n - 2) + findNth(n - 3);
        return tribs[n];
    }
}
<?php
function solve($n) {
    $tribs = [1, 1, 2];
    if ($n <= 3) {
        $tribs = array_slice($tribs, 0, $n);
    } else {
        for ($index = 3; $index < $n; $index++) {
            $tribs[] = $tribs[$index - 1] + $tribs[$index - 2] + $tribs[$index - 3];
        }
    }
    echo implode(' ', $tribs);
}

$n = intval(readline());
solve($n);

function solveRecursive($n) {
    $tribs = [1, 1, 2];
    $findNth = function ($n) use (&$findNth, &$tribs) {
        if (key_exists($n, $tribs)) return $tribs[$n];
        $tribs[$n] = $findNth($n - 1) + $findNth($n - 2) + $findNth($n - 3);
        return $tribs[$n];
    };

    $result = [];
    for ($i = 0; $i < $n; $i++) {
        $result[] = $findNth($i);

    }
    echo implode(' ', $result);

}

$n = intval(readline());
solveRecursive($n);

 

1