ในปัญหานี้ เราได้กำหนดจำนวนเต็ม M1, M2 และ N สามจำนวน หน้าที่ของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของทวีคูณของตัวเลขสองตัวที่ต่ำกว่า N
ในที่นี้ เราจะเพิ่มองค์ประกอบทั้งหมดด้านล่าง N ซึ่งเป็นผลคูณของ M1 หรือ M2
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
N = 13, M1 = 4, M2 = 6
ผลผลิต
20
คำอธิบาย − จำนวนที่เป็นทวีคูณของ 4 และ 6 ที่น้อยกว่า 13 คือ 4, 6, 8, 12
วิธีแก้ปัญหาง่ายๆ คือการวนซ้ำจาก 1 ถึง N และเพิ่มค่าทั้งหมดที่สามารถหารด้วย M1 หรือ M2 ได้
อัลกอริทึม
ขั้นตอนที่ 1 − sum =0 , i =0. วนรอบจาก i =1 ถึง N.
ขั้นตอนที่ 1.1 − ถ้า (i%M1 ==0) หรือ (i%M2 ==0) ผลรวม + =i
ขั้นตอนที่ 2 − ผลตอบแทนรวม
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The sum of multiples of 4 and 7 below 24 is 102
นี่ไม่ใช่ทางออกที่ดีที่สุดสำหรับปัญหาของเรา เนื่องจากต้องใช้เวลา O(n) ความซับซ้อน
ทางออกที่ดีกว่าคือการใช้สูตรทางคณิตศาสตร์สำหรับผลรวมของอนุกรม
ในที่นี้เราจะใช้สูตรสำหรับผลรวมของอนุกรม ผลรวมสุดท้ายจะเป็น (ทวีคูณของ M1 + ทวีคูณของ M2 - ทวีคูณของ M1*M2)
ผลรวมของจำนวนทวีคูณของ x ไม่เกิน n เงื่อนไขถูกกำหนดโดย
Sum(X) = (n * (1+n) * X)/2
มาคำนวณผลรวมกันเถอะ
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 ) )
ตัวอย่าง
โปรแกรมเพื่อแสดงวิธีแก้ปัญหา
#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;
} ผลลัพธ์
The sum of multiples of 4 and 7 below 24 is 102
