Trong bài toán này, chúng ta đã cho ba số nguyên M1, M2 và N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng bội của hai số dưới N.
Ở đây, chúng tôi sẽ thêm tất cả các phần tử bên dưới N là bội số của M1 hoặc M2
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 13, M1 = 4, M2 = 6
Đầu ra
20
Giải thích - Số là bội của 4 và 6 nhỏ hơn 13 là 4, 6, 8, 12.
Một giải pháp đơn giản cho vấn đề là lặp lại từ 1 đến N và thêm tất cả các giá trị có thể chia cho M1 hoặc M2.
Thuật toán
Bước 1 - sum =0, i =0. Vòng lặp từ i =1 đến N.
Bước 1.1 - if (i% M1 ==0) hoặc (i% M2 ==0), sum + =i
Bước 2 - Trả lại số tiền.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <iostream<
using namespace std;
int calcMulSum(int N, int M1, int M2){
int sum = 0;
for (int i = 0; i < N; i++)
if (i%M1 == 0 || i%M2 == 0)
sum += i;
return sum;
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
} Đầu ra
The sum of multiples of 4 and 7 below 24 is 102
Đây không phải là giải pháp tốt nhất cho vấn đề của chúng tôi vì nó có độ phức tạp lên đến O (n) thời gian.
Giải pháp tốt hơn sẽ là sử dụng các công thức toán học cho tổng của chuỗi.
Ở đây, chúng tôi sẽ sử dụng công thức cho tổng của chuỗi. Tổng cuối cùng sẽ là (bội số của M1 + bội số của M2 - bội số của M1 * M2)
Tổng của bội số x tối đa n số hạng được cho bởi,
Sum(X) = (n * (1+n) * X)/2
Hãy lập công thức tính tổng,
sum = ( ( ((n/M1)*(1+(n/M1))*M1)/2) + ((n/M2)*(1+(n/M2))*M2)/2 ) - ((n/M1*M2)*(1+(n/M1*M2))*M1*M2)/2 ) )
Ví dụ
Chương trình minh họa giải pháp,
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2){
N--;
return (((N/M1) * (1 + (N/M1)) * M1 / 2) + ((N/M2) * (1 + (N/M2)) * M2 / 2) - ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
} Đầu ra
The sum of multiples of 4 and 7 below 24 is 102