గోలోంబ్ క్రమం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది కాడెన్స్ ఇండియా నిజానికి టైమ్స్ ఇంటర్నెట్ యాత్ర
డైనమిక్ ప్రోగ్రామింగ్ సీక్వెన్స్

సమస్యల నివేదిక

“గోలోంబ్ సీక్వెన్స్” సమస్య మీకు ఇన్‌పుట్ ఇచ్చిందని పేర్కొంది పూర్ణ సంఖ్య n మరియు మీరు n వ మూలకం వరకు గోలోంబ్ సీక్వెన్స్ యొక్క అన్ని అంశాలను కనుగొనాలి.

ఉదాహరణ

n = 8
1 2 2 3 3 4 4 4

వివరణ
గోలోంబ్ సీక్వెన్స్ యొక్క మొదటి 8 నిబంధనలు కనుగొనబడ్డాయి మరియు ముద్రించబడ్డాయి. అవుట్పుట్ గోలోంబ్ సీక్వెన్స్ యొక్క మొదటి 8 అంశాలను సూచిస్తుంది కాబట్టి, అవుట్పుట్ సరైనది.

అప్రోచ్

గణితంలో, ఇచ్చిన క్రమాన్ని సిల్వర్‌మన్స్ సీక్వెన్స్ అని కూడా అంటారు. ఈ శ్రేణికి సోలమన్ డబ్ల్యూ. గోలోంబ్ పేరు పెట్టారు. ఇది తగ్గని పూర్ణాంక శ్రేణి, ఇక్కడ a (n) అనేది క్రమం లో n సంభవించే సంఖ్య. గోలోంబ్ సీక్వెన్స్ యొక్క మొదటి మూలకం 1. ఉదాహరణకు, a1 = 1 ఈ క్రమంలో 1 మాత్రమే సంభవిస్తుందని చెప్తుంది, కాబట్టి a2 కూడా 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.

గోలోంబ్ సీక్వెన్స్ యొక్క మూలకాలను ఉత్పత్తి చేయడానికి పునరావృత సంబంధం మాకు తెలుసు. పునరావృత సూత్రం

గోలోంబ్ క్రమం
పునరావృత సూత్రాన్ని ఉపయోగించి మేము సమస్యను పరిష్కరిస్తాము. పునరావృతం ఉపయోగించి సమస్యను పరిష్కరించడం ఒక మార్గం. కానీ అది మాకు ఘాతాంక సమయ సంక్లిష్టతను ఖర్చు చేస్తుంది ఎందుకంటే మేము అదే విలువలను మళ్లీ మళ్లీ లెక్కిస్తాము. ఎందుకంటే పునరావృత సంబంధం నుండి మనం చూడగలిగినట్లుగా, క్రమం యొక్క n వ మూలకం గతంలో లెక్కించిన పదాలపై ఆధారపడి ఉంటుంది. కాబట్టి మేము దానిని ఉపయోగించినప్పటి నుండి సమస్యను పరిష్కరించడానికి డైనమిక్ ప్రోగ్రామింగ్‌ను ఉపయోగిస్తాము, మేము ఇతర విలువలను తిరిగి లెక్కించాల్సిన అవసరం లేదు.

కోడ్

గోలోంబ్ సీక్వెన్స్ కోసం సి ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N), ఎందుకంటే n మూలకం గతంలో లెక్కించిన ఒక మూలకంపై ఆధారపడి ఉంటుంది, ఇది ప్రతి మూలకానికి ఈ ఆపరేషన్ O (1) సమయ సంక్లిష్టతను చేస్తుంది. N అంశాలు ఉన్నందున, సమయ సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

O (N), మేము n మూలకాలను నిల్వ చేస్తున్నందున, స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.