លំដាប់ Moser-de Bruijn


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ FreeCharge Snapdeal អ៊ិនធឺណិតដង។
ការសរសេរកម្មវិធីឌីណាមិក លំដាប់

នៅក្នុងបញ្ហានេះអ្នកត្រូវបានផ្តល់ឱ្យនូវចំនួនគត់បញ្ចូល n ។ ឥឡូវអ្នកត្រូវបោះពុម្ពធាតុ n ដំបូងនៃលំដាប់ Moser-de Bruijn ។

ឧទាហរណ៍

7
0, 1, 4, 5, 16, 17, 20

ការពន្យល់

លំដាប់លទ្ធផលមានធាតុប្រាំពីរដំបូងនៃលំដាប់ Moser-de Bruijn ។ ដូច្នេះលទ្ធផលគឺពិតជាត្រឹមត្រូវ។

វិធីសាស្រ្ត

In ទ្រឹស្តីលេខនេះ លំដាប់ Moser-de Bruijn គឺជា លំដាប់លេខគត់ ដាក់ឈ្មោះតាម ឡេអូម៉ូសឺរ និង នីកូឡាសហ្គូវឌ័រប្រូជិនដែលរួមមានផលបូកនៃផលបូកខុសគ្នានៃថាមពល 4. ដូច្នេះមានន័យថាវានឹងមានលេខទាំងអស់ដែលអាចត្រូវបានតំណាងដោយប្រើថាមពលខុសគ្នា 4 ។

យើងក៏អាចកំណត់លេខដែលបង្កើតជាលំដាប់ Moser-de Bruijn តាមលក្ខណៈខុសគ្នាបន្តិចបន្តួច។ ប្រសិនបើលេខដែលបានប្តូរទៅជាប្រព័ន្ធលេខ ៤ មានត្រឹមតែ ០ រឺ ១ ។ បន្ទាប់មកយើងនិយាយថាលេខមាននៅក្នុងលំដាប់ Moser-de Bruijn ។ វាមិនមានន័យថាប្រព័ន្ធលេខគោល ៤ មានត្រឹមតែ ០ និង ១ ជាតួលេខរបស់វា។ ការតំណាងមូលដ្ឋាន -៤ មាន ០, ១, ២, និង ៣។ ប៉ុន្តែប្រសិនបើលេខមាននៅក្នុងលំដាប់របស់យើង។ វាចាំបាច់ត្រូវអនុវត្តតាមតម្រូវការបឋមមួយចំនួនដែលមានផ្ទុកតែ ០ ឬ ១ ជាតំណាងមូលដ្ឋាន ៤ ។ ដូច្នេះឥឡូវនេះយើងស៊ាំជាមួយលេខប្រភេទណាដែលបង្កើតជាលំដាប់។ ប៉ុន្តែតើយើងបង្កើតលេខបែបនេះយ៉ាងដូចម្តេច?

វិធីសាមញ្ញមួយគឺប្រើរូបមន្តកើតឡើងដដែលៗដែលត្រូវបានប្រើដើម្បីបង្កើតលេខនៃលំដាប់។ ប៉ុន្តែមានការចាប់។

ទំនាក់ទំនងកើតឡើងដដែលៗ

លំដាប់ Moser-de Bruijn

ករណីមូលដ្ឋានគឺសម្រាប់ n = 0, S (0) = ០ ។ ឥឡូវប្រសិនបើយើងប្រើទំនាក់ទំនងកើតឡើងដដែលៗយើងនឹងគណនាតម្លៃមួយចំនួនច្រើនជាងមួយដង។ ដំណើរការនេះនឹងបន្ថែមតែដើម្បីបង្កើនពេលវេលាស្មុគស្មាញ។ ដើម្បីធ្វើឱ្យប្រសើរឡើងនូវក្បួនដោះស្រាយរបស់យើងយើងនឹងរក្សាទុកតម្លៃទាំងនេះដែលនឹងកាត់បន្ថយការគណនា។ បច្ចេកទេសនេះដែលយើងរក្សាទុកទិន្នន័យដែលអាចត្រូវបានប្រើនៅពេលក្រោយក្នុងកំឡុងពេលគណនាជាទូទៅត្រូវបានគេហៅថា ការសរសេរកម្មវិធីឌីណាមិក។ ពិនិត្យមើលមូលដ្ឋានគ្រឹះនៃ ការសរសេរកម្មវិធីថាមវន្ត នៅ​ទីនេះ.

លេខកូដ

កូដ C ++ ដើម្បីបង្កើតលំដាប់ Moser-de Bruijn

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of elements to be generated
  int n;cin>>n;
  if(n >= 1)cout<<0<<" ";
  if(n >= 2)cout<<1<<" ";
  if(n >= 3) {
    int dp[n];
    dp[0] = 0,dp[1] = 1;
    for(int i=2; i<n;i++){
      if(i%2 == 0)
        dp[i] = 4*dp[i/2];
      else
        dp[i] = 4*dp[i/2] + 1;
      cout<<dp[i]<<" ";
    }
  }
}
6
0 1 4 5 16 17

កូដចាវ៉ាដើម្បីបង្កើតលំដាប់ Moser-de Bruijn

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements to be generated
    int n = sc.nextInt();
    if(n >= 1)System.out.print("0 ");
    if(n >= 2)System.out.print("1 ");
    if(n >= 3) {
      int dp[] = new int[n];
      dp[0] = 0;dp[1] = 1;
      for(int i=2; i<n;i++){
        if(i%2 == 0)
          dp[i] = 4*dp[i/2];
        else
          dp[i] = 4*dp[i/2] + 1;
        System.out.print(dp[i]+" ");
      }
    }
  }
}
6
0 1 4 5 16 17

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ពីព្រោះនៅពេលដែលលេខមួយត្រូវបានគណនាវាមិនមានពេលវេលាដែលត្រូវការដើម្បីប្រើវានៅពេលក្រោយក្នុងការគណនាទេ។ ចាប់តាំងពីការគណនាមុនទាមទារពេលវេលា O (N) ។ ពេលវេលាភាពស្មុគស្មាញគឺលីនេអ៊ែរ។

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

O (N), ពីព្រោះយើងបានបង្កើតថ្មី DP អារេដែលអាស្រ័យលើធាតុបញ្ចូល។ ភាពស្មុគស្មាញនៃលំហសម្រាប់បញ្ហាគឺលីនេអ៊ែរ។