Пайдарпаии Голомб  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Cadence Ҳиндустон Ҳақиқатан Интернет Times Яра
Барномарезии динамикӣ Нишондиҳанда

Изҳороти мушкилот  

Масъалаи "пайдарпаии Голомб" мегӯяд, ки ба шумо маълумот дода мешавад ҳамаҷониба n ва ба шумо лозим аст, ки ҳамаи унсурҳои пайдарпаии Голомбро то элементи nth пайдо кунед.

мисол  

n = 8
1 2 2 3 3 4 4 4

Шарҳ
8 истилоҳи аввали пайдарпаии Голомб ёфт ва чоп карда шуд. Азбаски баромади аввал 8 унсури пайдарпаии Голомбро ифода мекунад, натиҷа дуруст аст.

усул  

Дар математика пайдарпаии додашударо пайдарпайии Силвермен низ меноманд. Пайдарпаӣ ба номи Сулаймон В.Голомб гузошта шудааст. Ин пайдарпайии камшаванда аст, ки дар он (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.

Мо муносибати такроршавандаро барои тавлиди унсурҳои пайдарпаии Голомб медонем. Формулаи рекурсивӣ ин аст

Пайдарпаии Голомб
Бо истифодаи формулаи рекурсивӣ мо масъаларо ҳал хоҳем кард. Яке аз роҳҳо ҳалли масъала бо истифодаи рекурсия мебошад. Аммо ин ба мо мураккабии вақти экспоненсиалӣ меорад, зеро мо ҳамон арзишҳоро гаштаю баргашта ҳисоб мекунем. Зеро тавре ки мо аз муносибати такрорӣ мебинем, унсури n-и пайдарпаӣ ба истилоҳҳои қаблан ҳисобшуда вобаста аст. Ҳамин тариқ, мо барои ҳалли мушкилот барномасозии динамикиро истифода хоҳем кард, зеро дигар қиматҳоро аз нав ҳисоб кардан лозим нест.

ҳамчунин нигаред
Шумораи максималии сегментҳои дарозии a, b ва c

рамз  

Рамзи 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

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), зеро унсури nth аз як унсури қаблан ҳисобшуда вобаста аст, ки ин амалиёт O (1) -ро барои ҳар як элемент мураккаб месозад. Азбаски n элемент мавҷуд аст, мураккабии вақт хатӣ аст.

Мураккабии фазо

O (N), азбаски мо n элементро нигоҳ медорем, мураккабии фазо низ хаттӣ аст.