Фибоначчийн дарааллыг 2 хувьсагч ашиглан хэвлэ  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Дели Мэдээллийн багц Фуркайт явган аялал MAQ o9 шийдэл PayU
Динамик програмчлал Fibonacci дараалал

Асуудлын мэдэгдэл  

"Фибоначчийн дарааллыг 2 хувьсагч ашиглан хэвлэх" гэсэн асуудалд та Фибоначчийн дарааллыг хэвлэх шаардлагатай гэсэн боловч зөвхөн 2 хувьсагч ашиглах хязгаарлалт бий.

Жишээ нь  

Фибоначчийн дарааллыг 2 хувьсагч ашиглан хэвлэ

n = 5
0 1 1 2 3 5

Тайлбар

Гаралтын дараалал нь Фибоначчийн цувралын эхний таван элементтэй байна.

арга барил  

Бидэнд нэг элементийг оролт болгон өгдөг бөгөөд энэ нь фибоначчийн дарааллаар үйлдвэрлэх шаардлагатай элементүүдийн тоог хэлж өгдөг. Тиймээс Фибоначчийн дарааллыг хэвлэх гэнэн хандлага ийм байна давтлага. Дараа нь бид фибоначчийн тоо тус бүрийг тооцоолоход бидний рекурсив функцийг дууддаг давталтыг ашиглаж болно. Гэхдээ энэ арга нь экспоненциал цаг хугацаа шаарддаг тул бидэнд илүү үр дүнтэй зүйл хэрэгтэй болно.

Бид бодож болно динамик програмчлал/ асуудлын дурсамж. Энэ арга нь цаг хугацааны нарийн төвөгтэй байдлыг багасгах нь дамжиггүй. Экспоненциаль цаг хугацааны нарийн төвөгтэй байдал нь шугаман хугацааны нарийн төвөгтэй болж буурах болно. Гэхдээ энэ хандлага нь бидэнд шугаман орон зайн нарийн төвөгтэй байдлыг шаарддаг хэвээр байна. Бид энэ орон зайн нарийн төвөгтэй байдлыг цаашид багасгах хэрэгтэй. Бидний хийж чадах зүйл бол оновчтой болгохыг хичээх явдал юм динамик програмчлал арга барил.

Хэрэв бид рекурсив томъёог харвал F (n) = F (n-1) + F (n-2) болно. Бид зөвхөн Фибоначчийн сүүлийн хоёр тооноос л хамааралтай байдаг. Одоогийн тоог олохын тулд бид зөвхөн сүүлийн хоёр Фибоначчийн тоог хадгалах боломжтой бөгөөд ингэснээр алгоритмийг O (1) орон зайд төвөгтэй болгоно.

код  

Фибоначчийн дарааллыг 2 хувьсагч ашиглан хэвлэх C ++ код

#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 хувьсагч ашиглан Фибоначчийн дарааллыг хэвлэх Java код

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),  Бид зөвхөн хоёр хувьсагч хэрэглэсэн тул сансрын байнгын төвөгтэй байдалд асуудлыг шийдсэн.