Последовательность Голомба


Сложный уровень Легко
Часто спрашивают в Cadence Индия В самом деле Таймс Интернет ятра
Динамическое программирование Последовательность

Постановка задачи

Задача «Последовательность Голомба» гласит, что вам предоставлен ввод целое 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-й элемент последовательности зависит от ранее вычисленных членов. Поэтому мы будем использовать динамическое программирование для решения проблемы, поскольку при его использовании нам не придется повторно вычислять другие значения.

Код:

Код C ++ для последовательности Голомба

#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

Код Java для последовательности Голомба

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 элементов, сложность пространства также линейна.