ในปัญหานี้ เราได้รับตัวเลข A, B และ N สามตัว หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาพจน์ที่ N หารด้วย A หรือ B ใน C++ ลงตัว
คำอธิบายปัญหา
เทอมที่ N หารด้วย A หรือ B ในที่นี้ เราจะพบเทอม n ของตัวเลขที่หารด้วยหมายเลข A หรือ B ลงตัว สำหรับสิ่งนี้ เราจะนับจนถึงตัวเลขที่ n ที่หารด้วย A หรือ B ลงตัว
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
A =4, B =3, N =5
ผลลัพธ์
9
คำอธิบาย
พจน์ที่หารด้วย 3 และ 4 ลงตัวคือ −
3, 4, 6, 8, 9, 12, …
เทอมที่ 5 คือ 9.
แนวทางการแก้ปัญหา
ในการหาเทอมที่ n ที่หารด้วย A หรือ B ลงตัว เราสามารถหาตัวเลขที่หารด้วย A หรือ B ลงตัว และเทอมที่ n ในอนุกรมนี้คือคำตอบของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
int findNTerm(int N, int A, int B) {
int count = 0;
int num = 1;
while( count < N){
if(num%A == 0 || num%B == 0)
count++;
if(count == N)
return num;
num++;
}
return 0;
}
int main(){
int N = 12, A = 3, B = 4;
cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B)<<endl;
} ผลลัพธ์
12th term divisible by 3 or 4 is 24
อีกแนวทางหนึ่งในการแก้ปัญหาคือการใช้การค้นหาแบบไบนารีเพื่อค้นหาองค์ประกอบที่ N ซึ่งหารด้วย A หรือ B เราจะหาพจน์ที่ N โดยใช้สูตร−
NTerm =maxNum/A + maxNum/B + maxNum/lcm(A,B)
และจากค่าของ Nterm เราจะตรวจสอบว่าจำเป็นต้องข้ามผ่านตัวเลขที่น้อยกว่า maxNum หรือมากกว่า maxNum หรือไม่
ตัวอย่าง
#include <iostream>
using namespace std;
int findLCM(int a, int b) {
int LCM = a, i = 2;
while(LCM % b != 0) {
LCM = a*i;
i++;
}
return LCM;
}
int findNTerm(int N, int A, int B) {
int start = 1, end = (N*A*B), mid;
int LCM = findLCM(A, B);
while (start < end) {
mid = start + (end - start) / 2;
if ( ((mid/A) + (mid/B) - (mid/LCM)) < N)
start = mid + 1;
else
end = mid;
}
return start;
}
int main() {
int N = 12, A = 3, B = 4;
cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B);
} ผลลัพธ์
12th term divisible by 3 or 4 is 24
