เราจะได้เลขจำนวนเต็ม สมมุติว่า N ซึ่งถือเป็นตัวหารและจะหารด้วยตัวเลขที่เริ่มตั้งแต่ 1 - N และงานคือการคำนวณหาตัวหารที่มีจำนวน set bit มากกว่า ผลหารเมื่อหารด้วยจำนวนที่กำหนด N.
ตัวอย่าง
ป้อนข้อมูล - int N =6
ผลลัพธ์ - จำนวนตัวหารที่มีเซตบิตมากกว่าผลหารในการหาร N คือ:5
คำอธิบาย - ประการแรก เราจะหารตัวเลข N ด้วยตัวเลขที่เริ่มต้นจาก 1 - N และคำนวณชุดบิตของตัวหารและผลหารเช่น
1-> N =6 /1(1) =6(2) =1 <2 =ไม่พิจารณา
2-> N =6 /2(1) =3(2) =2 =2 =พิจารณา
3-> N =6 /3(2) =2(1) =2> 1 =พิจารณา
4-> N =6 /4(1) =1(1) =1 =1 =พิจารณา
5-> N =6 /5(2) =1(1) =2> 1 =พิจารณา
6-> N =6 /6(2) =1(1) =2>1 =พิจารณา
อย่างที่เห็น เราจะพิจารณาคดีและผลลัพธ์จะเป็น 5.
ป้อนข้อมูล - int N =10
ผลลัพธ์ - จำนวนตัวหารที่มีเซตบิตมากกว่าผลหารในการหาร N คือ:8
คำอธิบาย - ประการแรก เราจะหารตัวเลข N ด้วยตัวเลขที่เริ่มต้นจาก 1 - N และคำนวณชุดบิตของตัวหารและผลหารเช่น
1-> N =10 /1(1) =10(2) =1 <2 =ไม่พิจารณา
2-> N =10 /2(1) =5(2) =2 =2 =พิจารณา
3-> N =10 /3(2) =3(2) =2 =2 =พิจารณา
4-> N =10 /4(1) =2(1) =1 <2 =ไม่พิจารณา
5-> N =10 /5(2) =2(1) =2> 2 =พิจารณา
6-> N =10 /6(2) =1(1) =2>1 =พิจารณา
7-> N =10 /7(3) =1(1) =3>1 =พิจารณา
8-> N =10 /8(1) =1(1) =1 =1 =พิจารณา
9-> N =10 /9(2) =1(1) =2> 2 =พิจารณา
10-> N =10 /10(2) =1(1) =2> 1 =พิจารณา
อย่างที่เห็น เราจะพิจารณาคดีและผลลัพธ์จะเป็น 8
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- ป้อนจำนวนเต็มบวก N และส่งไปยังฟังก์ชัน divisors_quotient() เป็นอาร์กิวเมนต์
- ภายในฟังก์ชัน divisors_quotient()
- คืนค่าการเรียก N - ไปที่ฟังก์ชัน set_quo(N) + 1 และไปที่ฟังก์ชัน set_quo()
- ภายในฟังก์ชัน set_quo()
- สร้างตัวแปรชั่วคราวเป็น start และ end และเริ่มต้นการเริ่มต้นด้วย 1 และสิ้นสุดด้วย sqrt(N)
- เริ่มวนรอบในขณะที่เริ่ม
- ตรวจสอบ IF(เรียกใช้ฟังก์ชัน Verify() และส่ง temp และ N เป็นอาร์กิวเมนต์) จากนั้นตั้งค่า end เป็น temp
- ELSE ตั้งค่า start เป็น temp + 1
- IF(!call ไปที่ฟังก์ชัน Verify() และส่งค่า temp และ N เป็นอาร์กิวเมนต์) จากนั้นให้คืนค่า start + 1
- ELSE เริ่มกลับ
- ภายในฟังก์ชัน Verify()
- ตรวจสอบว่า IF(การเรียกใช้ฟังก์ชัน val_bit(temp/val) น้อยกว่าการเรียกใช้ฟังก์ชัน val_bit(val)) แล้วคืนค่า true มิฉะนั้นจะคืนค่า False
- ภายในฟังก์ชัน val_bit()
- ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บผลลัพธ์
- เริ่มวนรอบในขณะที่ val มีค่า ภายในลูป ตั้งค่า val เป็น val / 2 และเพิ่มจำนวนขึ้น 1
- นับคืน.
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int val_bit(int val) {
int count = 0;
while (val) {
val = val / 2;
count++;
}
return count;
}
bool verify(int val, int temp) {
if (val_bit(temp / val) <= val_bit(val)) {
return true;
}
return false;
}
int set_quo(int N) {
int start = 1;
int end = sqrt(N);
while (start < end) {
int temp = (start + end) / 2;
if (verify(temp, N)) {
end = temp;
} else {
start = temp + 1;
}
}
if (!verify(start, N)) {
return start + 1;
} else {
return start;
}
}
int divisors_quotient(int N) {
return N - set_quo(N) + 1;
}
int main() {
int N = 10;
cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
return 0;
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of divisors having more set bits than quotient on dividing N are: 8
