এই সমস্যায়, আমাদের একটি সংখ্যা N দেওয়া আছে। আমাদের কাজ হল সি++-এ পারমিউটেশনে সন্নিহিত উপাদানগুলোর পার্থক্যের সর্বোচ্চ যোগফল বের করার একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমরা সব পারমিউটেশন অ্যারেতে সন্নিহিত উপাদানগুলোর পরম মানের পার্থক্যের সর্বোচ্চ যোগফল বের করব।
উদাহরণ দিয়ে বুঝতে চেষ্টা করি,
ইনপুট
N = 4
আউটপুট
7
ব্যাখ্যা
সাইজ 4-এর সব পারমিউটেশন: {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-এর জন্য maxSum মান বের করা যায়।
উদাহরণ
আমাদের সমাধানের কার্যকারিতা বোঝার জন্য প্রোগ্রাম,
#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
