এই সমস্যায়, আমাদের একটি সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল C++-এ সন্নিহিত উপাদানগুলির পার্থক্যের সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমরা সমস্ত পারমুটেশন অ্যারেগুলির সন্নিহিত উপাদানগুলির মধ্যে পরম পার্থক্যের সর্বাধিক যোগফল খুঁজে পাব৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 4
আউটপুট
7
ব্যাখ্যা
All permutations of size 4 are :
{1, 2, 3, 4} = 1 + 1 + 1 = 3
{1, 2, 4, 3} = 1 + 2 + 1 = 4
{1, 3, 2, 4} = 2 + 1 + 2 = 5
{1, 3, 4, 2} = 2 + 1 + 2 = 5
{1, 4, 2, 3} = 3 + 2 + 1 = 6
{1, 4, 3, 2} = 3 + 1 + 1 = 5
{2, 1, 3, 4} = 1 + 2 + 1 = 4
{2, 1, 4, 3} = 1 + 3 + 1 = 5
{2, 3, 1, 4} = 1 + 2 + 3 = 6
{2, 3, 4, 1} = 1 + 1 + 3 = 5
{2, 4, 1, 3} = 2 + 3 + 2 = 7
{2, 4, 3, 1} = 2 + 1 + 2 = 5
{3, 1, 2, 4} = 2 + 1 + 2 = 5
{3, 1, 4, 2} = 2 + 3 + 2 = 7
{3, 2, 1, 4} = 1 + 1 + 3 = 5
{3, 2, 4, 1} = 1 + 2 + 3 = 6
{3, 4, 1, 2} = 1 + 3 + 1 = 5
{3, 4, 2, 1} = 1 + 2 + 1 = 4
{4, 1, 2, 3} = 3 + 1 + 1 = 5
{4, 1, 3, 2} = 3 + 2 + 1 = 6
{4, 2, 1, 3} = 2 + 1 + 2 = 5
{4, 2, 3, 1} = 2 + 1 + 2 = 5
{4, 3, 1, 2} = 1 + 2 + 1 = 4
{4, 3, 2, 1} = 1 + 1 + 1 = 3 সমাধান পদ্ধতি
এই ধরনের সমস্যা সমাধানের জন্য, আমাদেরকে পারমুটেশনের সাধারণ যোগফল খুঁজে বের করতে হবে।
এখানে, N-এর বিভিন্ন মানের জন্য সন্নিহিত উপাদানগুলির পার্থক্যের সর্বাধিক যোগফলের কিছু মান রয়েছে।
N = 2, maxSum = 1 N = 3, maxSum = 3 N = 4, maxSum = 7 N = 5, maxSum = 11 N = 6, maxSum = 17 N = 7, maxSum = 23 N = 8, maxSum = 31
এই যোগফলটি N + N পদের যোগফল
এর উপর নির্ভরশীল একটি যোগের মত দেখাচ্ছেmaxSum =S(N) + F(N) S(N) =n(n-1)/2, এবং F(N) হল N
এর একটি অজানা ফাংশনS(N), maxSum(N) ব্যবহার করে F(N) খুঁজে বের করা যাক।
F(2) = 0 F(3) = 0 F(4) = 1 F(5) = 1 F(6) = 2 F(7) = 2 F(8) = 3
এখান থেকে, আমরা জানতে পারি যে F(N) হল Int(N/2 - 1)। F(N) N এর প্রতি সেকেন্ড মানের জন্য বৃদ্ধি পায় এবং প্রাথমিকভাবে 2 এবং 3 এর জন্য এটি শূন্য হয়।
এটি maxSum,
এর জন্য সূত্র তৈরি করেmaxSum = N(N-1)/2 + N/2 - 1 maxSum = N(N-1)/2 + N/2 - 2/2 maxSum = ( N(N-1) + N - 2 )/2 maxSum = ( (N^2) - N + N - 2 )/2 maxSum = ((N^2) - 2 )/2
এই সূত্রটি ব্যবহার করে, আমরা N.
এর যেকোনো প্রদত্ত মানের সর্বাধিকসম মান খুঁজে পেতে পারিউদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
নেমস্পেস std;int calcMaxSumofDiff(int N){ int maxSum =0 ব্যবহার করে#include <iostream>
using namespace std;
int calcMaxSumofDiff(int N){
int maxSum = 0;
maxSum = ((N*N) - 2) /2 ;
return maxSum;
}
int main(){
int N = 13;
cout<<"The maximum sum of difference of adjacent elements is "<<calcMaxSumofDiff(N);
return 0;
} আউটপুট
The maximum sum of difference of adjacent elements is 83
