Надрукаваць паслядоўнасць Фібаначы, выкарыстоўваючы 2 зменныя


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Дэліверы Факты Фуркайты Паход MAQ o9 рашэнні PayU
Дынамічнае праграмаванне Фібаначы Паслядоўнасць

Пастаноўка праблемы

Праблема «Друк паслядоўнасці Фібаначы з выкарыстаннем 2 зменных» абвяшчае, што трэба раздрукоўваць паслядоўнасць Фібаначы, але існуе абмежаванне выкарыстання толькі 2 зменных.

Прыклад

Надрукаваць паслядоўнасць Фібаначы, выкарыстоўваючы 2 зменныя

n = 5
0 1 1 2 3 5

Тлумачэнне

Вывадная паслядоўнасць мае першыя пяць элементаў серыі Фібаначы.

Падыход

У якасці ўваходных дадзеных мы атрымліваем адзін элемент, які паведамляе нам колькасць элементаў, якія неабходна стварыць з паслядоўнасці Фібаначы. Такім чынам, наіўны падыход да друку паслядоўнасці Фібаначы ёсць рэкурсія. Тады мы можам выкарыстоўваць цыкл, які выклікае нашу рэкурсіўную функцыю для разліку кожнага ліку Фібаначы. Але гэты падыход патрабуе экспанентнага часу, і, такім чынам, нам трэба нешта больш эфектыўнае.

Мы можам думаць дынамічнае праграмаванне/ памятка для праблемы. Падыход напэўна паменшыць складанасць часу. Экспаненцыяльная складанасць часу будзе зведзена да лінейнай складанасці часу. Але гэты падыход усё яшчэ патрабуе ад нас лінейнай складанасці прасторы. Нам трэба яшчэ больш скараціць гэтую касмічную складанасць. Што мы можам зрабіць, гэта паспрабаваць аптымізаваць дынамічнае праграмаванне падыходу.

Калі мы бачым рэкурсіўную формулу, F (n) = F (n-1) + F (n-2). Мы залежым толькі ад апошніх двух лікаў Фібаначы. Такім чынам, мы можам захоўваць толькі два апошнія лікі Фібаначы, каб знайсці бягучы лік, і гэта прымушае алгарытм працаваць у прасторы O (1).

код

Код C ++ для друку паслядоўнасці Фібаначы з выкарыстаннем 2 зменных

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

Код Java для друку паслядоўнасці Фібаначы з выкарыстаннем 2 зменных

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int last = 1, lastToLast = 0;
      if(n>=0)
          System.out.print(lastToLast+" ");
      if(n>=1)
          System.out.print(last+" ");
      for(int i=2;i<=n;i++){
          int cur = last + lastToLast;
          System.out.print(cur+" ");
          lastToLast = last;
          last = cur;
      }
  	}
}
5
0 1 1 2 3 5

Аналіз складанасці

Складанасць часу

O (N), таму што мы прайшлі шлях толькі да колькасці элементаў, якія нам патрэбныя для друку. Па-першае, мы думалі вырашыць праблему з выкарыстаннем рэкурсіі, але яна была экспанентнай па часе. Потым мы скарачалі час, калі выкарыстоўвалі дынамічнае праграмаванне. З-за чаго нам удалося вырашыць задачу за лінейны час.

Касмічная складанасць

O (1),  мы вырашылі задачу ў пастаяннай складанасці прасторы, таму што выкарысталі толькі дзве зменныя.