এই সমস্যায়, আমরা তিনটি পূর্ণসংখ্যা 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 − যোগফল =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