Moser-de Bruijn თანმიმდევრობა


Რთული ტური საშუალო
ხშირად ეკითხებიან უფასო დატენვა Snapdeal Times ინტერნეტი
დინამიური პროგრამირება თანმიმდევრობა

ამ პრობლემის დროს, თქვენ გეძლევათ n. ახლა თქვენ უნდა დაბეჭდოთ Moser-de Bruijn თანმიმდევრობის პირველი n ელემენტები.

მაგალითი

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

განმარტება

გამომავალ თანმიმდევრობას აქვს Moser-de Bruijn თანმიმდევრობის პირველი შვიდი ელემენტი. ამრიგად, გამოცემა აბსოლუტურად სწორია.

მიდგომა

In რიცხვების თეორიასაქართველოს Moser – de Bruijn თანმიმდევრობა არის მთელი თანმიმდევრობა სახელობის ლეო მოსერი და ნიკოლას გოვერტ დე ბრიუინი, შედგება 4 განსხვავებული ძალების ჯამებისაგან. ასე რომ, ეს ნიშნავს, რომ იგი შეიცავს ყველა იმ რიცხვს, რომელთა წარმოდგენა შესაძლებელია 4-ის მკაფიო ძალების გამოყენებით.

ჩვენ ასევე შეგვიძლია ცოტა განსხვავებულად განვსაზღვროთ ციფრები, რომლებიც ქმნიან Moser-de Bruijn Sequence- ს. თუ ფუძე -4 რიცხვის სისტემაში გადაკეთებული რიცხვი შეიცავს მხოლოდ 0-ს ან 1-ს. მაშინ ჩვენ ვამბობთ, რომ ნომერი არსებობს Moser-de Bruijn თანმიმდევრობით. ეს არ ნიშნავს, რომ ბაზა-4 რიცხვითი სისტემა შეიცავს მხოლოდ 0 და 1 ციფრებს. Base-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

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 მასივი, რომელიც დამოკიდებულია შეყვანაზე. სივრცის სირთულე პრობლემისთვის ხაზოვანია.