เราได้รับจำนวนเต็มบวก N เป้าหมายคือการนับตัวเลขที่น้อยกว่าหรือเท่ากับ N ที่มี 1 ทั้งหมดในการแทนค่าไบนารี ตัวอย่างเช่น 1 คือ 1, 3 คือ 11, 7 คือ 111, 15 คือ 1111... เป็นต้น
ถ้าเราเห็นตัวเลข แสดงว่าทั้งหมดเป็น 2i-1 โดยเริ่มจาก 1. ให้ตรวจสอบตัวเลขดังกล่าวให้น้อยกว่า n เราจะเปรียบเทียบว่า 2i-1<=n. แล้วนับเพิ่ม
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − N=15
ผลผลิต − จำนวนที่มี 1 ทั้งหมดเป็นเลขฐานสอง :4
คำอธิบาย − ตัวเลขเป็นผลรวมของจำนวนเฉพาะเดียวกัน − ตัวเลขจะเป็น 1 3 7 15
ป้อนข้อมูล − N=50
ผลผลิต − จำนวนที่มี 1 ทั้งหมดเป็นเลขฐานสอง :5
คำอธิบาย − ตัวเลขเป็นผลรวมของจำนวนเฉพาะเดียวกัน −
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราหาจำนวนเต็มบวก N..
-
ฟังก์ชัน allOnes(int n) รับ n เป็นอินพุตและส่งกลับตัวเลขที่มี 1 ทั้งหมดในรูปแบบไบนารี
-
ใช้ตัวแปรเริ่มต้นนับเป็น 0 สำหรับตัวเลขดังกล่าว..
-
ข้ามจาก i=1 ไปยัง i<=n โดยใช้ for loop.
-
สำหรับแต่ละ i ถ้า pow(2,i)-1 น้อยกว่าหรือเท่ากับ n จำนวนที่เพิ่มขึ้น
-
คืนค่าการนับเป็นผลเมื่อสิ้นสุดลูป for
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int allOnes(int n){
int count = 0;
for(int i=1;i<=n;i++){
if(n>=pow(2,i)-1){
count++;
//cout<<" "<<pow(2,i)-1;
}
}
return count;
}
int main(){
int N=23;
cout <<endl<< "Number having all 1's in binary : "<<allOnes(N);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Number having all 1's in binary : 4
