सी++ में आसन्न तत्वों के अंतर का अधिकतम योग

इस समस्या में, हमें एक संख्या N दी जाती है। हमारा कार्य C++ में आसन्न तत्वों के अंतर का अधिकतम योग ज्ञात करने के लिए एक प्रोग्राम बनाना है।

समस्या का विवरण

हम सभी क्रमपरिवर्तन सरणियों के आसन्न तत्वों के बीच पूर्ण अंतर का अधिकतम योग पाएंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

N = 4

आउटपुट

स्पष्टीकरण

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 पदों के योग पर निर्भर जोड़ जैसा दिखता है

मैक्ससम =एस (एन) + एफ (एन) एस (एन) =एन (एन -1) / 2, और एफ (एन) एन का एक अज्ञात कार्य है

आइए 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 = 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 के किसी भी दिए गए मान का अधिकतम योग मान ज्ञात कर सकते हैं।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,

#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