Рубрики

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

Учитывая число n, напишите функцию, которая генерирует и печатает все двоичные числа с десятичными значениями от 1 до n.

Примеры:

Input: n = 2
Output: 1, 10

Input: n = 5
Output: 1, 10, 11, 100, 101

Простой метод состоит в том, чтобы запустить цикл от 1 до n, вызвать десятичный к двоичному внутри цикла.

Ниже приведен интересный метод, который использует структуру данных очереди для печати двоичных чисел. Спасибо Vivek за предложенный подход.
1) Создать пустую очередь из строк
2) Поставьте в очередь первое двоичное число «1» в очередь.
3) Теперь запустите цикл для генерации и печати n двоичных чисел.
…… а) Снимите с очереди и распечатайте начало очереди.
…… б) Добавьте «0» в конце переднего элемента и поставьте его в очередь.
…… в) Добавьте «1» в конце передней части и поставьте в очередь.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для генерации двоичных чисел от 1 до n
#include <iostream>
#include <queue>

using namespace std;

  
// Эта функция использует структуру данных очереди для печати двоичных чисел

void generatePrintBinary(int n)

{

    // Создать пустую очередь строк

    queue<string> q;

  

    // ставим в очередь первое двоичное число

    q.push("1");

  

    // Этот цикл похож на BFS дерева с 1 в качестве корня

    // 0 как левый ребенок и 1 как правый ребенок и так далее

    while (n--)

    {

        // выводим начало очереди

        string s1 = q.front();

        q.pop();

        cout << s1 << "\n";

  

        string s2 = s1;  // Сохраняем s1 перед его изменением

    

        // Добавляем "0" к s1 и ставим его в очередь

        q.push(s1.append("0"));

  

        // Добавляем «1» к s2 и ставим его в очередь. Обратите внимание, что s2 содержит

        // предыдущий фронт

        q.push(s2.append("1"));

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 10;

    generatePrintBinary(n);

    return 0;

}

Джава

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

  

import java.util.LinkedList;

import java.util.Queue;

  

public class GenerateBNo 

{

    // Эта функция использует структуру данных очереди для печати двоичных чисел

    static void generatePrintBinary(int n)

    {

        // Создать пустую очередь строк

        Queue<String> q = new LinkedList<String>();

          

        // ставим в очередь первое двоичное число

        q.add("1");

          

        // Этот цикл похож на BFS дерева с 1 в качестве корня

        // 0 как левый ребенок и 1 как правый ребенок и так далее

        while(n-- > 0)

        {

            // выводим начало очереди

            String s1 = q.peek();

            q.remove();

            System.out.println(s1);

              

            // Сохраняем s1 перед его изменением

            String s2 = s1;

              

            // Добавляем "0" к s1 и ставим его в очередь

            q.add(s1 + "0");

              

            // Добавляем «1» к s2 и ставим его в очередь. Обратите внимание, что s2 содержит

            // предыдущий фронт

            q.add(s2 + "1");

        }

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int n=10;

        generatePrintBinary(n);

    }

}
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python для генерации двоичных чисел из
№ 1 до п

  
# Эта функция использует структуру данных очереди для печати двоичных чисел

def generatePrintBinary(n):

      

    # Создать пустую очередь

    from Queue import Queue

    q = Queue()

      

    # Поставить в очередь первое двоичное число

    q.put("1")

  

    # Этот цикл похож на BFS дерева с 1 в качестве корня

    # 0 как левый ребенок и 1 как правый ребенок и так далее

    while(n>0):

        n-= 1 

        # Распечатать начало очереди

        s1 = q.get() 

        print s1 

      

        s2 = s1 # Сохраните s1 перед его изменением

      

        # Добавить "0" к s1 и поставить его в очередь

        q.put(s1+"0")

  

        # Добавить "1" к s2 и поставить его в очередь. Обратите внимание, что s2

        # содержит предыдущий фронт

        q.put(s2+"1")

      

  
# Программа драйвера для проверки вышеуказанной функции

n = 10

generatePrintBinary(n)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для генерации двоичного файла
// числа от 1 до n

using System;

using System.Collections.Generic;

  

class GFG

{

    // Эта функция использует данные очереди

    // структура для печати двоичных чисел

    public static void generatePrintBinary(int n)

    {

        // Создать пустую очередь строк

        LinkedList<string> q = new LinkedList<string>();

  

        // ставим в очередь первое двоичное число

        q.AddLast("1");

  

        // Этот цикл похож на BFS дерева

        // с 1 в качестве корня 0 в качестве левого ребенка

        // и 1 как правильный ребенок и так далее

        while (n-- > 0)

        {

            // выводим начало очереди

            string s1 = q.First.Value;

            q.RemoveFirst();

            Console.WriteLine(s1);

  

            // Сохраняем s1 перед его изменением

            string s2 = s1;

  

            // Добавляем "0" к s1 и ставим его в очередь

            q.AddLast(s1 + "0");

  

            // Добавляем «1» к s2 и ставим его в очередь.

            // Обратите внимание, что s2 содержит предыдущий фронт

            q.AddLast(s2 + "1");

        }

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        int n = 10;

        generatePrintBinary(n);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

1
10
11
100
101
110
111
1000
1001
1010

Сложность времени: O (n * logn)
Эта статья предоставлена Abhishek . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes