Trong bài toán này, chúng ta có ba số A, B và N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm số hạng thứ N chia hết cho A hoặc B trong C ++.
Mô tả vấn đề
Số hạng thứ N chia hết cho A hoặc B. Ở đây, chúng ta sẽ tìm số hạng thứ n chia hết cho số A hoặc B. Vì vậy, chúng ta sẽ đếm đến số thứ n chia hết cho A hoặc B.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
A =4, B =3, N =5
Đầu ra
9
Giải thích
Các số hạng chia hết cho 3 và 4 là -
3, 4, 6, 8, 9, 12,…
Số hạng thứ 5 là 9.
Phương pháp tiếp cận giải pháp
Để tìm số hạng thứ n chia hết cho A hoặc B. Chúng ta chỉ cần tìm các số chia hết cho A hoặc B và số hạng thứ n trong dãy là câu trả lời của chúng ta.
Ví dụ
#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;
} Đầu ra
12th term divisible by 3 or 4 is 24
Một cách tiếp cận khác để giải quyết vấn đề có thể là sử dụng tìm kiếm Nhị phân để tìm phần tử thứ N chia hết cho A hoặc B. Chúng ta sẽ tìm số hạng thứ N bằng công thức−
NTerm =maxNum / A + maxNum / B + maxNum / lcm (A, B)
Và dựa trên giá trị của Nterm, chúng tôi sẽ kiểm tra xem chúng tôi có cần duyệt các số nhỏ hơn maxNum hay lớn hơn maxNum hay không.
Ví dụ
#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);
} Đầu ra
12th term divisible by 3 or 4 is 24