{"id":410,"date":"2022-06-30T09:19:04","date_gmt":"2022-06-30T09:19:04","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=410"},"modified":"2024-05-17T20:31:18","modified_gmt":"2024-05-17T20:31:18","slug":"al-n-lea-termen-din-sirul-lui-fibonacci","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/al-n-lea-termen-din-sirul-lui-fibonacci\/","title":{"rendered":"Al n-lea termen din \u0219irul lui Fibonacci \u00een timp logaritmic"},"content":{"rendered":"\n

Un termen din \u0219irul lui Fibonacci se formeaz\u0103 din suma ultimilor doi dinaintea lui, iar primii doi termeni \u00eei consider\u0103m 1. \u0218irul lui Fibonacci arat\u0103 a\u0219a: 1 1 2 3 5 8 13 …<\/p>\n\n\n\n

\u00cen acest articol v\u0103 voi prezenta 4 modalit\u0103\u021bi de a afla al n-lea termen din \u0219irul lui Fibonacci, de la cea mai ineficient\u0103 la cea mai eficient\u0103. \u00cen continuare, vom nota al n-lea termen din \u0219irul lui Fibonacci cu F(n)<\/strong>.<\/p>\n\n\n\n

    \n
  1. Complexitate O(2n<\/sup>)<\/a><\/li>\n\n\n\n
  2. Complexitate O(n) recursiv<\/a><\/li>\n\n\n\n
  3. Complexitate O(n) nerecursiv<\/a><\/li>\n\n\n\n
  4. Complexitate O(log2<\/sub>n)<\/a><\/li>\n<\/ol>\n\n\n\n

    1. Complexitate O(2n<\/sup>)<\/strong><\/p>\n\n\n\n

    \u0218tim c\u0103 F(n) = F(n-1) + F(n-2). S\u0103 facem o func\u021bie recursiv\u0103 care s\u0103 ne calculeze acest rezultat.<\/p>\n\n\n\n

    int fibo(int n)\n{\n   if (n <= 2)\n      return 1;\n   else\n      return fibo(n-1) + fibo(n-2);\n}<\/pre>\n\n\n\n
    Dac\u0103 n este mai mic sau egal dec\u00e2t 2, atunci \u0219tim c\u0103 rezultatul este 1 (pentru c\u0103 F(1) = F(2) = 1).
    Altfel, F(n) se ob\u021bine din F(n-1) + F(n-2).<\/p>\n\n\n\n
    S\u0103 vedem de ce acest algoritm are complexitatea O(2n<\/sup>).<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    Fiecare cercule\u021b al acestui arbore \u00eel vom considera a fi un apel de func\u021bie.
    Primul apel, F(n), este r\u0103d\u0103cina acestui arbore.
    F(n) face dou\u0103 apeluri, F(n-1) \u0219i F(n-2), adic\u0103 cele de pe nivelul al doilea din acest arbore.
    F(n-1) \u0219i F(n-2) fac fiecare c\u00e2te dou\u0103 apeluri de func\u021bie, deci se vor forma 4 \u00een total (nivelul 3).
    Din 4 apeluri, se mai fac alte 8 apeluri (nivelul 4).
    Astfel, num\u0103rul total de apeluri va fi aproximativ 1 + 2 + 4 + 8 + … + 2n-1<\/sup>, care \u00eenseamn\u0103 aproximativ 2n<\/sup> apeluri. Deci, complexitate de timp O(2n<\/sup>), iar complexitate de spa\u021biu O(n).<\/p>\n\n\n\n
    2. Complexitate O(n) recursiv<\/strong><\/p>\n\n\n\n
    Putem s\u0103 \u00eembun\u0103t\u0103\u021bim algoritmul de mai sus. Observ\u0103m c\u0103 multe apeluri se calculeaz\u0103 de foarte multe ori. De aceea, vom memora rezultatul unui apel cu scopul de a nu mai calcula tot apelul degeaba. Aceast\u0103 solu\u021bie se mai nume\u0219te \u0219i recursivitate cu memoizare.<\/p>\n\n\n\n
    int f[100];

    int fibo(int n)
    {
       if (n <= 2)
          return 1;
       else
       {
          if (f[n] != 0)
             return f[n];
          else
          {
             f[n] = fibo(n-1) + fibo(n-2);
             return f[n];
          }
       }
    }<\/pre>\n\n\n\n
    La fel ca la prima solu\u021bie, dac\u0103 n este mai mic sau egal dec\u00e2t 2, return\u0103m 1.
    Altfel, verific\u0103m dac\u0103 nu cumva am calculat deja F(n); dac\u0103 f[n] este diferit de 0, \u00eenseamn\u0103 c\u0103 l-am calculat deja, \u0219i vom returna direct f[n], f\u0103r\u0103 a mai face alte apeluri inutile.
    Altfel (dac\u0103 f[n] este egal cu 0), \u00eenseamn\u0103 c\u0103 nu l-am calculat pe F(n), deci vom face cele dou\u0103 apeluri F(n-1) \u0219i F(n-2), \u0219i vom \u00eensuma rezultatele \u00een f[n], pentru a \u00eel memora pentru alte apeluri.<\/p>\n\n\n\n
    3. Complexitate O(n) nerecursiv<\/strong><\/p>\n\n\n\n
    Aceast\u0103 solu\u021bie presupune folosirea program\u0103rii dinamice. Codul este foarte simplu de \u00een\u021beles, nu are rost s\u0103 \u00eel explic.<\/p>\n\n\n\n
    int f[100];

    int fibo(int n)
    {
       f[1] = f[2] = 1;
       for (int i = 3; i <= n; ++i)
          f[i] = f[i-1] + f[i-2];

       return f[n];
    }<\/pre>\n\n\n\n
    \u00cen general, ne mul\u021bumim cu aceast\u0103 complexitate. Codul este foarte u\u0219or de scris \u0219i simplu de \u00een\u021beles pentru oricine.<\/p>\n\n\n\n
    4. Complexitate O(log2<\/sub>n)<\/strong><\/p>\n\n\n\n
    Pentru a \u00een\u021belege aceast\u0103 solu\u021bie, trebuie s\u0103 \u0219tim ce sunt matricele. Nu matricele din informatic\u0103, ci cele din matematic\u0103.<\/p>\n\n\n\n
    Din ce am \u00een\u021beles eu, matricele sunt ni\u0219te chestii inventate doar pentru a u\u0219ura calculele.
    Exist\u0103 reguli diferite pentru adunarea, sc\u0103derea, \u00eenmul\u021birea \u0219i \u00eemp\u0103r\u021birea matricilor, \u00eens\u0103 pe noi ne va interesa doar \u00eenmul\u021birea matricilor.<\/p>\n\n\n\n
    \u00cenmul\u021birea matricelor 2×2 cu 2×2<\/em><\/span><\/p>\n\n\n
    \"\begin{bmatrix}<\/p>\n\n\n\n
    \u00cenmul\u021birea matricelor 2×2 cu 2×1<\/em><\/span><\/p>\n\n\n
    \"\begin{bmatrix}<\/p>\n\n\n\n
    \u0218tiind regulile de mai sus, putem s\u0103 cre\u0103m urm\u0103toarea ecua\u021bie:<\/p>\n\n\n
    \"\begin{bmatrix}<\/p>\n\n\n\n
    Pentru a demonstra c\u0103 ecua\u021bia de mai sus este adev\u0103rat\u0103, aceasta se traduce \u00een:<\/p>\n\n\n
    \"\begin{bmatrix}<\/p>\n\n\n\n
    S\u0103 form\u0103m \u0219i ecua\u021bia pentru matricea format\u0103 din F(4) cu F(3):<\/p>\n\n\n
    \"\begin{bmatrix}<\/p>\n\n\n\n
    \u00cenlocuind ecua\u021bia (1) \u00een ecua\u021bia (2), ob\u021binem:<\/p>\n\n\n
     \"\begin{bmatrix}<\/p>\n\n\n\n
    La cazul general:<\/p>\n\n\n
     \"\begin{bmatrix}<\/p>\n\n\n\n
    O form\u0103 pu\u021bin mai simplificat\u0103 este:<\/p>\n\n\n
     \"\begin{bmatrix}<\/p>\n\n\n\n
    Singura problem\u0103 mai dificil\u0103 r\u0103mas\u0103 este ridicarea la putere a unei matrice. Pentru a ob\u021bine complexitatea O(log2<\/sub>n), vom folosi exponen\u021bierea rapid\u0103. Dup\u0103, ne mai r\u0103m\u00e2ne s\u0103 \u00eenmul\u021bim rezultatul cu \u00eenc\u0103 o matrice. Acesta este codul:<\/p>\n\n\n\n
    struct mat2x2 {\n   int v00, v01, v10, v11;\n};\n\nstruct mat2x1 {\n   int v00, v10;\n};\n\n\nmat2x2 multipl(mat2x2 a, mat2x2 b)\n{\n   mat2x2 c;\n   c.v00 = a.v00 * b.v00 + a.v01 * b.v10;\n   c.v01 = a.v00 * b.v01 + a.v01 * b.v11;\n   c.v10 = a.v10 * b.v00 + a.v11 * b.v10;\n   c.v11 = a.v10 * b.v01 + a.v11 * b.v11;\n\n   return c;\n}\n\n\nmat2x1 multipl(mat2x2 a, mat2x1 b)\n{\n   mat2x1 c;\n   c.v00 = a.v00 * b.v00 + a.v01 * b.v10;\n   c.v10 = a.v10 * b.v00 + a.v11 * b.v10;\n\n   return c;\n}\n\nmat2x2 pow(mat2x2 a, int exp)\n{\n   \/\/ initalizez ans cu a, si scad exp cu 1\n   mat2x2 ans = a;\n   exp--;\n\n   while (exp != 0)\n   {\n      if (exp % 2 == 1)\n      {\n         ans = multipl(ans, a);\n         exp -= 1;\n      }\n      else\n      {\n         a = multipl(a, a);\n         exp \/= 2;\n      }\n   }\n\n   return ans;\n}\n\nint fibo(int n)\n{\n   if (n <= 2)\n      return 1; \/\/ nu ridicam matricea la puterea 0 sau -1\n\n   mat2x2 def1 = {1, 1, 1, 0};\n   mat2x1 def2 = {1, 1};\n   mat2x1 c = multipl(pow(def1, n-2), def2);\n\n   return c.v00; \/\/ c.v00 e F(n), c.v10 e F(n-1)\n}<\/pre>\n\n\n\n
    Av\u00e2nd \u00een vedere c\u0103 termenul al 46-lea este cel mai mare termen care poate fi calculat \u00een tipul int (la toate cele 4 solu\u021bii prezentate), aceste solu\u021bii pot fi extinse pe numere mai mari folosind aritmetica modular\u0103.<\/p>\n\n\n\n
    \u00cei mul\u021bumesc indianului de pe YouTube<\/a> \u0219i pbInfo-ului<\/a> pentru c\u0103 m-au \u00eenv\u0103\u021bat lucrurile pe care vi le-am prezentat.<\/p>\n\n\n\n
    V\u0103 propun urm\u0103toarele probleme de rezolvat: Fibonacci2<\/a>, NumarDeSubmultimi1<\/a>, kfib<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Un termen din \u0219irul lui Fibonacci se formeaz\u0103 din suma ultimilor doi dinaintea lui, iar primii doi termeni \u00eei consider\u0103m … <\/p>\n","protected":false},"author":4,"featured_media":446,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[48,47,51,50],"class_list":["post-410","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-fibonacci","tag-exponentiere-rapida","tag-fibonacci","tag-programare-dinamica","tag-recursivitate"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=410"}],"version-history":[{"count":37,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/410\/revisions"}],"predecessor-version":[{"id":529,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/410\/revisions\/529"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/446"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}