លំដាប់ Golomb  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Cadence ឥណ្ឌា ជា​ការ​ពិត អ៊ិនធឺណិតដង។ Yatra
ការសរសេរកម្មវិធីឌីណាមិក លំដាប់

សេចក្តីថ្លែងការណ៍បញ្ហា។  

បញ្ហា“ លំដាប់ Golomb” បានចែងថាអ្នកត្រូវបានផ្តល់យោបល់ integer n ហើយអ្នកត្រូវរកធាតុទាំងអស់នៃលំដាប់ហ្គូបមរហូតដល់ធាតុទី។

ឧទាហរណ៍  

n = 8
1 2 2 3 3 4 4 4

ការពន្យល់
លក្ខខណ្ឌ ៨ ដំបូងនៃលំដាប់ហ្គូបមត្រូវបានរកឃើញនិងបោះពុម្ព។ ដោយសារលទ្ធផលបង្ហាញពីធាតុទាំង ៨ ដំបូងនៃលំដាប់ហ្គោលបមលទ្ធផលត្រឹមត្រូវ។

វិធីសាស្រ្ត  

នៅក្នុងគណិតវិទ្យាលំដាប់ដែលបានផ្តល់ឱ្យត្រូវបានគេហៅថាលំដាប់លំដោយ Silverman ផងដែរ។ លំដាប់ត្រូវបានដាក់ឈ្មោះតាមសាឡូម៉ូនដបុលយូកូលប។ វាជាលំដាប់ចំនួនគត់ដែលមិនថយចុះដែល a (n) គឺជាចំនួនដងដែល n កើតឡើងក្នុងលំដាប់។ ធាតុទី ១ របស់កូឡុំបឹមគឺ ១ ។ ឧទាហរណ៍ a1 = ១ និយាយថា ១ កើតឡើងតែម្តងក្នុងលំដាប់ដូច្នេះ a1 មិនអាច ១ ដែរតែវាអាចជាហើយដូច្នេះត្រូវតែ ២ ។

ពាក្យពីរបីដំបូងនៃលំដាប់គឺ ១, ២, ៣, ៣, ៤, ៤, ៤, ៥, ៥, ៥, ៦, ៦, ៦, ៧, ៧, ៨, ៨, ៨ ៨, ៨, ៩, ៩, ៩, ៩, ១០, ១០, ១០, ១០, ១១, ១១, ១១, ១២, ១២ ។

យើងដឹងពីទំនាក់ទំនងកើតឡើងចំពោះការបង្កើតធាតុនៃលំដាប់ហ្គូបម។ រូបមន្តហៅឡើងវិញគឺ

លំដាប់ Golomb
ដោយប្រើរូបមន្តហៅខ្លួនឯងយើងនឹងដោះស្រាយបញ្ហា។ វិធីមួយគឺត្រូវដោះស្រាយបញ្ហាដោយប្រើការហៅខ្លួនឯង។ ប៉ុន្តែនោះនឹងធ្វើឱ្យយើងខាតពេលវេលាអិចស្ប៉ូណង់ស្យែលពីព្រោះយើងនឹងគណនាតម្លៃដូចគ្នាម្តងហើយម្តងទៀត។ ដោយសារតែដូចដែលយើងអាចមើលឃើញពីទំនាក់ទំនងកើតឡើងដដែលៗធាតុទីនៃលំដាប់គឺពឹងផ្អែកលើពាក្យដែលបានគណនាពីមុន។ ដូច្នេះយើងនឹងប្រើ Dynamic Programming ដើម្បីដោះស្រាយបញ្ហាចាប់តាំងពីប្រើវាយើងនឹងមិនចាំបាច់គណនាតម្លៃផ្សេងទៀតទេ។

សូម​មើល​ផង​ដែរ
ចំនួនអតិបរមានៃចម្រៀកនៃប្រវែង 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 គឺអាស្រ័យលើធាតុដែលបានគណនាពីមុនដែលធ្វើឱ្យប្រតិបត្ដិការនេះមានពេលវេលាស្មុគស្មាញ (១) សម្រាប់ធាតុនីមួយៗ ដោយសារមានធាតុ n ភាពស្មុគស្មាញពេលវេលាគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N) ដោយសារយើងកំពុងរក្សាទុកធាតុ n ភាពស្មុគស្មាញនៃលំហក៏ជាលីនេអ៊ែរដែរ។