Усули ҷолиб барои тавлиди Ададҳои дуӣ аз 1 то n


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Белзабар Маҳиндра Комвива ServiceNow Вукер
Ҷустуҷӯи аввалини васеъ навбат

Изҳороти мушкилот

Масъалаи "Усули ҷолиб барои тавлиди рақамҳои дуӣ аз 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 ададҳои дуӣ, a гардиши фармоишӣ ба дарахт ва аввал n гиреҳро чоп кунед.

  1. Навбати сатрро бо номи q созед. Як миқдори тағирёбандаро ҳамчун 0 оғоз кунед.
  2. "1" -ро ба навбат тела диҳед, яъне решаи дарахт.
  3. Дар ҳоле, ки маҷмӯъ аз n камтар аст, қадами 4 ва 5 -ро такрор кунед.
  4. Элементро аз навбат, онро чоп кунед ва фарзанди чапашро (унсур + "0") ва фарзанди ростро (унсур + "1") ба навбат тела диҳед.
  5. Ҷамъ афзоиши 1.

Шарҳ

Мисолеро дида мебароем, ки мо бояд рақами дуӣ аз 1 то 6 -ро тавлид кунем.

Аввал мо дарахтро тавре месозем, ки дар тасвири боло нишон дода шудааст, решаи дарахт 1 мебошад ва барои ҳар як гиреҳ фарзанди чапи он (арзиши гиреҳ + "0") ва кӯдаки рост (арзиши гиреҳ + "1") мебошад.

Дар дарахт мо мебинем, ки реша ба нишондиҳии дуии даҳии 1 мувофиқат мекунад. Кӯдаки чапи реша намояндагии дуии 2, фарзанди рости реша намояндагии дуии 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 ++ Code ба усули ҷолиб барои тавлиди Ададҳои дуӣ аз 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо танҳо унсурҳоро тай карда, то ба унсури мақсадноки худ нарасем. Ҳамин тариқ, алгоритм дар вақти хатӣ мебошад.

Мураккабии фазо

O (N), чунон ки мо ба воситаи унсурҳое гузаштем, ки аз унсури ҳадаф камтаранд. Мо ин унсурҳоро ба навбат меандохтем, аз ин рӯ мураккабии фазо низ хаттӣ аст.