Фибоначчи сандарын тескери тартипте басып чыгарыңыз


Кыйынчылык деңгээли жеңил
Көп суралган 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 Фибоначчи сандарынын натыйжасынан канчалык көз каранды экендигин билдирет.

Algorithm

  1. Басып чыгарылуучу элементтердин санын киргизиңиз.
  2. Берилген маалыматтын көлөмү катары массив жарыялаңыз.
  3. 0 жана 1 массив индексин 0 жана 1 менен баштаңыз.
  4. Биз i = 2 ден циклди иштетип баштайбыз, i маанисин бирден көбөйтүп жатканда i мааниси nден кем эмес.
    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), анткени биз фибоначчи сандарынын маанисин сактоо үчүн массивди колдондук, мейкиндиктин татаалдыгы сызыктуу.