Штампајте Фибоначијеве бројеве обрнутим редоследом


Ниво тешкоће Лако
Често питани у Аццентуре МАК о9 решења УХГ Оптум
Динамичко програмирање Секвенца

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

Дати број н, исписати фибоначијеве бројеве обрнутим редоследом.

Пример

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. Почињемо да покрећемо петљу од и = 2, све док вредност и није мања од н, док вредност и повећавамо један по један.
    1. Наставите да чувате додавање последњег елемента индекса и последњег до последњег елемента индекса.
  5. Сада одштампајте овај низ обрнутим редоследом.

Приступ

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

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

код

Ц ++ код за испис фибоначијевих бројева обрнутим редоследом

#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

Јава код за испис фибоначијевих бројева обрнутим редоследом

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

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

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

О (Н), ово време је потребно за израчунавање фибоначијевих бројева. Зато што само покрећемо једну петљу да бисмо пронашли фибоначијев низ. Сложеност времена је линеарна.

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

О (Н), јер смо користили низ за чување вредности фибоначијевих бројева, сложеност простора је линеарна.