تسلسل موسر دي بروين


مستوى الصعوبة متوسط
كثيرا ما يطلب في شحن مجاني Snapdeal مرات الانترنت
البرمجة الديناميكية تسلسل

في هذه المشكلة ، يتم إعطاؤك إدخال عدد صحيح n. أنت الآن بحاجة إلى طباعة العناصر n الأولى من سلسلة Moser-de Bruijn.

مثال

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

تفسير

يحتوي تسلسل الإخراج على العناصر السبعة الأولى من سلسلة Moser-de Bruijn. وبالتالي فإن المخرجات صحيحة تمامًا.

الرسالة

In نظرية الأعدادأطلقت حملة تسلسل موسر دي بروين هو تسلسل صحيح سميت باسم ليو موسر و نيكولاس جوفيرت دي بروين، التي تتكون من مجموع قوى مميزة لـ 4. وهذا يعني أنها ستحتوي على جميع الأرقام التي يمكن تمثيلها باستخدام قوى مميزة لـ 4.

يمكننا أيضًا تحديد الأرقام التي يتكون منها تسلسل Moser-de Bruijn بطريقة مختلفة قليلاً. إذا كان الرقم المحول إلى نظام رقم أساسي 4 يحتوي على 0 أو 1. ثم نقول إن الرقم موجود في تسلسل Moser-de Bruijn. هذا لا يعني أن نظام الأرقام ذو الأساس 4 يحتوي فقط على 0 و 1 كأرقامه. يحتوي تمثيل Base-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

كود Java لإنشاء تسلسل 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 مجموعة تعتمد على المدخلات. التعقيد المكاني للمشكلة خطي.