Chúng tôi được cung cấp một số, giả sử là num và nhiệm vụ là tính toán số lượng các chuỗi nhị phân có thể được hình thành thông qua số num đã cho chỉ chứa o’s và 1’s.
Hệ thống số nhị phân là một loại kỹ thuật biểu diễn số. Nó phổ biến nhất và được sử dụng trong các hệ thống kỹ thuật số. Hệ thống nhị phân được sử dụng để biểu diễn các đại lượng nhị phân có thể được biểu diễn bằng bất kỳ thiết bị nào chỉ có hai trạng thái hoạt động hoặc các điều kiện có thể. Ví dụ, một công tắc chỉ có hai trạng thái:mở hoặc đóng.
Trong Hệ thống nhị phân, chỉ có hai ký hiệu hoặc các giá trị chữ số có thể có, tức là, 0 và 1. Được biểu thị bởi bất kỳ thiết bị nào chỉ có 2 trạng thái hoạt động hoặc các điều kiện có thể. Chuỗi nhị phân là những chuỗi có chứa các giá trị nhị phân, tức là 0 hoặc 1
Ví dụ
Input − num = 3 Output − count is 8
Giải thích - các kết hợp nhị phân có thể được tạo thành có độ dài 3 là:000, 111, 001,101, 100, 110, 011, 010 vì chúng có tổng là 8 trong các số do đó số đếm là 8.
Input − num = 2 Output − count is 4
Giải thích - các kết hợp nhị phân có thể được tạo thành với độ dài 2 là:00, 11, 01,10 vì chúng có tổng 4 trong các số do đó số lượng là 4.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một số kiểu với độ dài miễn là số đó có thể dài bất kỳ chữ số nào
-
Tính giá trị mod là (long long) (le9 + 7)
-
Tạo một hàm để tính toán số lượng
-
Khai báo một biến tạm thời sẽ lưu trữ số đếm và một biến khác tạm thời và khởi tạo nó bằng 2.
-
Đặt num là temp =temp% mod
-
Bắt đầu vòng lặp trong khi num> 0
-
Kiểm tra IF num &1 rồi đặt số lượng là (count * temp)% mod
-
Đặt num =num>> 1
-
Đặt temp =(temp * temp)% mod
-
Số lần trả lại
-
In kết quả.
Ví dụ
#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// An iterative function to find (x^y)%p in O(log y)
ll power(ll x, ll y, ll p){
ll result = 1;
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0){
// If y is odd, multiply x with result
if (y & 1){
result = (result * x) % p;
}
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return result;
}
// Function to count the number of binary strings
ll countbstring(ll num){
int count = power(2, num, mod);
return count;
}
int main(){
ll num = 3;
cout <<"count is: "<<countbstring(num);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is: 8