Низа на голомби


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

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

Проблемот „Голомб низа“ наведува дека ви е даден внес број 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, XNUMX.

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

Низа на голомби
Користејќи ја рекурзивната формула ќе го решиме проблемот. Еден начин е да се реши проблемот користејќи рекурзија. Но, тоа ќе не чини експоненцијална сложеност во времето, бидејќи повторно и повторно ќе ги пресметуваме истите вредности. Бидејќи, како што можеме да видиме од релацијата на повторување, 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

Јава код за низата Голомб

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

Комплексноста на просторот

О (Н), бидејќи чуваме n елементи, просторната сложеност е исто така линеарна.