Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng chênh lệch lớn nhất của các phần tử liền kề trong C ++.
Mô tả vấn đề
Chúng tôi sẽ tìm Tổng lớn nhất của hiệu số tuyệt đối giữa các phần tử liền kề của tất cả các mảng hoán vị.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 4
Đầu ra
7
Giải thích
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 Phương pháp tiếp cận giải pháp
Để giải quyết dạng bài toán này, chúng ta cần tìm tổng chung của hoán vị.
Dưới đây là một số giá trị của Tổng hiệu số tối đa của các phần tử liền kề đối với các giá trị khác nhau của 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
Tổng này trông giống như một phép cộng phụ thuộc của N + tổng của N số hạng
maxSum =S (N) + F (N) S (N) =n (n-1) / 2, và F (N) là một hàm chưa biết của N
Hãy tìm F (N) bằng cách sử dụng S (N), maxSum (N).
F(2) = 0 F(3) = 0 F(4) = 1 F(5) = 1 F(6) = 2 F(7) = 2 F(8) = 3
Từ đây, chúng ta có thể suy ra rằng F (N) là Int (N / 2 - 1). F (N) tăng lên với mỗi giá trị thứ hai của N và ban đầu đối với 2 và 3 thì nó bằng không.
Điều này tạo nên công thức cho 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
Sử dụng công thức này, chúng ta có thể tìm giá trị maxSum của bất kỳ giá trị N nào cho trước.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum sum of difference of adjacent elements is 83