የሁለትዮሽ ቁጥሮችን ከ 1 ወደ n ለማመንጨት አስደሳች ዘዴ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ቤልዛባር ማሂንድራ ኮምቪቫ አገልግሎቱ 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 የሁለትዮሽ ቁጥሮች ለማመንጨት ሀ ደረጃ ማዘዋወር የእርሱ ዛፍ እና የመጀመሪያዎቹን አንጓዎች ያትሙ።

  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 እና ወዘተ የሁለትዮሽ ውክልና ነው ፡፡

ስለዚህ ከ 1 እስከ 6 ያሉትን ቁጥሮች የሁለትዮሽ ውክልና ለማተም እኛ ማድረግ ያለብን የዛፉን የመጀመሪያዎቹ 6 አንጓዎች ማተም ብቻ ነው ፣ ዛፉን በደረጃ ቅደም ተከተል በማለፍ ወረፋ በመጠቀም ሊከናወን ይችላል ፡፡

ስለሆነም ውፅዓት ነው
1 10 11 100 101 110

ኮድ

ባለ ሁለትዮሽ ቁጥሮችን ከ 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

ባለ ሁለትዮሽ ቁጥሮችን ከ 1 ወደ n ለማመንጨት C ++ ኮድ ወደ አንድ አስደሳች ዘዴ

#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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ የተሰጠንን ዒላማ አካል እስክንደርስ ድረስ ንጥረ ነገሮችን ብቻ እየተጓዝን ስለሆነ ፡፡ ስለዚህ አልጎሪዝም በጊዜ ሂደት መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ከዒላማው ንጥረ ነገር ባነሰ ንጥረ ነገሮች ውስጥ እንዳለፍን ፡፡ እነዚህን አካላት ወደ ወረፋው እየገፋፋቸው ስለነበረ የቦታ ውስብስብነቱ እንዲሁ ቀጥተኛ ነው ፡፡