Последователност на Moser-de Bruijn


Ниво на трудност M
Често задавани в FreeCharge Snapdeal Times Интернет
Динамично програмиране Последователност

В този проблем получавате цяло число n. Сега трябва да отпечатате първите n елементи от последователността Moser-de Bruijn.

Пример

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

Обяснение

Изходната последователност има първите седем елемента от последователността на Moser-de Bruijn. По този начин изходът е абсолютно правилен.

Подход

In теория на числата, на Последователност на Moser – de Bruijn е целочислена последователност кръстен на Лео Мозер и Николаас Говерт де Броййн, състоящ се от сумите на различни степени на 4. Така че това означава, че ще съдържа всички числа, които могат да бъдат представени с помощта на различни степени на 4.

Можем също така да дефинираме числата, които съставляват последователността на Moser-de Bruijn, по малко по-различен начин. Ако числото, преобразувано в числова система base-4, съдържа само 0 или 1. Тогава казваме, че числото съществува в Moser-de Bruijn Sequence. Това не означава, че числовата система base-4 съдържа само 0 и 1 като цифри. Представянето на Base-4 съдържа 0, 1, 2 и 3. Но ако числото съществува в нашата последователност. Той трябва да спазва някои предпоставки, които трябва да съдържат само 0 или 1 в представяне на base-4. Така че сега сме запознати с какъв тип числа образуват последователността. Но как да генерираме такива числа?

Един прост начин е да се използва формулата за повторение, която се използва за генериране на числата на последователността. Но има уловка.

Рецидивиращата връзка

Последователност на Moser-de Bruijn

Основният случай е за n = 0, S (0) = 0. Сега, ако просто използваме връзката за повторение, ще изчислим някои стойности повече от веднъж. Този процес ще се добави само за увеличаване на сложността на времето. За да подобрим нашия алгоритъм, ще съхраним тези стойности, което ще намали изчисленията. Тази техника, при която съхраняваме данните, които могат да бъдат използвани по-късно по време на изчислението, обикновено се нарича Динамично програмиране. Вижте основите на динамично програмиране тук.

код

C ++ код за генериране на Moser-de Bruijn Sequence

#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 масив, който зависи от входа. Сложността на пространството за проблема е линейна.