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

[Stacks and Queues]08. Recursive Fibonacci

Колеги, някой който judge му е дал 100т., би ли бил така добър да си paste-не кода?

И на някой, ако му се обяснява, по по-прост начин какво е memoization technique. Че аз не можах да разбера нищо.

Тагове:
1
Java Advanced
krisdx avatar krisdx 67 Точки
Best Answer

Здравей,

Предполагам си измислил решението, което е без мемоизация:


 private static long recursiveFibonacci(int n)  {
        if (n <= 1) {
            return 1;
        } 
        return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
  }
 

Ако дебъгнеш решението ще видиш, че ще извиква n - 1, докато не стигне до 1. И на практика от n сме сметнали всички числа до 1. При n - 2, правиме горе-долу същото. Тоест проблема е, че изчисляваме доста пъти едни и същи неща и това е много бавно. 

И мемоизацията е просто едно масивче, където ако сметнеме някое число просто го запазваме. И така кагато примерно искаме да намериме 70-тото число на фибоначи, ще се спуснем един път и ще сме сметнали голяма част от числата който ни трябват. Това се нарича динамично оптимиране (DP). Има цяла тема за него, както и за рекурсия в курса по Алгоритми. Можеш да ги погледнеш, Наско обяснява много добре.

Ето примери с решението без мемоизация, с мемоизация и ако ти е трудна рекусията, има трети вариант, който прави абсолютно същото без рекурсия.

8
23/05/2016 12:07:59
Elena123456 avatar Elena123456 63 Точки

В тази тема споделям и курса по алгоритми на C# от 2019 на Ивайло Кенов, кoйто е оптимизиран и е съобразен с по-новата програма, в която след всяка лекция следва съответното упражнение. Предполагам, че тъй като материята е и за по-опитни програмисти, че най-удачния вариант за по-неопитните ще е да гледат паралелно и двата курса. :)

https://softuni.bg/trainings/2459/algorithms-july-2019-online

До този момент това е най-последното издания на курса по алгоритми в Софтуерния университет.

0
17/09/2020 13:09:23
msmilkoff avatar msmilkoff 341 Точки

Общо взето кешираш текущото число на фибоначи в някакъв стек или хешмап и при всяко извикване на метода проверяваш дали числото не е в кеша, вместо да го преизчисляваш чрез рекурсия.
В псевдо-код, опростено би изглеждало нещо такова:
 

long fib(int num){

cache = new fibList

add 0 to cache

add 1 to cache

long result

if num is in fibList-> return result

else result = fib (num - 2) + fib(num - 1)

add (num, result) to cache

}

3
22/05/2016 23:24:12
mitkovasilev avatar mitkovasilev 8 Точки

Ето още едно авторско решение: https://pastebin.com/ytEK0ZmR, надявам се да съм ти помогнал! Поздрави!

0