רצף גולומב  


רמת קושי קַל
נשאל לעתים קרובות קדנס הודו אכן פעמים באינטרנט יטרה
תכנות דינמי רצף

הצהרת בעיה  

הבעיה "רצף גולומב" קובעת שאתה מקבל קלט מספר שלם 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 של הרצף תלוי במונחים שחושבו בעבר. אז נשתמש בתכנות דינמי כדי לפתור את הבעיה מאחר והשימוש בה, לא נצטרך לחשב מחדש ערכים אחרים.

ראה גם
המספר המרבי של קטעי אורכים 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 אלמנטים, מורכבות החלל היא גם לינארית.