Голомбова секвенца


Ниво тешкоће Лако
Често питани у Цаденце Индиа Заиста Тимес Интернет Иатра
Динамичко програмирање Секвенца

Изјава о проблему

Проблем „Голомб секвенца“ наводи да сте добили улаз цео број н и треба да пронађете све елементе Голомб секвенце до н-тог елемента.

Пример

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.

Позната нам је релација понављања за генерисање елемената Голомбове секвенце. Рекурзивна формула је

Голомбова секвенца
Користећи рекурзивну формулу решићемо проблем. Један од начина је решавање проблема помоћу рекурзије. Али то ће нас коштати експоненцијалне временске сложености јер ћемо изнова рачунати исте вредности. Јер, као што видимо из релације понављања, н-ти елемент низа зависи од претходно израчунатих чланова. Дакле, користићемо динамичко програмирање да бисмо решили проблем, јер ако га користимо, нећемо морати поново израчунавати друге вредности.

код

Ц ++ код за Голомб секвенцу

#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) чини сложеним за сваки елемент. С обзиром да постоји н елемената, временска сложеност је линеарна.

Сложеност простора

О (Н), пошто чувамо н елемената, сложеност простора је такође линеарна.