गोलॉम्ब क्रम


अडचण पातळी सोपे
वारंवार विचारले कॅडन्स इंडिया खरंच टाइम्स इंटरनेट यात्रा
डायनॅमिक प्रोग्रामिंग अनुक्रम

समस्या विधान

“गोलॉम सिक्वेन्स” ही समस्या सांगते की आपल्याला एक इनपुट देण्यात आले आहे पूर्णांक n आणि आपल्याला XNUMX व्या घटकापर्यंत गोलब अनुक्रमातील सर्व घटक शोधण्याची आवश्यकता आहे.

उदाहरण

n = 8
1 2 2 3 3 4 4 4

स्पष्टीकरण
गोलॉम्ब क्रमातील प्रथम 8 संज्ञा सापडल्या आणि मुद्रित केल्या. आउटपुट गोलोल सिक्वेन्सचे पहिले 8 घटक दर्शवते म्हणून आउटपुट योग्य आहे.

दृष्टीकोन

गणितामध्ये दिलेल्या क्रमांना सिल्व्हरमॅन सीक्वेन्स असेही म्हणतात. या क्रमाचे नाव सोलोमन डब्ल्यू. गोलॉम्ब यांच्या नावावर आहे. हा एक नॉन-घटणारा पूर्णांक आहे जिथे अ (एन) क्रमांकामध्ये एन किती वेळा होतो. गोलब सिक्वेन्सचा पहिला घटक 1 आहे. उदाहरणार्थ, ए 1 = 1 म्हणतो की अनुक्रमात 1 फक्त एकदाच येते, म्हणून ए 2 देखील 1 असू शकत नाही, परंतु ते असू शकते आणि म्हणूनच 2 असणे आवश्यक आहे.

अनुक्रमातील पहिल्या काही अटी 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, XNUMX.

आम्हाला गोलॉम क्रमातील घटक तयार करण्यासाठी पुनरावृत्ती संबंध माहित आहेत. रिकर्सिव फॉर्म्युला आहे

गोलॉम्ब क्रम
रिकर्सिव फॉर्म्युला वापरुन आम्ही समस्या सोडवू. पुनरावृत्तीचा वापर करून समस्या सोडविणे हा एक मार्ग आहे. परंतु यामुळे आपल्यासाठी घाईघाईची वेळ गुंतागुंत होईल कारण आपण पुन्हा पुन्हा त्याच मूल्यांची गणना करत आहोत. कारण पुनरावृत्तीच्या नात्यातून आपण बघू शकतो की अनुक्रमातील नववा घटक पूर्वीच्या संगणकीय अटींवर अवलंबून आहे. म्हणून आम्ही डायनॅमिक प्रोग्रामिंगचा वापर केल्यापासून समस्येचे निराकरण करण्यासाठी वापरू, आम्हाला इतर मूल्यांची गणना करण्याची गरज नाही.

कोड

गोलॉम सिक्वन्ससाठी सी ++ कोड

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

int main(){
  // number of elements of Golomb sequence which are required
  int n;cin>>n;

  cout<<1<<" ";
  int dp[n+1];
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i] = 1 + dp[i-dp[dp[i-1]]];
    cout<<dp[i]<<" ";
  }
}
10
1 2 2 3 3 4 4 4 5 5

गोलॉम सिक्वन्ससाठी जावा कोड

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements of Golomb sequence which are required
    int n = sc.nextInt();

    System.out.print("1 ");
    int dp[] = new int[n+1];
    dp[1] = 1;
    for(int i=2;i<=n;i++){
      dp[i] = 1 + dp[i-dp[dp[i-1]]];
      System.out.print(dp[i]+" ");
    }
  }
}
10
1 2 2 3 3 4 4 4 5 5

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

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

ओ (एन), कारण नववा घटक एका पूर्वीच्या गणना केलेल्या घटकावर अवलंबून असतो जो प्रत्येक घटकासाठी हे ऑपरेशन ओ (1) वेळ जटिल बनवितो. तेथे एन घटक आहेत, वेळ गुंतागुंत रेषात्मक आहे.

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

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