2 വേരിയബിളുകൾ ഉപയോഗിച്ച് ഫിബൊനാച്ചി സീക്വൻസ് പ്രിന്റുചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ദില്ലി ഫാക്റ്റ്സെറ്റ് ഫോർകൈറ്റുകൾ ഉയർത്തൽ MAQ o9 പരിഹാരങ്ങൾ പേ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഫിബൊനാച്ചി അനുക്രമം

പ്രശ്നം പ്രസ്താവന

“2 വേരിയബിളുകൾ ഉപയോഗിച്ച് ഫിബൊനാച്ചി സീക്വൻസ് പ്രിന്റുചെയ്യുക” എന്ന പ്രശ്നം നിങ്ങൾ ഫിബൊനാച്ചി സീക്വൻസ് പ്രിന്റുചെയ്യേണ്ടതുണ്ടെന്നും എന്നാൽ 2 വേരിയബിളുകൾ മാത്രം ഉപയോഗിക്കുന്നതിന് പരിമിതി ഉണ്ടെന്നും പറയുന്നു.

ഉദാഹരണം

2 വേരിയബിളുകൾ ഉപയോഗിച്ച് ഫിബൊനാച്ചി സീക്വൻസ് പ്രിന്റുചെയ്യുക

n = 5
0 1 1 2 3 5

വിശദീകരണം

B ട്ട്‌പുട്ട് സീക്വൻസിന് ഫിബൊനാച്ചി സീരീസിന്റെ ആദ്യ അഞ്ച് ഘടകങ്ങളുണ്ട്.

സമീപനം

ഇൻപുട്ടായി ഒരൊറ്റ ഘടകം ഞങ്ങൾക്ക് നൽകിയിട്ടുണ്ട്, ഇത് ഫൈബൊനാച്ചി ശ്രേണിയിൽ നിന്ന് ഉത്പാദിപ്പിക്കേണ്ട ഘടകങ്ങളുടെ എണ്ണം പറയുന്നു. അതിനാൽ ഫിബൊനാച്ചി സീക്വൻസ് അച്ചടിക്കുന്നതിനുള്ള നിഷ്കളങ്കമായ സമീപനമാണ് ആവർത്തനം. ഓരോ ഫിബൊനാച്ചി നമ്പറിന്റെയും കണക്കുകൂട്ടലിനായി ഞങ്ങളുടെ ആവർത്തന പ്രവർത്തനത്തെ വിളിക്കുന്ന ഒരു ലൂപ്പ് ഉപയോഗിക്കാം. എന്നാൽ ഈ സമീപനത്തിന് എക്‌സ്‌പോണൻഷ്യൽ സമയം ആവശ്യമാണ്, അതിനാൽ ഞങ്ങൾക്ക് കൂടുതൽ കാര്യക്ഷമമായ എന്തെങ്കിലും ആവശ്യമാണ്.

നമുക്ക് ചിന്തിക്കാം ഡൈനാമിക് പ്രോഗ്രാമിംഗ്/ പ്രശ്നത്തിനുള്ള ഓർമ്മപ്പെടുത്തൽ. സമീപനം തീർച്ചയായും സമയ സങ്കീർണ്ണത കുറയ്ക്കും. എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണത രേഖീയ സമയ സങ്കീർണ്ണതയിലേക്ക് ചുരുക്കും. എന്നാൽ ഈ സമീപനത്തിന് ഇപ്പോഴും ഞങ്ങൾക്ക് ലീനിയർ സ്പേസ് സങ്കീർണ്ണത ആവശ്യമാണ്. ഈ സ്ഥല സങ്കീർണ്ണത ഞങ്ങൾ ഇനിയും കുറയ്ക്കേണ്ടതുണ്ട്. ഒപ്റ്റിമൈസ് ചെയ്യാൻ ശ്രമിക്കുക എന്നതാണ് ഞങ്ങൾക്ക് ചെയ്യാൻ കഴിയുന്നത് ഡൈനാമിക് പ്രോഗ്രാമിംഗ് സമീപനം.

ആവർത്തന സൂത്രവാക്യം കണ്ടാൽ, F (n) = F (n-1) + F (n-2). ഞങ്ങൾ അവസാന രണ്ട് ഫിബൊനാച്ചി നമ്പറുകളെ മാത്രം ആശ്രയിച്ചിരിക്കുന്നു. അതിനാൽ, നിലവിലെ നമ്പർ കണ്ടെത്താൻ അവസാന രണ്ട് ഫിബൊനാച്ചി നമ്പറുകൾ മാത്രമേ സംഭരിക്കാൻ കഴിയൂ, ഇത് O (1) സ്പേസ് സങ്കീർണ്ണതയിൽ അൽഗോരിതം പ്രവർത്തിപ്പിക്കുന്നു.

കോഡ്

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

ജാവ കോഡ് 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ അച്ചടിക്കാൻ ആവശ്യമായ ഘടകങ്ങളുടെ എണ്ണം വരെ മാത്രമേ സഞ്ചരിച്ചിട്ടുള്ളൂ. ആദ്യം, ആവർത്തനം ഉപയോഗിച്ച് പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾ ആലോചിച്ചുവെങ്കിലും അത് കാലക്രമേണ എക്‌സ്‌പോണൻഷ്യൽ ആയിരുന്നു. ഞങ്ങൾ ഉപയോഗിക്കുമ്പോൾ സമയ സങ്കീർണ്ണത കുറച്ചു ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. ഇക്കാരണത്താൽ ലീനിയർ സമയത്ത് പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾക്ക് കഴിഞ്ഞു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1),  ഞങ്ങൾ രണ്ട് വേരിയബിളുകൾ മാത്രം ഉപയോഗിച്ചതിനാൽ സ്ഥിരമായ സ്ഥല സങ്കീർണ്ണതയിൽ ഞങ്ങൾ പ്രശ്നം പരിഹരിച്ചു.