Фибоначчийн тоог урвуу дарааллаар хэвлэ


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accenture MAQ o9 шийдэл UHG Optum
Динамик програмчлал дараалал

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

N тоо өгөгдсөн бол фибоначчийн тоог урвуу дарааллаар хэвлэ.

Жишээ нь

n = 5
3 2 1 1 0

Тайлбар: Фибоначчийн тоо нь захиалгын дагуу 0, 1, 1, 2, 3 байна. Гэхдээ бид урвуу дарааллаар хэвлэх хэрэгтэй байсан болохоор.

n = 7
8 5 3 2 1 1 0

Фибоначчийн тоог урвуу дарааллаар хэвлэ

Зураг нь Фибоначчийн тоо нь сүүлийн 2 фибоначчийн тооны үр дүнгээс хэрхэн хамааралтай болохыг илэрхийлнэ.

Алгоритм

  1. Хэвлэх элементийн тоог оруулна уу.
  2. Массивын хэмжээг тухайн оролтын хэмжээтэй адил зарлана уу.
  3. 0 ба 1 массивын индексийг 0 ба 1-ээр эхлүүлнэ.
  4. I-ийн утгыг нэг нэгээр нь өсгөхдөө i-ийн утга n-ээс бага болтол бид i = 2-оос давталт хийж эхэлнэ.
    1. Сүүлийн индекс элементийн сүүлчийн индекс элементийн нэмэлтийг хадгалж байгаарай.
  5. Одоо энэ массивыг урвуу дарааллаар хэвлэ.

арга барил

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

Альтернатив арга нь динамик програмчлал, асуудлыг шийдвэрлэхэд илүү олон удаа шаардлагатай өгөгдлийг хадгалдаг. Түүнчлэн фибоначчийн тоог олох талаар ярилцсан динамик програмчлал өмнөх дэх дараах.

код

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

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

int main()
{
    int n;cin>>n;
    int fib[n];
    if(n>=1)
    fib[0] = 0;
    if(n>=2)
    fib[1] = 1;
    for(int i=2;i<n;i++)
        fib[i] = fib[i-1] + fib[i-2];
    for(int i=n-1;i>=0;i--)
        cout<<fib[i]<<" ";
}
4
2 1 1 0

Фибоначчийн дугаарыг урвуу дарааллаар хэвлэх Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), энэ удаа фибоначчийн тоог тооцоолох шаардлагатай. Учир нь бид фибоначчийн дарааллыг олохын тулд ганц л давталт хийдэг. Цаг хугацааны нарийн төвөгтэй байдал нь шугаман байна.

Сансрын нарийн төвөгтэй байдал

O (N), бид фибоначчийн тооны утгыг хадгалах массивыг ашигласан тул орон зайн нарийн төвөгтэй байдал нь шугаман байна.