ന്യൂമാൻ-കോൺവേ സീക്വൻസ്


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഹണിവെൽ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം അനുക്രമം

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

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

ഉദാഹരണം

n = 6
4
n = 10
6

വിശദീകരണം

Man ട്ട്‌പുട്ട് ഘടകങ്ങൾ ന്യൂമാൻ-കോൺവേ സീക്വൻസിന്റെ ആറാമത്തെയും പത്താമത്തെയും ഘടകത്തെ പ്രതിനിധീകരിക്കുന്നതിനാൽ. Output ട്ട്‌പുട്ട് തികച്ചും ശരിയാണ്.

ന്യൂമാൻ-കോൺവേ സീക്വൻസ് കണ്ടെത്താനുള്ള സമീപനം

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

ന്യൂമാൻ-കോൺവേ സീക്വൻസ്

 

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

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

കോഡ്

Nth ന്യൂമാൻ-കോൺവേ സീക്വൻസ് ഘടകം കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#include <bits/stdc++.h>
using namespace std;

int main(){
  // element 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]];
  cout<<dp[n];
}
6
4

Nth ന്യൂമാൻ-കോൺവേ സീക്വൻസ് ഘടകം കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt 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]];
    System.out.print(dp[n]);
  }
}
6
4

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

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

O (N), കാരണം സീക്വൻസിന്റെ ഒൻപതാം ഘടകം കണ്ടെത്താൻ ഞങ്ങൾ ഒരൊറ്റ ലൂപ്പ് ഓടിച്ചു. അങ്ങനെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

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

O (N), ഒൻപതാമത്തെ മൂലകത്തിന്റെ കണക്കുകൂട്ടലിന് ആവശ്യമായ ഇന്റർമീഡിയറ്റ് ഫലങ്ങൾ സംഭരിക്കാൻ ഞങ്ങൾ ഒരു ഡിപി അറേ ഉപയോഗിച്ചതിനാൽ. സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.

അവലംബം