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

समस्या विवरण

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

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

उदाहरण

इनपुट

N = 4

आउटपुट

व्याख्या

आकार 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 मान ढूंढ सकते हैं।

C++ कार्यान्वयन

#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