Интересный метод генерации двоичных чисел от 1 до n


Сложный уровень средний
Часто спрашивают в Амазонка Белзабар Махиндра Комвива ServiceNow Wooker
Поиск в ширину Очередь

Постановка задачи

Задача «Интересный метод генерации двоичных чисел от 1 до n» гласит, что вам дано число n, выведите все числа от 1 до n в двоичная форма.

Примеры

3
1 10 11

 

6
1 10 11 100 101 110

Алгоритм

Генерацию двоичных чисел от 1 до n можно рассматривать как двоичное дерево, где 1 - корень дерева, и каждый узел имеет 2 дочерних элемента, левый дочерний элемент получается добавлением «0» в конец числа, а правый дочерний элемент получается добавлением «1» в конце числа. См. Изображение ниже.

Интересный метод генерации двоичных чисел от 1 до n

Чтобы сгенерировать первые n двоичных чисел, выполните обход порядка уровней дерево и выведите первые n узлов.

  1. Создайте очередь строки с именем q. Инициализируйте переменную total как 0.
  2. Поставьте «1» в очередь, то есть в корень дерева.
  3. Пока сумма меньше n, повторите шаги 4 и 5.
  4. Вытащить элемент из очередь, распечатайте его и поместите его левый дочерний элемент (элемент + «0») и правый дочерний элемент (элемент + «1») в очередь.
  5. Увеличить сумму на 1.

объяснение

Рассмотрим пример, когда нам нужно сгенерировать двоичное число от 1 до 6.

Сначала мы создаем дерево, как показано на изображении выше, корень дерева равен 1, и для каждого узла его левый дочерний элемент (значение узла + «0»), а правый дочерний элемент - (значение узла + «1»).

В дереве мы видим, что корень соответствует двоичному представлению десятичного числа 1. Левый дочерний элемент root является двоичным представлением 2, правый дочерний элемент root является двоичным представлением 3. Аналогично, левый узел « 2 - это двоичное представление числа 4, а правый узел числа «2» - двоичное представление числа 5 и так далее.

Итак, чтобы распечатать двоичное представление чисел от 1 до 6, все, что нам нужно сделать, это распечатать первые 6 узлов дерева, что можно сделать с помощью очереди, пройдя дерево в порядке уровней.

Следовательно, выход
1 10 11 100 101 110

Код:

Код Java для интересного метода генерации двоичных чисел от 1 до n

import java.util.LinkedList;
import java.util.Queue;

class AnInterestingMethodToGenerateBinaryNumbersFrom1ToN {
    private static void generateBinaryNumbers(int n) {
        if (n == 0) {
            return;
        }

        // create a queue of strings
        Queue<String> q = new LinkedList<>();
        // push the root to the queue
        q.add("1");

        // initialize total as 0
        int total = 0;

        // while total is less than n
        while (total < n) {
            // remove an element from queue and print it
            String curr = q.poll();
            System.out.print(curr + " ");
            // add the left and right child of curr to the queue
            q.add(curr + "0");
            q.add(curr + "1");
            // increment total
            total++;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        int n1 = 3;
        generateBinaryNumbers(n1);

        int n2 = 6;
        generateBinaryNumbers(n2);
    }
}
1 10 11 
1 10 11 100 101 110

Код на C ++ для интересного метода генерации двоичных чисел от 1 до n

#include<bits/stdc++.h> 
using namespace std; 

void generateBinaryNumbers(int n) {
    if (n == 0) {
        return;
    }
    
    // create a queue of strings
    queue<string> q;
    // push the root to the queue
    q.push("1");
    
    // initialize total as 0
    int total = 0;
    
    // while total is less than n
    while (total < n) {
        // remove an element from queue and print it
        string curr = q.front();
        q.pop();
        cout<<curr<<" ";
        // add the left and right child of curr to the queue
        q.push(curr + "0");
        q.push(curr + "1");
        // increment total
        total++;
    }
    
    cout<<endl;
}

int main() {
    int n1 = 3;
    generateBinaryNumbers(n1);
    
    int n2 = 6;
    generateBinaryNumbers(n2);
    
    return 0;
}
1 10 11 
1 10 11 100 101 110

Анализ сложности

Сложность времени

НА), поскольку мы только проходим элементы, пока не достигнем заданного целевого элемента. Таким образом, алгоритм линейен во времени.

Космическая сложность

НА), поскольку мы прошли через элементы, которые меньше целевого элемента. Мы помещаем эти элементы в очередь, поэтому сложность пространства также линейна.