Genera numeri binari utilizzando una coda

Problema

Genera numeri binari da 1 a qualsiasi numero dato, "n", utilizzando una coda.

Firma funzione

List<string> GenerateBinaryNumber(int n)

Esempio di input e output

n =1 => (1)

n =3 => ( 1, 10, 11)

Strategia per la risoluzione dei problemi

Supponendo che tu non abbia mai riscontrato questo problema prima e non abbia molta esperienza nell'uso di stack e code, prova a scoprire uno schema. Il primo passo per scoprire un modello è annotare alcuni input e output di esempio.

Decimale :1        2         3        4          5

Binario :    1       10       11     1000      101

Se noti attentamente, vedrai che 2 è formato aggiungendo uno "0" al numero precedente, "1". E 3 è formato aggiungendo un "1" al numero precedente precedente, 1. Allo stesso modo, 4 è formato aggiungendo uno "0" a 2 ("10") e 5 è formato aggiungendo un "1" a 2.

Quindi potrebbe essere che se continuiamo ad aggiungere uno "0" e "1" al numero binario precedentemente generato, possiamo creare questo modello? Sì ! Visualizziamo come funzionerà con una coda.

Visualizza la soluzione

Useremo una coda per generare i numeri e un elenco (o array) per memorizzare i risultati.

Quindi, dopo aver elaborato un esempio grafico, sembra che funzionerà, quindi formalizziamo l'algoritmo

Algoritmo

1. Crea una coda vuota:verrà utilizzata per generare i numeri binari
2. Crea un elenco/matrice vuoto:questo verrà utilizzato per contenere i risultati, ovvero l'elenco dei numeri binari generati fino a n
3. Metti in coda "1" in coda
4. Genera i numeri binari all'interno di un ciclo che viene eseguito finché "n" numeri binari non sono stati aggiunti all'elenco. Ecco cosa succede all'interno del loop:
   • Rimuovi un elemento dalla coda:chiama questa "X"
   • Genera i prossimi due  numeri binari aggiungendo rispettivamente "0" e "1" a "X". I due nuovi numeri binari così generati sono “X0” e “X1”
   • Accedi "X0" e "X1" nella coda
   • Aggiungi "X" all'elenco dei risultati

Nota:una volta aggiunti "n" elementi all'elenco, il ciclo termina. A questo punto, potrebbero esserci più elementi rimasti nella coda che non verranno aggiunti all'elenco dei risultati (poiché abbiamo bisogno solo di n elementi). Ma va bene.

Implementazione C#

using System;
using System.Collections.Generic;

namespace StacksNQueues
{
    public class GenerateBinaryNumbers
    {
        public static List<string> GenerateBinaryNumber(int n)
        {
            Queue<string> binaryGenerationQueue = new Queue<string>();
            List<string> results = new List<string>();

            binaryGenerationQueue.Enqueue("1");
            
            while(n!=0)
            {
                string current = binaryGenerationQueue.Dequeue();
                results.Add(current);

                string appendZero = current + "0";
                string appendOne = current + "1";

                binaryGenerationQueue.Enqueue(appendZero);
                binaryGenerationQueue.Enqueue(appendOne);

                n--;
            }
            return results;
        }
    }
}

Ed ecco il programma di test

using System;
using System.Collections.Generic;

namespace StacksNQueues
{
    class Program
    {
        static void Main(string[] args)
        {
            // test generate binary numbers using a queue
            List<string> testbinary0 = GenerateBinaryNumbers.GenerateBinaryNumber(0);
            List<string> testbinary1 = GenerateBinaryNumbers.GenerateBinaryNumber(1);
            List<string> testbinary3 = GenerateBinaryNumbers.GenerateBinaryNumber(3);
            List<string> testbinary5 = GenerateBinaryNumbers.GenerateBinaryNumber(5);
        }
    }
}

Analisi della complessità

Complessità di runtime : O(n) poiché eseguiamo il ciclo solo finché non abbiamo generato n numeri e il tempo di esecuzione aumenta in modo lineare man mano che n diventa più grande

Complessità spaziale: O(2n) =O(n) perché utilizziamo una coda e un List/Array per elaborare e conservare i risultati