fib(n) = fib(n − 1) + fib(n − 2). Нэг дуудлага хоёр шинэ дуудлага үүсгэдэг тул recursion tree хурдан томордог.

Pre-IntermediateХугацаа: O(2ⁿ)Санах ой: O(n) (дуудлагын стек)
HackerRank дээр бодох

Эхлээд жижиг бодлого

fib(4) хэд вэ? fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), fib(2) = fib(1) + fib(0). fib(1) = 1, fib(0) = 0.

Доороос нь бодвол fib(2) = 1, fib(3) = 2, fib(4) = 3. Гэхдээ function нийт 9 удаа дуудагдана, fib(2) хоёр удаа бодогдоно.

Энгийн аргаас санаа руу

Томьёог шууд кодонд буулгавал хамгийн энгийн recursion гарна: return fib(n - 1) + fib(n - 2);. Бичихэд амар ч нэг дуудлага хоёр шинэ дуудлага үүсгэдэг тул recursion tree хурдан томорно.

fib(n)-ийг бодоход 2·fib(n + 1) − 1 дуудлага хийгддэг. fib(40)-ийг бодоход 300 сая гаруй дуудлага болно. Шалтгаан нь ижил утгыг дахин дахин бодох. Хариуг нэг удаа бодоод хадгалбал (memoization, DP) n удаа л бодно. Энэ animation яг тэр давталтыг харуулахад зориулагдсан.

Нэр томьёо ба тэмдэглэгээ

fib(n)
n дэх Фибоначчийн тоо: 0, 1, 1, 2, 3, 5, 8…
base case
n < 2 бол хариу нь n өөрөө.
recursion tree
Дуудлага бүр нэг цэг, түүний дуудсан дуудлагууд доод талд нь байдаг зураг.
a, b
a = fib(n - 1), b = fib(n - 2). Хариу нь a + b.
n = 4
Call stack
хоосон

fib(n) = fib(n − 1) + fib(n − 2). Эхний хоёр нь fib(0) = 0, fib(1) = 1. Нэг дуудлага хоёр шинэ дуудлага үүсгэнэ.

Алхам 1 / 19
Хурд
  • Ажиллаж буй дуудлага
  • Хариу хүлээж буй
  • Base case
  • Хариугаа өгсөн
Слайд 1 / 6

Фибоначчийн тоо

0, 1, 1, 2, 3, 5, 8 … Дараагийн тоо бүр өмнөх хоёрынхоо нийлбэр: fib(n) = fib(n − 1) + fib(n − 2).

fibonacci-recursion.cpp
#include <bits/stdc++.h>
using namespace std;
int fib(int n) {
if (n < 2) return n;
int a = fib(n - 1);
int b = fib(n - 2);
return a + b;
}
int main() {
int n;
cin >> n;
cout << fib(n) << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Фибоначчийн дарааллын fib(n)-ийг recursion ашиглан олно. Recursion tree-г харж, ижил дуудлага олон дахин бодогддогийг анзаарна. Ингэснээр DP яагаад хэрэгтэйг мэдэрнэ.

Яаж ажилладаг вэ?

1. Эхний хоёр тоо: fib(0) = 0, fib(1) = 1. n < 2 бол шууд n-ийг буцаана. 2. Үгүй бол fib(n − 1)-ийг бодож a-д хадгална. 3. Дараа нь fib(n − 2)-ыг бодож b-д хадгална. 4. a + b-г буцаана. Анхаар: fib(2), fib(1) гэх мэт ижил дуудлага олон дахин бодогддог. n = 40 үед 300 сая гаруй дуудлага болно. Үүнийг DP хурдасгадаг. Оролт: нэг тоо n.

Яагаад зөв, хэр хурдан бэ?

fib(0), fib(1) хоёр шууд зөв. n-ээс бага бүх утгыг зөв бодно гэвэл fib(n) = fib(n − 1) + fib(n − 2) нь яг томьёо тул зөв. Индукцаар бүх n-д зөв.

Дуудлагын тоо fib(n) шиг өсдөг. n нэгээр нэмэгдэх бүрт ойролцоогоор 1.6 дахин олон болно: хугацаа O(1.6ⁿ). n = 30 бол 2.7 сая, n = 40 бол 330 сая дуудлага. Call stack-ийн гүн нь n тул санах ой O(n).

Түгээмэл алдаа

  • Энэ кодыг n = 50 дээр ажиллуулах. Хэдэн минут болж time limit-ээс хэтэрнэ. Memoization эсвэл loop хэрэглэ.
  • int ашиглах. fib(47) нь int-ээс хэтэрнэ. Том n бол long long ав.
  • Base case-д зөвхөн n == 1 шалгах. fib(0) дуудагдахад зогсохгүй.

Хязгаарын тохиолдол

  • n = 0: шууд 0 буцаана, нэг л дуудлага.
  • n = 1: шууд 1 буцаана.
  • n = 2: 3 дуудлага, хариу 1.

Өөрийгөө шалга

  1. fib(5)-ыг бодоход function хэдэн удаа дуудагдах вэ?

    Хариу харах

    15 удаа. 2 · fib(6) − 1 = 2 · 8 − 1 = 15.

  2. fib(4)-ийг бодоход fib(2) хэдэн удаа бодогдох вэ?

    Хариу харах

    2 удаа: fib(3) дотор нэг, fib(4)-ийн баруун талд нэг.

  3. fib(10) хэд вэ?

    Хариу харах

    55.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.fib(5)-ын recursion tree-г зур. Навч болсон fib(1), fib(0) тус бүр хэд вэ?

    Hint харах

    Навчнуудын нийлбэр хариутай тэнцүү.

    Хариу ба тайлбар

    fib(1) 5 удаа, fib(0) 3 удаа гарна. Навчны нийлбэр 5 · 1 + 3 · 0 = 5 = fib(5).

  2. 2.Хариуг array-д хадгалдаг болгож (memoization) кодыг хурдасга.

    Hint харах

    memo[n]-ийг −1-ээр дүүргээд, бодсон бол шууд буцаа.

    Хариу ба тайлбар

    if (memo[n] != -1) return memo[n]; return memo[n] = fib(n - 1) + fib(n - 2);. Утга бүрийг нэг удаа бодох тул O(n). fib(90) хүртэл long long-д багтана.

  3. 3.n шаттай шатаар нэг эсвэл хоёр шатаар алхаж өгсөнө. Хэдэн янзаар өгсөх вэ? n = 4 бол?

    Hint харах

    Сүүлийн алхам 1 эсвэл 2 шат. Тэгэхээр ways(n) = ways(n − 1) + ways(n − 2).

    Хариу ба тайлбар

    ways(1) = 1, ways(2) = 2 гэвэл ways(3) = 3, ways(4) = 5. Энэ нь fib(n + 1)-тэй тэнцүү.

Жишээ

Оролт

4

Гаралт

3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.