Moser-de Bruijn Sıra

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Pulsuz yükləmə Snapdeal Times İnternet
Dinamik proqramlaşdırma ArdıcıllıqBaxılıb 22

Bu problemdə sizə n tam girişi verilir. İndi Moser-de Bruijn Sırasının ilk n elementini çap etməlisiniz.

misal

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

Izahat

Çıxış ardıcıllığı Moser-de Bruijn Sırasının ilk yeddi elementinə malikdir. Beləliklə nəticə tamamilə doğrudur.

Yanaşma

In say nəzəriyyəsiKi, Moser – de Bruijn ardıcıllığı bir tam ardıcıllıqla adlı Şir Moser və Nikolaas Qovert de Bruijn, 4-ün fərqli güclərinin cəmlərindən ibarətdir. Beləliklə, 4-ün fərqli güclərindən istifadə edərək göstərilə bilən bütün rəqəmləri ehtiva edir.

Moser-de Bruijn ardıcıllığını təşkil edən rəqəmləri bir az fərqli şəkildə də təyin edə bilərik. Əgər baza-4 say sisteminə çevrilən ədədin yalnız 0 və ya 1-i varsa, onda sayın Moser-de Bruijn Sırasında mövcud olduğunu deyirik. Baza-4 say sisteminin rəqəmləri olaraq yalnız 0 və 1-i ehtiva etdiyi demək deyil. Base-4 nümayəndəliyi 0, 1, 2 və 3-ü ehtiva edir. Ancaq rəqəm ardıcıllığımızda varsa. Baza-0 təmsilçiliyində yalnız 1 və ya 4-i ehtiva edən bəzi ilkin şərtlərə riayət etməlidir. Beləliklə, ardıcıllığı hansı növ növlər təşkil etdiyini bilirik. Bəs bu cür rəqəmləri necə yaradırıq?

Sadə bir yol, ardıcıllığın nömrələrini yaratmaq üçün istifadə olunan təkrarlama düsturundan istifadə etməkdir. Ancaq bir ov var.

Təkrarlanma əlaqəsi

Moser-de Bruijn Sıra

Əsas vəziyyət n = 0, S (0) = 0 üçündür. İndi təkrarlanma münasibətindən istifadə etsək, bəzi dəyərləri dəfələrlə hesablayacağıq. Bu proses yalnız vaxtın mürəkkəbliyini artırmaq üçün əlavə edəcəkdir. Alqoritmimizi yaxşılaşdırmaq üçün hesablamaları azaldacaq bu dəyərləri saxlayacağıq. Daha sonra hesablama zamanı istifadə edilə bilən məlumatları saxladığımız bu texnikaya ümumiyyətlə deyilir Dinamik proqramlaşdırma. Əsaslarını yoxlayın dinamik proqramlaşdırma burada.

Kodu

Moser-de Bruijn Sıra yaratmaq üçün C ++ kodu

#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 Sıra yaratmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki bir nömrə hesablandıqdan sonra onu hesablamada istifadə etmək üçün vaxt qalmır. Əvvəlcədən hesablama O (N) vaxt tələb etdiyindən. Zaman, mürəkkəblik doğrudur.

Kosmik Mürəkkəblik

O (N), çünki yenisini yaratdıq DP girişdən asılı olan bir sıra. Problem üçün kosmik mürəkkəblik doğrudur.

Translate »