Всички ние сме направили програмата за изчисляване на сумата от редицата на Фибоначи в часовете по програмиране в нашето училище или университет.
Но винаги е имало голяма вратичка в начина, по който пишем нашите серии на Фибоначи. Нека се потопим малко по-дълбоко в концепцията и различните движещи се части.
Ето нормалния код, който един програмист би написал за Фибоначи, използвайки рекурсия.
Въпреки че това може да изглежда напълно добре и осигурява правилния резултат, в същото време страда от проблема с някои ненужни повиквания!
И така, какъв е проблемът с този код?
Ако изградим дървото на общия брой извиквания, направени от тази функция, то изглежда по следния начин:
Съвсем ясно е, че има прекомерен брой обаждания, които изобщо не са необходими. Функцията се извиква 2, 3 пъти, а за 0 и 1 многократно. Това прави кода не толкова ефективен. Трябва да намерим някакъв начин, по който можем да елиминираме тези повтарящи се извиквания на функцията.
И така, това, което ще направим, е да отидем в Google и да потърсим най-добрия подход и след това да копираме и поставим кода!
Хааааа! Майтапя се. Моите извинения за PJ.
Нека видим по-добър подход сега.
Ако направим масив и продължим да съхраняваме резултата от извикванията, тогава няма да е необходимо да правим повиквания за едно и също цяло число отново и отново.
И така, нека направим нов масив и засега инициализираме всички стойности на -1.
И след това, след като всяка функция върне обратно стойността, ние ще я съхраним в съответния елемент на масива.
Преди да направим по-нататъшно извикване, ще проверим дали имаме стойността на функцията за това конкретно число, която вече е съхранена в масив. Ако го имаме, няма да направим друго обаждане, в противен случай ще се обадим.
А ето и дървото с по-добър подход.
Всички червени кръстове означават, че тези повиквания няма да бъдат направени, тъй като всички тези функционални стойности вече са съхранени в масива arr. Тази техника за съхраняване на извиквания на функции за елиминиране на повтарящи се повиквания се нарича мемоизация.
И това е вашата подобрена версия на кода!
Насладете се на Buds!
Ето някои от моите профили, ако искате да се свържете с този маниак!
