دنباله موزر دو بروژن


سطح دشواری متوسط
اغلب در شارژ رایگان اسنپدل بار اینترنت
برنامه نویسی پویا دنباله

در این مشکل ، یک ورودی عدد صحیح به شما داده می شود. اکنون شما باید اولین عناصر دنباله Moser-de Bruijn را چاپ کنید.

مثال

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

توضیح

توالی خروجی هفت عنصر اول دنباله Moser-de Bruijn را دارد. بنابراین خروجی کاملاً صحیح است.

روش

In نظریه اعداداز سکانس Moser – de Bruijn است توالی عدد صحیح نامگذاری شده است لئو موزر و نیکولاس گوورت د بروین، متشکل از مجموع توانهای متمایز 4. بنابراین ، این بدان معنی است که شامل تمام اعدادی است که می توانند با استفاده از توانهای مجزا 4 نمایش داده شوند.

ما همچنین می توانیم اعدادی را که توالی Moser-de Bruijn را تشکیل می دهند ، به روشی کمی متفاوت تعریف کنیم. اگر عددی که به سیستم عدد پایه 4 تبدیل شده است فقط شامل 0 یا 1 باشد ، بنابراین می گوییم که این عدد در توالی Moser-de Bruijn وجود دارد. این بدان معنا نیست که سیستم عدد پایه 4 فقط شامل 0 و 1 به عنوان رقم های خود است. نمایش پایه 4 شامل 0 ، 1 ، 2 و 3 است. اما اگر این عدد در توالی ما وجود داشته باشد. این باید برخی از پیش نیازها را دنبال کند که شامل فقط 0 یا 1 در نمای 4 است. بنابراین اکنون با این که چه نوع اعدادی توالی را تشکیل می دهند آشنا شده ایم. اما چگونه چنین اعدادی را تولید می کنیم؟

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

رابطه عود

دنباله موزر دو بروژن

حالت پایه برای n = 0 ، S (0) = 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) نیاز دارد. زمان ، پیچیدگی خطی است.

پیچیدگی فضا

بر)، زیرا ما جدید ایجاد کرده ایم DP آرایه ای که به ورودی وابسته است. پیچیدگی فضا برای این مسئله خطی است.