โปรแกรมนี้คือการค้นหาความแตกต่างสัมบูรณ์ขั้นต่ำของอาร์เรย์ เนื่องจากเรามีอาร์เรย์ที่มีองค์ประกอบที่แตกต่างกัน หากต้องการเรียนรู้แนวคิดนี้ให้ดีขึ้น เรามาแปรงสิ่งที่จำเป็นอีกครั้ง
อาร์เรย์ เป็นคอนเทนเนอร์ขององค์ประกอบประเภทข้อมูลเดียวกัน ต้องกำหนดความยาวของอาร์เรย์ไว้ล่วงหน้า
ความแตกต่างโดยสิ้นเชิง คือค่าสัมบูรณ์ของผลต่างระหว่างตัวเลขสองตัว กล่าวคือ ผลต่างจะเป็นบวกเสมอ ค่าลบจะถูกแปลงเป็นค่าบวก
ผลรวมของผลต่างสัมบูรณ์ต่ำสุดของแต่ละธาตุจะต้องหาสูตรผลต่างสัมบูรณ์ต่ำสุดคือ
ความแตกต่างสัมบูรณ์ขั้นต่ำ (a) =min(abs(a – arr[j]));
โดยที่ 1 <=j <=n และ j !=i, abs คือค่าสัมบูรณ์
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 =นาที( abs(arr[i] – arr[i-1]), abs(ar[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
