Одштампајте Фибоначијеву секвенцу помоћу 2 променљиве


Ниво тешкоће Лако
Често питани у амазонка Делхивери Фацтсет Фоуркитес Пешачење МАК о9 решења ПаиУ
Динамичко програмирање Фибонацци Секвенца

Изјава о проблему

Проблем „Штампање Фибоначијеве секвенце помоћу 2 променљиве“ наводи да треба да одштампате Фибоначијеву секвенцу, али постоји ограничење употребе само 2 променљиве.

Пример

Одштампајте Фибоначијеву секвенцу помоћу 2 променљиве

n = 5
0 1 1 2 3 5

Објашњење

Излазна секвенца има првих пет елемената Фибоначијеве серије.

Приступ

Добијамо један елемент као улаз, који нам говори о броју елемената које треба произвести из фибоначијеве секвенце. Дакле, наиван приступ штампању Фибоначијеве секвенце је рекурзија. Тада можемо користити петљу која позива нашу рекурзивну функцију за израчунавање сваког фибоначијевог броја. Али овај приступ захтева експоненцијално време и стога нам треба нешто ефикасније.

Можемо смислити динамичко програмирање/ памћење проблема. Приступ ће сигурно смањити временску сложеност. Експоненцијална временска сложеност биће сведена на линеарну временску сложеност. Али овај приступ и даље захтева линеарну сложеност простора. Морамо додатно смањити ову сложеност свемира. Оно што можемо је да покушамо да оптимизујемо динамичко програмирање приступ.

Ако видимо рекурзивну формулу, Ф (н) = Ф (н-1) + Ф (н-2). Зависни смо само од последња два Фибоначијева броја. Тако можемо сачувати само последња два Фибоначијева броја да бисмо пронашли тренутни број и то чини алгоритам да ради у сложености простора О (1).

код

Ц ++ код за штампање Фибонаццијеве секвенце помоћу 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

Јава код за штампање Фибоначијеве секвенце помоћу 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

Анализа сложености

Сложеност времена

НА), јер смо путовали само до броја елемената који су нам потребни за штампу. Прво смо размишљали о решавању проблема помоћу рекурзије, али то је било експоненцијално у времену. Тада смо смањили временску сложеност када смо користили динамичко програмирање. Због које смо успели да решимо проблем у линеарном времену.

Сложеност простора

О (1),  проблем смо решили у константној сложености простора јер смо користили само две променљиве.