เรามีจำนวน N และฐาน b ในโปรแกรมนี้เราต้องตรวจสอบว่าตัวเลขขึ้นต้นด้วย 1 ในฐาน b หรือไม่ สมมุติว่าให้เลข 6 ในไบนารีนี้คือ 110 ดังนั้นมันเริ่มต้นด้วย 1 ในฐาน 4 มันจะเป็น 124 . นอกจากนี้ยังเริ่มต้นด้วย 1
อย่างที่เราทราบ หากแสดงตัวเลข N ในฐาน b แล้ว b จะถูกแปลงเป็นลำดับบิต m+1 bm bm-1 … b0 นี่หมายความว่า bm ข ม + bm-1 * b m-1 + … + b0 *b 0 =N. จำนวนที่มากที่สุดจะเป็น 2*b m – 1. N อยู่ใน b m ≤ N ≤ 2*b ม. – 1. อีกอย่างที่ควรสังเกตคือ m ไม่เกิน $\lfloor\log_2 m\;\rfloor$ นั่นเป็นเพราะเมื่อเราแทนตัวเลขใดๆ ในฐาน-2 มันจะถูกแปลงเป็นลำดับเพียง 0s และ 1s ดังนั้น ความยาวของลำดับนี้จะมากกว่าการแสดงฐานอื่น ๆ เสมอ และความยาวของมันจะเท่ากับ$\lfloor\log_2 m\;\rfloor+1$ ดังนั้นในการตรวจสอบจำนวนที่กำหนด N เริ่มต้นด้วย 1 ในฐาน b หรือไม่ เราจะสำรวจจาก m =1 ถึง m =$\lfloor\log_2 m\;\rfloor$ และตรวจสอบว่ามีค่าของ m หรือไม่ N อยู่ใน ช่วง b m ≤ N ≤ 2*b ม. – 1 หรือไม่ แล้วคืนค่าตามจริงหรือเท็จ
ตัวอย่าง
#include <iostream>
#include <cmath>
using namespace std;
bool isStartWithOne(int number, int base) {
int m = log2(number);
for (int i = 1; i <= m; i++) {
if (number >= pow(base, i) && number <= 2 * pow(base, i) - 1) //if number is in the given range
return true;
}
return false;
}
int main() {
int num = 19, base = 16;
if(isStartWithOne(num, base)){
cout << "Can be represented";
}else{
cout << "Can not be represented";
}
} ผลลัพธ์
Can be represented
