[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). Има цяла тема за него, както и за рекурсия в курса по Алгоритми. Можеш да ги погледнеш, Наско обяснява много добре.
Ето примери с решението без мемоизация, с мемоизация и ако ти е трудна рекусията, има трети вариант, който прави абсолютно същото без рекурсия.
В тази тема споделям и курса по алгоритми на C# от 2019 на Ивайло Кенов, кoйто е оптимизиран и е съобразен с по-новата програма, в която след всяка лекция следва съответното упражнение. Предполагам, че тъй като материята е и за по-опитни програмисти, че най-удачния вариант за по-неопитните ще е да гледат паралелно и двата курса. :)
https://softuni.bg/trainings/2459/algorithms-july-2019-online
До този момент това е най-последното издания на курса по алгоритми в Софтуерния университет.