ගොලොම්බ අනුක්‍රමය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ කේඩන්ස් ඉන්දියාව ඇත්ත වශයෙන්ම ටයිම්ස් අන්තර්ජාලය යත්රා
ගතික වැඩසටහන්කරණය අනුපිළිවෙල

ගැටළු ප්රකාශය

“ගොලොම්බ් අනුක්‍රමය” ගැටලුවේ සඳහන් වන්නේ ඔබට ආදානයක් ලබා දී ඇති බවයි නිඛිල n සහ n වන මූලද්‍රව්‍යය තෙක් ගොලොම්බ් අනුක්‍රමයේ සියලුම අංග සොයාගත යුතුය.

උදාහරණයක්

n = 8
1 2 2 3 3 4 4 4

පැහැදිලි කිරීම
ගොලොම්බ් අනුක්‍රමයේ පළමු පද 8 සොයාගෙන මුද්‍රණය කර ඇත. ප්‍රතිදානය ගොලොම්බ් අනුක්‍රමයේ පළමු අංග 8 නිරූපණය කරන බැවින් ප්‍රතිදානය නිවැරදි ය.

ප්රවේශය

ගණිතයේ දී, දී ඇති අනුක්‍රමය සිල්වර්මන්ගේ අනුක්‍රමය ලෙස ද හැඳින්වේ. අනුක්‍රමය නම් කර ඇත්තේ සොලමන් ඩබ්ලිව්. ගොලොම්බ් විසිනි. එය අඩු නොවන පූර්ණ සංඛ්‍යා අනුක්‍රමයකි, එහිදී a (n) යනු අනුක්‍රමය තුළ n සිදුවන වාර ගණන වේ. ගොලොම්බ් අනුක්‍රමයේ පළමු මූලද්‍රව්‍යය 1. නිදසුනක් ලෙස, a1 = 1 පවසන්නේ අනුක්‍රමය තුළ එක් වරක් පමණක් සිදුවන බවයි, එබැවින් a1 ද 2 විය නොහැක, නමුත් එය එසේ විය හැකි අතර එබැවින් 1 විය යුතුය.

අනුක්‍රමයේ පළමු පද කිහිපය නම් 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.

ගොලොම්බ් අනුක්‍රමයේ මූලද්‍රව්‍ය ජනනය කිරීම සඳහා පුනරාවර්තන සම්බන්ධතාවය අපි දනිමු. පුනරාවර්තන සූත්‍රය වේ

ගොලොම්බ අනුක්‍රමය
පුනරාවර්තන සූත්‍රය භාවිතා කරමින් අපි ගැටළුව විසඳන්නෙමු. එක් ක්‍රමයක් නම් පුනරාවර්තනය භාවිතා කරමින් ගැටළුව විසඳීමයි. නමුත් එමඟින් අපට on ාතීය කාල සංකීර්ණත්වයක් වැය වනු ඇත, මන්ද අප එකම අගයන් නැවත නැවතත් ගණනය කරනු ඇත. පුනරාවර්තන සම්බන්ධතාවයෙන් අපට පෙනෙන පරිදි අනුක්‍රමයේ 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 ගබඩා කරන බැවින් අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.