นับจำนวนเลขฐานสองที่น้อยกว่า N ด้วย C++

ได้รับจำนวนเต็ม N เป็นอินพุต เป้าหมายคือการหาจำนวนจำนวนเต็มที่น้อยกว่า N และแสดงในรูปแบบฐานสอง (binary) ตัวอย่างเช่น หาก N = 12 จำนวนที่น้อยกว่า 12 และเป็นเลขฐานสองคือ 1, 10, 11 รวม 3 จำนวน

ตัวอย่าง

Input

N=100

Output

Count of Binary Digit numbers smaller than N are: 4

Explanation

The Binary numbers less than 100 are: 1, 10, 11, 100

Input

N=120

Output

Count of Binary Digit numbers smaller than N are: 7

Explanation

The Binary numbers less than 100 are: 1, 10, 11, 100, 101, 110, 111

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้เวกเตอร์จำนวนเต็ม vec เริ่มต้นเพิ่ม 1 เข้าไป ในการสร้างเลขฐานสองตัวถัดไป จะนำตัวเลขสุดท้าย (temp) จาก vec (เริ่มต้นเป็น 1) แล้วสร้างตัวถัดไปโดย temp*10 และ temp*10+1 เนื่องจากเลขฐานสองจะเป็นลำดับ (1, 10, 11, 100, 110, 111...) นำตัวเลขออกจาก vec และถ้าน้อยกว่าหรือเท่ากับ N ให้เพิ่มจำนวนนับ

• รับจำนวนเต็ม N เป็นอินพุต
• ฟังก์ชัน Smaller_N(int N) รับ N คืนค่าจำนวนเลขฐานสองที่น้อยกว่า N
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• สร้างเวกเตอร์ vec สำหรับเก็บจำนวนเต็มที่ประกอบด้วย 0 และ 1 เท่านั้น
• เพิ่ม 1 เข้าไปในเวกเตอร์ด้วย vec.push_back(1)
• ใช้ while loop วนลูปผ่าน vec นำตัวสุดท้ายออกมาเป็น temp = vec.back() แล้วลบออกจาก vec
• ถ้า temp <= N ให้เพิ่มจำนวนนับ และสร้างเลขฐานสองต่อไป temp*10 และ temp*10+1 เพิ่มเข้า vec
• เมื่อลูปสิ้นสุด คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int Smaller_N(int N){
    int count = 0;
    vector<int> vec;
    vec.push_back(1);
    while (!vec.empty()){
        int temp = vec.back();
        vec.pop_back();
        if (temp <= N){
            count++;
            int temp_2 = temp * 10;
            vec.push_back(temp_2);
            vec.push_back(temp_2 + 1);
        }
    }
    return count;
}

int main(){
    int N = 1000;
    cout << "Count of Binary Digit numbers smaller than N are: " << Smaller_N(N);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of Binary Digit numbers smaller than N are: 8