न्यूमॅन-कॉनवे सीक्वेन्सच्या अटी प्रिंट करा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन किल्ला फॅक्टसेट कट्टरता जेपी मॉर्गन
डायनॅमिक प्रोग्रामिंग गणित मालिका

समस्या विधान

“न्यूमॅन-कॉनवे सीक्वेन्सच्या प्रिंट एन अटी” या समस्येमध्ये असे म्हटले आहे की आपल्याला एक पूर्णांक “एन” देण्यात आला आहे. न्यूमॅन-कॉनवे सीक्वेन्सच्या प्रथम एन अटी शोधा आणि त्या नंतर मुद्रित करा.

उदाहरण

n = 6
1 1 2 2 3 4

स्पष्टीकरण
मुद्रित केल्या गेलेल्या सर्व अटी न्यूमॅन-कॉनवे सीक्वेन्सचे अनुसरण करतात आणि अशाच प्रकारे आपण तसे करणे आवश्यक आहे. आम्ही प्रथम एन अटी शोधण्याचा प्रयत्न करू.

न्यूमॅन-कॉनवे सीक्वेन्सच्या एन अटी मुद्रित करण्यासाठी दृष्टिकोन

न्यूमॅन-कॉनवे सीक्वेन्स हा एक क्रम आहे ज्याचा प्रत्येक शब्द पुढील पुनरावृत्ती संबंधास समाधानी करतो:

पी (1) = पी (2) = 1

न्यूमॅन-कॉनवे सीक्वेन्सच्या अटी प्रिंट करा

आता आपल्याला अनुक्रमातील प्रथम n अटी शोधणे आवश्यक आहे. आम्ही आधीपासूनच अशाच समस्येचे निराकरण केले आहे जिथे आपल्याला nth घटक शोधायचा होता न्यूमॅन-कॉनवे सीक्वेन्कई. त्यावेळी आमच्याकडे दोन पर्याय होते. एकतर आम्ही रिकर्सन वापरून समस्या सोडवू शकलो किंवा आम्ही वापरु शकलो असतो डायनॅमिक प्रोग्रामिंग. आम्ही शिकलो की पुनरावृत्ती वापरणे ही वेळ मर्यादेपेक्षा जास्त असेल. आवर्तनाची वेळ गुंतागुंतीची आहे. पुनरावृत्ती समाधानासाठी आम्ही पुनरावृत्ती सूत्र वापरू आणि वेगवेगळ्या घटकांच्या मूल्यांची गणना करत राहू. आपल्याला पी (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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही फक्त डायनॅमिक प्रोग्रामिंग अप्रोचमध्ये पळवाट चालविली आहे. जसे की आपल्याकडे नेहमीच घटकांचे पुनर्गणना होते जे सध्याच्या घटकाच्या मोजणीसाठी आवश्यक होते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), सर्व एन घटक साठवण्यासाठी रेषीय जागा आवश्यक असते आणि अशा प्रकारे स्पेसची गुंतागुंत देखील रेषात्मक असते.