โปรแกรมนี้หาผลรวมความต่างสัมบูรณ์ต่ำสุดของอาร์เรย์ที่มีสมาชิกไม่ซ้ำกัน เริ่มจากทบทวนแนวคิดที่จำเป็น:
- อาร์เรย์ (Array) — ตู้เก็บข้อมูลชนิดเดียวกัน ความยาวต้องกำหนดไว้ล่วงหน้า
- ความต่างสัมบูรณ์ (Absolute Difference) — ค่าสัมบูรณ์ของความต่างระหว่างสองจำนวน (ค่าบวกเสมอ)
สูตรความต่างสัมบูรณ์ต่ำสุดของแต่ละสมาชิก:
Minimum Absolute Difference (a) = min(abs(a – arr[j])) โดยที่ 1 ≤ j ≤ n และ j ≠ i
Input: arr = {1, 3, 9, 3, 6} Output: 8
คำอธิบาย
คำตอบที่ดีที่สุดคือเลือก x = 3 ซึ่งให้ผลรวม:
|1 – 3| + |3 – 3| + |9 – 3| + |3 – 3| = 2 + 0 + 6 + 0 = 8
อัลกอริทึม
- เรียงลำดับอาร์เรย์ที่รับเข้ามา
- ความต่างสัมบูรณ์ต่ำสุดของ สมาชิกแรก คำนวณจากสมาชิกที่สอง
- ความต่างสัมบูรณ์ต่ำสุดของ สมาชิกสุดท้าย คำนวณจากสมาชิกลำดับก่อนสุด
- สำหรับสมาชิกอื่นๆ ที่อยู่ดัชนี i คำนวณจาก: minAbsDiff = min( abs(arr[i] – arr[i-1]), abs(arr[i] – arr[i+1]) )
ตัวอย่างโค้ด
#include<iostream>
#include <algorithm>
using namespace std;
int abs_sum(int a[], int len);
int main() {
int a[]={1, 3, 9, 3, 6};
int n, i;
n=5;
sort(a, a+n);
int sum = 0;
sum += abs(a[0]- a[1]);
sum += abs(a[n-1]-a[n-2]);
for (int i = 1; i < n-1; i++) {
sum += min(abs(a[i]-a[i-1]), abs(a[i]-a[i+1]));
}
cout<<"The element with minimum sum of absolute differences is : "<<sum;
return 0;
}
ผลลัพธ์
The element with minimum sum of absolute differences is : 8
