Паслядоўнасць Голамба


Узровень складанасці Лёгка
Часта пытаюцца ў Cadence Індыя Сапраўды Times Інтэрнэт яйкі
Дынамічнае праграмаванне Паслядоўнасць

Пастаноўка праблемы

Праблема «Паслядоўнасць Голамба» абвяшчае, што вам дадзены ўвод цэлае 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 ++ для паслядоўнасці Golomb

#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 для Golomb Sequence

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 элементаў, складанасць прасторы таксама лінейная.