Послідовність Мозер-де Бруйна


Рівень складності Medium
Часто запитують у FreeCharge Snapdeal Times Інтернет
Динамічне програмування Послідовність

У цій задачі вам дається ціле число n. Тепер вам потрібно надрукувати перші n елементів Послідовності Мозер-де Бруйна.

Приклад

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

Пояснення

Вихідна послідовність містить перші сім елементів послідовності Мозера-де-Брюйна. Таким чином, результат абсолютно правильний.

Підхід

In теорія чисел, то Послідовність Мозера – де Бруйна є ціла послідовність імені Лео Мозер і Ніколааса Говерта де Бруйна, що складається з сум різних степеней 4. Таким чином, це означає, що він буде містити всі числа, які можна представити, використовуючи різні степені 4.

Ми також можемо визначити цифри, що складають послідовність Мозер-де Бруйна, дещо по-іншому. Якщо число, перетворене в систему числення base-4, містить лише 0 або 1. Тоді ми говоримо, що число існує в послідовності Moser-de Bruijn. Це не означає, що система числення base-4 містить лише 0 та 1 як цифри. Представлення Base-4 містить 0, 1, 2 і 3. Але якщо число існує в нашій послідовності. Потрібно дотримуватися деяких передумов, які повинні містити лише 0 або 1 у поданні base-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 масив, який залежить від вводу. Складність простору для задачі лінійна.