Golomb ardıcıllığı

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Cadence Hindistan Həqiqətən Times İnternet Yatra
Dinamik proqramlaşdırma ArdıcıllıqBaxılıb 26

Problem bəyanat

Problem "Golomb ardıcıllığı" sizə bir giriş verildiyini bildirir tam n və n elementə qədər Golomb ardıcıllığının bütün elementlərini tapmaq lazımdır.

misal

n = 8
1 2 2 3 3 4 4 4

Izahat
Golomb ardıcıllığının ilk 8 şərtləri tapılıb çap olunur. Çıxış Golomb ardıcıllığının ilk 8 elementini ifadə etdiyindən, çıxış doğrudur.

Yanaşma

Riyaziyyatda verilmiş ardıcıllığa Silverman's Sequence də deyilir. Ardıcıllıq Solomon W. Golombun adını daşıyır. Azalan olmayan bir tam ardıcıllıqdır, burada a (n) n-in ardıcıllıqla baş vermə sayıdır. Golomb ardıcıllığının ilk elementi 1-dir. Məsələn, a1 = 1, 1-in ardıcıllıqda yalnız bir dəfə meydana gəldiyini, buna görə a2-nin də 1 ola bilməyəcəyini, ancaq ola biləcəyini və buna görə də 2 olması lazım olduğunu söyləyir.

Ardıcıllığın ilk bir neçə şərtləri 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.

Golomb ardıcıllığının elementlərinin yaradılması üçün təkrarlanma əlaqəsini bilirik. Rekursiv düstur

Golomb ardıcıllığı
Rekursiv formuldan istifadə edərək problemi həll edəcəyik. Bir yolu, rekursiyadan istifadə edərək problemi həll etməkdir. Ancaq bu, üst-üstə zaman mürəkkəbliyinə başa gələcək, çünki eyni dəyərləri dəfələrlə hesablayacağıq. Çünki təkrarlanma münasibətindən də göründüyü kimi ardıcıllığın n elementi əvvəllər hesablanmış şərtlərdən asılıdır. Beləliklə, problemi istifadə etdikdən bəri həll etmək üçün Dinamik Proqramlaşdırma istifadə edəcəyik, digər dəyərləri yenidən hesablamaq məcburiyyətində qalmayacağıq.

Kodu

Golomb Sıra üçün C ++ kodu

#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

Golomb Sequence üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki n-ci element bu əməliyyatı O (1) -i hər element üçün mürəkkəbləşdirən əvvəlcədən hesablanmış bir elementdən asılıdır. N element olduğu üçün zaman mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (N), n elementi saxladığımızdan, kosmik mürəkkəblik də xəttlidir.

Translate »