C++에서 인접한 요소의 차이의 최대 합

이 문제에서 우리는 숫자 N을 받습니다. 우리의 임무는 C++에서 인접 요소의 차이의 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명

모든 순열 배열의 인접 요소 간의 절대 차이의 최대 합을 찾습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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 =1N =3, maxSum =3N =4, maxSum =7N =5, maxSum =11N =6, maxSum =17N =7, maxSum =23N =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) =0F(3) =0F(4) =1F(5) =1F(6) =2F(7) =2F(8) =3

여기에서 F(N)이 Int(N/2 - 1)임을 도출할 수 있습니다. F(N)은 N 값이 2초마다 증가하고 처음에는 2와 3에 대해 0입니다.

이것은 maxSum에 대한 공식을 만듭니다.

이 공식을 사용하여 주어진 N 값의 maxSum 값을 찾을 수 있습니다.

예시

솔루션의 작동을 설명하는 프로그램,

#include 네임스페이스 std;int calcMaxSumofDiff(int N){ int maxSum =0; 최대합 =((N*N) - 2) /2; return maxSum;}int main(){ int N =13; cout<<"인접한 요소의 차이의 최대 합은 "< 
출력
 
인접한 요소의 차이의 최대 합은 83입니다.