سکانس گلومب  


سطح دشواری ساده
اغلب در کادنس هند در واقع بار اینترنت یاترا
برنامه نویسی پویا دنباله

بیان مسأله  

مسئله "دنباله Golomb" بیان می کند که به شما ورودی داده می شود عدد صحیح n و شما باید تمام عناصر دنباله Golomb را تا عنصر n پیدا کنید.

مثال  

n = 8
1 2 2 3 3 4 4 4

توضیح
8 اصطلاح اول توالی Golomb پیدا شده و چاپ می شود. از آنجا که خروجی نشان دهنده 8 عنصر اول دنباله Golomb است ، خروجی درست است.

روش  

در ریاضیات ، توالی داده شده دنباله سیلورمن نیز نامیده می شود. این سکانس به نام Solomon W. Golomb نامگذاری شده است. این یک دنباله صحیح بدون کاهش است که در آن a (n) تعداد دفعاتی است که n در دنباله رخ می دهد. اولین عنصر دنباله Golomb 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 ، XNUMX.

ما می دانیم که رابطه عود برای تولید عناصر دنباله Golomb. فرمول بازگشتی است

سکانس گلومب
با استفاده از فرمول بازگشتی مسئله را حل خواهیم کرد. یکی از راه ها حل مسئله با استفاده از بازگشت است. اما این برای ما پیچیدگی زمانی نمایی خواهد بود زیرا ما دوباره و دوباره همان مقادیر را محاسبه خواهیم کرد. زیرا همانطور که از رابطه عود می بینیم عنصر 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

کد جاوا برای دنباله 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) ، زیرا عنصر n به یک عنصر قبلاً محاسبه شده بستگی دارد که این عملیات را برای هر عنصر O (1) پیچیده می کند. از آنجا که n عنصر وجود دارد ، پیچیدگی زمان خطی است.

پیچیدگی فضا

O (N) ، از آنجا که n عنصر را ذخیره می کنیم ، پیچیدگی فضا نیز خطی است.