Moser-de Bruijn အဆက်မပြတ်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် FreeCharge Snapdeal Times ကိုအင်တာနက်
Dynamic Programming အစဉ်အတိုင်းလိုက်ခြင်း

ဤပြproblemနာတွင်သင့်အားကိန်းပြည့်ထည့်သွင်းမှု n ပေးထားသည်။ ယခုသင်သည် Moser-de Bruijn အဆက်မပြတ်၏ပထမဆုံး n element များကိုပုံနှိပ်ထုတ်ရန်လိုအပ်သည်။

နမူနာ

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

ရှင်းလင်းချက်

output sequence တွင် Moser-de Bruijn အဆက်မပြတ်၏ပထမခုခု element တွေရှိတယ်။ ထို့ကြောင့် output ကိုလုံးဝမှန်ကန်သည်။

ချဉ်းကပ်နည်း

In ဂဏန်းသီအိုရီ, အ Moser-de Bruijn sequence ကို တစ်ဦးဖြစ်ပါတယ် ကိန်းဂဏန်းအရေအတွက် ပြီးနောက်အမည်ရှိ Leo Moser နှင့် Nicolaas Govert က de Bruijn, 4 ၏ကွဲပြားနိုင်သည့်စွမ်းရည်များကိန်းဂဏန်းများပါဝင်သည်။ ဆိုလိုသည်မှာ ၄ သည်ကွဲပြားသောစွမ်းအားများကို အသုံးပြု၍ ကိုယ်စားပြုနိုင်သည့်နံပါတ်များအားလုံးပါဝင်လိမ့်မည်။

Moser-de Bruijn အဆက်မပြတ်ဖြစ်စေသည့်နံပါတ်များကိုအနည်းငယ်နည်းနည်းဖြင့်လည်းကျွန်ုပ်တို့သတ်မှတ်နိုင်သည်။ base-4 number system သို့ပြောင်းလိုက်သောအရေအတွက်သည် 0 သို့မဟုတ် 1 သာရှိလျှင်၎င်းသည် Moser-de Bruijn အဆက်မပြတ်တွင်ရှိသည်ဟုကျွန်ုပ်တို့ဆိုကြသည်။ အခြေခံ -၄ ဂဏန်းစနစ်တွင် 4 နှင့် 0 သာကိန်းဂဏန်းများပါဝင်သည်ဟုမဆိုလိုပါ။ Base-1 ကိုယ်စားပြုမှုတွင် 4, 0, 1 နှင့် 2 တို့ပါ ၀ င်သည်။ အကယ်၍ အရေအတွက်သည်ကျွန်ုပ်တို့၏အစီအစဉ်တွင်တည်ရှိပါက။ Base-3 ကိုယ်စားပြုမှုတွင် 0 သို့မဟုတ် 1 သာပါဝင်ရမည်ဖြစ်သောလိုအပ်ချက်များကိုလိုက်နာရန်လိုအပ်သည်။ ဒီတော့ကိန်းဂဏန်းပုံစံကိုမည်သည့်ဂဏန်းအမျိုးအစားနှင့်အကျွမ်းတဝင်ရှိပြီလဲ။ သို့သော်ကျွန်ုပ်တို့သည်ထိုကဲ့သို့သောနံပါတ်များကိုမည်သို့ထုတ်လုပ်နိုင်သနည်း။

ရိုးရှင်းသောနည်းတစ်နည်းမှာ sequence ၏နံပါတ်များကိုထုတ်လုပ်ရန်အတွက်အသုံးပြုသော recurrence formula ကိုအသုံးပြုရန်ဖြစ်သည်။ ဒါပေမယ့်ဖမ်းမိတယ်။

အဆိုပါထပ်မဖြစ်အောင်စပ်လျဉ်း

Moser-de Bruijn အဆက်မပြတ်

အခြေအနေမှာ n = 0, S (0) = 0. အတွက်ဖြစ်သည်။ ယခုကျွန်ုပ်တို့သည်ထပ်တလဲလဲဆက်စပ်မှုကိုသာအသုံးပြုပါကကျွန်ုပ်တို့သည်တန်ဖိုးအချို့ကိုတစ်ကြိမ်ထက် ပို၍ တွက်ချက်လိမ့်မည်။ ဤလုပ်ငန်းစဉ်သည်အချိန်ရှုပ်ထွေးမှုကိုတိုးမြှင့်စေရန်တက်လာလိမ့်မည်။ ကျွန်ုပ်တို့၏ algorithm ကိုတိုးတက်စေရန်ကျွန်ုပ်တို့သည်တန်ဖိုးများကိုသိမ်းဆည်းပြီး၎င်းသည်တွက်ချက်မှုကိုလျှော့ချလိမ့်မည်။ ကျွန်ုပ်တို့တွက်ချက်သည့်ဒေတာများကိုသိမ်းဆည်းသောဤနည်းစနစ်ကိုယေဘုယျအားဖြင့်ရည်ညွှန်းသည် Dynamic Programming။ ၏အခြေခံထွက်စစ်ဆေးပါ dynamic programming ကို ဒီမှာ.

ကုဒ်

Moser-de Bruijn အဆက်မပြတ်ထုတ်လုပ်ရန် C ++ ကုဒ်

#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 အဆက်မပြတ်ထုတ်လုပ်ရန် Java ကုဒ်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာလို့လဲဆိုတော့နံပါတ်တစ်ခုကိုတွက်ချက်တာနဲ့တွက်ချက်မှုနောက်မှာအဲဒါကိုသုံးဖို့အချိန်မရှိဘူး။ pre-တွက်ချက်မှုအို (N) အချိန်လိုအပ်ပါတယ်ကတည်းက။ အဆိုပါအချိန်, ရှုပ်ထွေး linear ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (N)၊ ငါတို့အသစ်တစ်ခုကိုဖန်တီးခဲ့ကြလို့ပဲ DP input ကိုအပေါ်မှီခိုသောခင်းကျင်း။ ပြtheနာအတွက်အာကာသရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။