Cho một số nguyên N làm đầu vào. Mục đích là để tìm số lượng các số nguyên nhỏ hơn N và được biểu diễn dưới dạng Binary. Ví dụ:nếu đầu vào N là 12 thì các số nhỏ hơn 12 là 1,10,11 là hệ nhị phân và chứa các chữ số 0 và 1. Câu trả lời sẽ là 3.
Ví dụ
Đầu vào
N=100
Đầu ra
Count of Binary Digit numbers smaller than N are − 4
Giải thích
The Binary numbers less than 100 are − 1, 10, 11, 100
Đầu vào
N=120
Đầu ra
Count of Binary Digit numbers smaller than N are: 7
Giải thích
The Binary numbers less than 100 are : 1, 10, 11, 100, 101, 110, 111
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một vec vector số nguyên. Đối với điều này, đầu tiên chúng ta sẽ đẩy 1. Bây giờ để tạo số nhị phân tiếp theo, chúng ta sẽ trích xuất số cuối cùng (tạm thời) từ vec (Ban đầu là 1). Sau đó, tạo tiếp theo bằng cách sử dụng:temp * 10 và temp * 10 + 1 như các số nhị phân sẽ luôn là (1,10,11,100,110,111….). Số nổi bật từ vec và nếu nó nhỏ hơn N số lượng không tăng.
-
Lấy một số nguyên N làm đầu vào.
-
Hàm Smaller_N (int N) nhận N và trả về số lượng chữ số nhị phân nhỏ hơn N.
-
Lấy số lượng ban đầu là 0.
-
Lấy vec-tơ số nguyên để lưu trữ số nguyên chỉ chứa 0 và 1.
-
Thêm 1 vào vectơ bằng vec.push_back (1).
-
Sử dụng vòng lặp while, duyệt qua vec [] và lấy ra lần cuối được đẩy dưới dạng temp =vec.back (). Và xóa nó khỏi vec.
-
Nếu tạm thời <=N, thì số gia tăng và tạo số nguyên nhị phân tiếp theo dưới dạng tạm thời * 10 và tạm thời * 10 + 1 và thêm vào vec.
-
Kết quả là ở cuối thời gian trả về.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of Binary Digit numbers smaller than N are: 8