ลำดับ Moser-de Bruijn


ระดับความยาก กลาง
ถามบ่อยใน ฟรีค่าธรรมเนียม Snapdeal ไทม์อินเทอร์เน็ต
การเขียนโปรแกรมแบบไดนามิก ลำดับ

ในปัญหานี้คุณจะได้รับอินพุตจำนวนเต็ม n ตอนนี้คุณต้องพิมพ์ n องค์ประกอบแรกของลำดับ Moser-de Bruijn

ตัวอย่าง

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

คำอธิบาย

ลำดับเอาต์พุตมีเจ็ดองค์ประกอบแรกของลำดับ Moser-de Bruijn ดังนั้นผลลัพธ์จึงถูกต้องอย่างแน่นอน

เข้าใกล้

In ทฤษฎีจำนวนที่ ลำดับโมเซอร์ - เดอบรอยน์ เป็น ลำดับจำนวนเต็ม การตั้งชื่อตาม ลีโอโมเซอร์ และ  Nicolaas Govert de Bruijnประกอบด้วยผลรวมของพลังที่แตกต่างกันของ 4 ดังนั้นหมายความว่ามันจะมีตัวเลขทั้งหมดที่สามารถแสดงโดยใช้พลังที่แตกต่างกันของ 4

นอกจากนี้เรายังสามารถกำหนดตัวเลขที่ประกอบขึ้นเป็นลำดับ Moser-de Bruijn ในลักษณะที่แตกต่างกันเล็กน้อย หากตัวเลขที่แปลงเป็นระบบเลขฐาน 4 มีเพียง 0 หรือ 1 เราจะบอกว่าตัวเลขนั้นมีอยู่ในลำดับ Moser-de Bruijn ไม่ได้หมายความว่าระบบเลขฐาน 4 มีเพียง 0 และ 1 เป็นหลัก การแทนค่าฐาน -4 ประกอบด้วย 0, 1, 2 และ 3 แต่ถ้าตัวเลขมีอยู่ในลำดับของเรา จำเป็นต้องปฏิบัติตามข้อกำหนดเบื้องต้นบางประการซึ่งจะต้องมีเพียง 0 หรือ 1 ในการแทนค่าฐาน -4 ตอนนี้เราคุ้นเคยกับประเภทของตัวเลขที่สร้างลำดับ แต่เราจะสร้างตัวเลขดังกล่าวได้อย่างไร?

วิธีง่ายๆวิธีหนึ่งคือการใช้สูตรการเกิดซ้ำซึ่งใช้ในการสร้างตัวเลขของลำดับ แต่มีการจับ

ความสัมพันธ์การเกิดซ้ำ

ลำดับ Moser-de Bruijn

กรณีฐานคือสำหรับ 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 Sequence

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 อาร์เรย์ซึ่งขึ้นอยู่กับอินพุต ความซับซ้อนของปริภูมิสำหรับปัญหาเป็นเชิงเส้น