[Stacks and Queues]08. Recursive Fibonacci
Колеги, някой който judge му е дал 100т., би ли бил така добър да си paste-не кода?
И на някой, ако му се обяснява, по по-прост начин какво е memoization technique. Че аз не можах да разбера нищо.
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). Има цяла тема за него, както и за рекурсия в курса по Алгоритми. Можеш да ги погледнеш, Наско обяснява много добре.
Ето примери с решението без мемоизация, с мемоизация и ако ти е трудна рекусията, има трети вариант, който прави абсолютно същото без рекурсия.
Общо взето кешираш текущото число на фибоначи в някакъв стек или хешмап и при всяко извикване на метода проверяваш дали числото не е в кеша, вместо да го преизчисляваш чрез рекурсия.
В псевдо-код, опростено би изглеждало нещо такова:
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
}
Ето още едно авторско решение: https://pastebin.com/ytEK0ZmR, надявам се да съм ти помогнал! Поздрави!
В тази тема споделям и курса по алгоритми на C# от 2019 на Ивайло Кенов, кoйто е оптимизиран и е съобразен с по-новата програма, в която след всяка лекция следва съответното упражнение. Предполагам, че тъй като материята е и за по-опитни програмисти, че най-удачния вариант за по-неопитните ще е да гледат паралелно и двата курса. :)
https://softuni.bg/trainings/2459/algorithms-july-2019-online
До този момент това е най-последното издания на курса по алгоритми в Софтуерния университет.