1 සිට n දක්වා ද්විමය සංඛ්‍යා උත්පාදනය කිරීමට සිත්ගන්නා ක්‍රමයක්  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් බෙල්සබාර් මහින්ද්‍රා කොම්විවා සර්විස්නව් වෝකර්
පළල පළමු සෙවීම පෝලිමේ

ගැටළු ප්රකාශය  

“ද්විමය සංඛ්‍යා 1 සිට n දක්වා ජනනය කිරීමට සිත්ගන්නා ක්‍රමයක්” යන ගැටලුවේ සඳහන් වන්නේ ඔබට අංකයක් ලබා දී ඇති බවත්, 1 සිට n දක්වා සියලු අංක මුද්‍රණය කරන බවත්ය ද්විමය ස්වරූපය.

උදාහරණ  

3
1 10 11

 

6
1 10 11 100 101 110

ඇල්ගොරිතම  

1 සිට n දක්වා ද්විමය සංඛ්‍යා උත්පාදනය ද්විමය ගසක් ලෙස දැකිය හැකි අතර, එහිදී ගසෙහි මුල 1 වන අතර සෑම නෝඩයකම දරුවන් දෙදෙනෙකු සිටින අතර, වම් දරුවා ලබා ගන්නේ අංකයේ අවසානයේ '2' එකතු කිරීමෙන් දකුණු දරුවා අංක අවසානයේ '0' එකතු කිරීමෙන් ලබා ගනී. පහත රූපය බලන්න.

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 හි ද්විමය නිරූපණය වේ.

එබැවින් 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

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

මත), අප ලබා දී ඇති ඉලක්කගත මූලද්‍රව්‍යය කරා ළඟා වන තෙක් අපි මූලද්‍රව්‍ය හරහා ගමන් කරන බැවින්. මේ අනුව ඇල්ගොරිතම කාලයාගේ ඇවෑමෙන් රේඛීය වේ.

මෙයද බලන්න
පළමු ධනාත්මක අතුරුදහන්

අභ්‍යවකාශ සංකීර්ණතාව

මත), ඉලක්කගත මූලද්‍රව්‍යයට වඩා අඩු මූලද්‍රව්‍ය හරහා අප ගමන් කර ඇති බැවින්. අප මෙම මූලද්‍රව්‍යයන් පෝලිමට තල්ලු කරමින් සිටින අතර අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.