เราได้รับตัวเลข สมมติว่า num และภารกิจคือการคำนวณจำนวนสตริงไบนารีที่สามารถเกิดขึ้นได้จากตัวเลข num ที่ให้มีเพียง o และ 1 เท่านั้น
ระบบเลขฐานสองเป็นเทคนิคการแทนตัวเลขชนิดหนึ่ง เป็นที่นิยมและใช้งานในระบบดิจิทัลมากที่สุด ระบบไบนารีใช้สำหรับแสดงปริมาณไบนารีซึ่งสามารถแสดงโดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียงสองสถานะหรือเงื่อนไขที่เป็นไปได้ ตัวอย่างเช่น สวิตช์มีเพียงสองสถานะ:เปิดหรือปิด
ในระบบไบนารี มีเพียงสองสัญลักษณ์หรือค่าตัวเลขที่เป็นไปได้ นั่นคือ 0 และ 1 ที่แสดงโดยอุปกรณ์ใดๆ ที่มีสถานะการทำงานเพียง 2 สถานะหรือเงื่อนไขที่เป็นไปได้ สตริงไบนารีคือสตริงที่มีค่าไบนารีเช่น 0 หรือ 1
ตัวอย่าง
Input − num = 3 Output − count is 8
คำอธิบาย − ชุดค่าผสมไบนารีที่มีความยาว 3 ได้คือ:000, 111, 001,101, 100, 110, 011, 010 เนื่องจากเป็นตัวเลขทั้งหมด 8 ตัว จึงนับเป็น 8
Input − num = 2 Output − count is 4
คำอธิบาย − ชุดค่าผสมไบนารีที่มีความยาว 2 ได้คือ:00, 11, 01,10 เนื่องจากเป็นตัวเลขทั้งหมด 4 ตัว จึงนับเป็น 4
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ป้อนตัวเลขแบบยาวเนื่องจากตัวเลขสามารถเป็นตัวเลขยาวได้
-
คำนวณค่า mod เป็น (long long)(le9 + 7)
-
สร้างฟังก์ชันคำนวณการนับ
-
ประกาศตัวแปรชั่วคราวที่จะเก็บการนับและตัวแปรชั่วคราวอื่น และเริ่มต้นด้วย 2
-
ตั้งค่า num เป็น temp =temp % mod
-
เริ่มวนซ้ำในขณะที่ num> 0
-
ตรวจสอบ IF num &1 แล้วตั้งค่า count as (count * temp)% mod
-
ตั้งค่า num =num>> 1
-
ตั้งค่าอุณหภูมิ =(อุณหภูมิ * อุณหภูมิ) % mod
-
จำนวนคืน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
count is: 8
