Տպիր Ֆիբոնաչիի համարները հակառակ հերթականությամբ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են 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 = 2-ից, մինչև i- ի արժեքը n- ից փոքր է `i- ի արժեքը մեկ առ մեկ ավելացնելով:
    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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N), այս անգամ պահանջվում է `համարի համարները համարը հաշվարկելու համար: Քանի որ մենք պարզապես վարում ենք մեկ օղակ ՝ գտնելու համար հաջորդականությունը: Timeամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (N), քանի որ մենք օգտագործել ենք զանգված ՝ ֆիդայական թվերի արժեքները պահելու համար, տարածության բարդությունը գծային է: