ഗോലോംബ് സീക്വൻസ്


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു കഡെൻസ് ഇന്ത്യ തീർച്ചയായും ടൈംസ് ഇന്റർനെറ്റ് യാത്ര
ഡൈനാമിക് പ്രോഗ്രാമിംഗ് അനുക്രമം

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

“ഗൊലോംബ് സീക്വൻസ്” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു ഇൻപുട്ട് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ n കൂടാതെ ഒൻപതാം ഘടകം വരെ നിങ്ങൾ ഗോലോംബ് സീക്വൻസിന്റെ എല്ലാ ഘടകങ്ങളും കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

n = 8
1 2 2 3 3 4 4 4

വിശദീകരണം
ഗോലോംബ് സീക്വൻസിന്റെ ആദ്യ 8 പദങ്ങൾ കണ്ടെത്തി അച്ചടിക്കുന്നു. Gol ട്ട്‌പുട്ട് ഗോലോംബ് സീക്വൻസിന്റെ ആദ്യ 8 ഘടകങ്ങളെ സൂചിപ്പിക്കുന്നതിനാൽ, output ട്ട്‌പുട്ട് ശരിയാണ്.

സമീപനം

ഗണിതശാസ്ത്രത്തിൽ, നൽകിയിരിക്കുന്ന ശ്രേണിയെ സിൽവർമാൻ സീക്വൻസ് എന്നും വിളിക്കുന്നു. സോളമൻ ഡബ്ല്യു. ഗോലോംബിന്റെ പേരിലാണ് ഈ ശ്രേണി. ഇത് കുറയാത്ത സംഖ്യയാണ്, ഇവിടെ a (n) എന്നത് ശ്രേണിയിൽ n സംഭവിക്കുന്നതിന്റെ എണ്ണം. ഗോലോംബ് സീക്വൻസിന്റെ ആദ്യ ഘടകം 1 ആണ്. ഉദാഹരണത്തിന്, 1 ൽ ഒരു തവണ മാത്രമേ സംഭവിക്കുകയുള്ളൂവെന്ന് a1 = 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.

ഗോലോംബ് സീക്വൻസിന്റെ ഘടകങ്ങൾ സൃഷ്ടിക്കുന്നതിനുള്ള ആവർത്തന ബന്ധം നമുക്കറിയാം. ആവർത്തന സൂത്രവാക്യം

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

കോഡ്

ഗോലോംബ് സീക്വൻസിനായുള്ള സി ++ കോഡ്

#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 ഘടകങ്ങൾ സംഭരിക്കുന്നതിനാൽ, സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.