Տպեք Ֆիբոնաչիի հաջորդականությունը ՝ օգտագործելով 2 փոփոխական


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Առաքում Փաստեր Ֆուրկիտներ Զբոսանք MAQ o9 լուծումներ PayU
Դինամիկ ծրագրավորում Fibonacci Հերթականություն

Խնդիրի հայտարարություն

«Տպիր Ֆիբոնաչիի հաջորդականությունը ՝ օգտագործելով 2 փոփոխական» խնդիրը ասում է, որ անհրաժեշտ է տպել Ֆիբոնաչիի հաջորդականությունը, բայց կա միայն 2 փոփոխականի օգտագործման սահմանափակում:

Օրինակ

Տպեք Ֆիբոնաչիի հաջորդականությունը ՝ օգտագործելով 2 փոփոխական

n = 5
0 1 1 2 3 5

բացատրություն

Ելքի հաջորդականությունն ունի Ֆիբոնաչիի շարքի առաջին հինգ տարրերը:

Մոտեցում

Որպես ներդրում մեզ տրամադրվում է մեկ տարր, որը մեզ ասում է այն տարրերի քանակը, որոնք անհրաժեշտ է արտադրել ըստ մակարդակի հաջորդականության: Այսպիսով, Ֆիբոնաչիի հաջորդականությունը տպելու միամիտ մոտեցումն է հետադարձություն, Դրանից հետո մենք կարող ենք օգտագործել մի օղակ, որը զանգահարում է մեր ռեկուրսիվ ֆունկցիան `յուրաքանչյուր մակարդակային համարի հաշվարկման համար: Բայց այս մոտեցումը պահանջում է էքսպոնենտալ ժամանակ և, այդպիսով, մեզ ավելի արդյունավետ բան է պետք:

Կարող ենք մտածել դինամիկ ծրագրավորում/ հիշողություն խնդրի համար: Մոտեցումն, անկասկած, կնվազեցնի ժամանակի բարդությունը: Expուցադրման ժամանակի բարդությունը կնվազեցվի գծային ժամանակի բարդության: Բայց այս մոտեցումը մեզանից դեռ պահանջում է գծային տիեզերական բարդություն: Մենք պետք է հետագայում նվազեցնենք այս տիեզերական բարդությունը: Այն, ինչ մենք կարող ենք անել, փորձել օպտիմալացնել այն դինամիկ ծրագրավորում մոտեցում.

Եթե ​​մենք տեսնում ենք ռեկուրսիվ բանաձեւը, F (n) = F (n-1) + F (n-2): Մենք կախված ենք միայն Ֆիբոնաչիի վերջին երկու թվերից: Այսպիսով, մենք կարող ենք պահպանել միայն Ֆիբոնաչիի վերջին երկու թվերը `ներկայիս թիվը գտնելու համար, և դա ստիպում է, որ ալգորիթմը գործի O (1) տարածության բարդության մեջ:

Կոդ

C ++ ծածկագիր ՝ Ֆիբոնաչիի հաջորդականությունը տպելու համար ՝ օգտագործելով 2 փոփոխական

#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

Java փոփոխական կոդ ՝ Fibonacci հաջորդականությունը տպելու համար ՝ օգտագործելով 2 փոփոխական

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

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

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

ՎՐԱ), քանի որ մենք անցել ենք միայն մինչև այն տարրերի քանակը, որոնք մենք պահանջում ենք տպել: Նախ, մենք մտածեցինք խնդիրը լուծել ռեկուրսիայի միջոցով, բայց դա ժամանակի ընթացքում ցուցիչ էր: Հետո մենք օգտագործումը նվազեցրեցինք մեր ժամանակի բարդությունը դինամիկ ծրագրավորում, Որի պատճառով մենք կարողացանք խնդիրը լուծել գծային ժամանակում:

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

O (1),  մենք խնդիրը լուծել ենք տարածության անընդհատ բարդության պայմաններում, քանի որ օգտագործել ենք ընդամենը երկու փոփոխական: