یک روش جالب برای تولید اعداد دودویی از 1 تا n


سطح دشواری متوسط
اغلب در آمازون بلزابار ماهیندرا کامویوا 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 را انجام دهید پیمایش سفارش سطح از درخت و گره های اول را چاپ کنید.

  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

رمز

جاوا کد به روشی جالب برای تولید اعداد دودویی از 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

تحلیل پیچیدگی

پیچیدگی زمان

بر)، از آنجا که ما فقط در حال عبور از عناصر هستیم تا زمانی که به عنصر مورد نظر خود برسیم. بنابراین الگوریتم از نظر زمان خطی است.

پیچیدگی فضا

بر)، همانطور که از عناصر کمتری از عنصر هدف عبور کرده ایم. ما این عناصر را به صف فشار می دهیم بنابراین پیچیدگی فضا نیز خطی است.