ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ n നിബന്ധനകൾ അച്ചടിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ കോട്ട ഫാക്റ്റ്സെറ്റ് ഫനാറ്റിക്സ് ജെപി മോർഗൻ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം സീരീസ്

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

“ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ പ്രിന്റ് എൻ നിബന്ധനകൾ” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു പൂർണ്ണസംഖ്യ “എൻ” നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ ആദ്യ n നിബന്ധനകൾ കണ്ടെത്തി അവ പ്രിന്റുചെയ്യുക.

ഉദാഹരണം

n = 6
1 1 2 2 3 4

വിശദീകരണം
അച്ചടിച്ച എല്ലാ നിബന്ധനകളും ന്യൂമാൻ-കോൺവേ സീക്വൻസിനെ പിന്തുടരുന്നു, അതിനാൽ ഞങ്ങൾ അത് ചെയ്യേണ്ടതുണ്ട്. ആദ്യത്തെ n പദങ്ങൾ കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിക്കും.

ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ n നിബന്ധനകൾ അച്ചടിക്കാനുള്ള സമീപനം

ഓരോ പദവും ഇനിപ്പറയുന്ന ആവർത്തന ബന്ധത്തെ തൃപ്തിപ്പെടുത്തുന്ന ഒരു ശ്രേണിയാണ് ന്യൂമാൻ-കോൺവേ സീക്വൻസ്:

പി (1) = പി (2) = 1

ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ n നിബന്ധനകൾ അച്ചടിക്കുക

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

ഡൈനാമിക് പ്രോഗ്രാമിംഗ് സമീപനം

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

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

കോഡ്

ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ നിബന്ധനകൾ അച്ചടിക്കാനുള്ള സി ++ കോഡ്

#include <bits/stdc++.h>
using namespace std;
int main(){
  // elements to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  for(int i=1;i<=n;i++)
  	cout<<dp[i]<<" ";
}
6
1 1 2 2 3 4

ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ നിബന്ധനകൾ പ്രിന്റുചെയ്യാനുള്ള ജാവ കോഡ്

import java.util.*;
class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    // elemnts to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  	for(int i=1;i<=n;i++)
    	System.out.print(dp[i]+" ");
  }
}
6
1 1 2 2 3 4

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

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

O (N), കാരണം ഞങ്ങൾ ഒരു ചലനാത്മക പ്രോഗ്രാമിംഗ് സമീപനത്തിൽ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിച്ചു. നിലവിലെ മൂലകത്തിന്റെ കണക്കുകൂട്ടലിന് ആവശ്യമായ എല്ലാ ഘടകങ്ങളും വീണ്ടും കണക്കാക്കിയതിനാൽ.

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

O (N), എല്ലാ n ഘടകങ്ങളും സംഭരിക്കുന്നതിന് ലീനിയർ സ്പേസ് ആവശ്യമാണ്, അതിനാൽ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.