Професионална програма
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 60 Точки

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

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

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

0
17/09/2020 13:09:23