ਗੋਲੋਮ ਕ੍ਰਮ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੈਡੈਂਸ ਇੰਡੀਆ ਅਸਲ ਵਿੱਚ ਟਾਈਮਜ਼ ਇੰਟਰਨੈੱਟ ਯਾਤਰਾ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਕ੍ਰਮ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ “ਗੋਲੋਮ ਸੀਨਜ” ਕਹਿੰਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੰਪੁੱਟ ਦਿੱਤਾ ਗਿਆ ਹੈ ਪੂਰਨ ਅੰਕ n ਅਤੇ ਤੁਹਾਨੂੰ ਗੋਲੰਬ ਕ੍ਰਮ ਦੇ ਸਾਰੇ ਤੱਤ ਨੂੰ ਨੌਵੇਂ ਤੱਤ ਤੱਕ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

n = 8
1 2 2 3 3 4 4 4

ਕਥਾ
ਗੋਲੋਮਬ ਲੜੀ ਦੇ ਪਹਿਲੇ 8 ਸ਼ਬਦ ਲੱਭੇ ਅਤੇ ਛਾਪੇ ਗਏ ਹਨ. ਕਿਉਂਕਿ ਆਉਟਪੁਟ ਗੋਲੋਮ ਸੀਨਵੈਂਸ ਦੇ ਪਹਿਲੇ 8 ਤੱਤ ਦਰਸਾਉਂਦਾ ਹੈ, ਆਉਟਪੁੱਟ ਸਹੀ ਹੈ.

ਪਹੁੰਚ

ਗਣਿਤ ਵਿੱਚ, ਦਿੱਤੇ ਤਰਤੀਬ ਨੂੰ ਸਿਲਵਰਮੈਨ ਸੀਕੁਐਂਸ ਵੀ ਕਿਹਾ ਜਾਂਦਾ ਹੈ. ਇਸ ਤਰਤੀਬ ਦਾ ਨਾਮ ਸੁਲੇਮਾਨ ਡਬਲਯੂ. ਗੋਲੋਮਬ ਦੇ ਨਾਮ ਤੇ ਰੱਖਿਆ ਗਿਆ ਹੈ. ਇਹ ਇੱਕ ਘਟਣ ਵਾਲਾ ਪੂਰਨ ਅੰਕ ਹੈ, ਜਿੱਥੇ ਕਿ ਇੱਕ (n) ਉਸ ਸਮੇਂ ਦੀ ਸੰਖਿਆ ਹੈ ਜੋ n ਕ੍ਰਮ ਵਿੱਚ ਵਾਪਰਦਾ ਹੈ. ਗੋਲੋਮ ਲੜੀ ਦਾ ਪਹਿਲਾ ਤੱਤ 1. ਹੈ. ਉਦਾਹਰਣ ਵਜੋਂ, ਏ 1 = 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, XNUMX, 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) ਸਮਾਂ ਗੁੰਝਲਦਾਰ ਬਣਾਉਂਦਾ ਹੈ. ਕਿਉਂਕਿ ਇੱਥੇ ਐ ਐਲੀਮੈਂਟਸ ਹੁੰਦੇ ਹਨ, ਇਸ ਲਈ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਰੇਖੀ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ n ਐਲੀਮੈਂਟਸ ਨੂੰ ਸਟੋਰ ਕਰ ਰਹੇ ਹਾਂ, ਇਸ ਲਈ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਵੀ ਲਕੀਰ ਹੈ.