หาจำนวนเซ็กซ์ทูเพลต (Sextuplets) ที่ทำให้สมการเป็นจริงด้วย C++

ในบทความนี้ เราจะอธิบายวิธีการหาจำนวนเซ็กซ์ทูเพลต (6 ตัวเลข) ที่ทำให้สมการเป็นจริง เราใช้สมการเป็นตัวอย่างที่เราต้องหาค่า a, b, c, d, e, และ f ที่ทำให้สมการด้านล่างเป็นจริง

( a + b + c ) * e / d = f

จัดเรียงสมการใหม่:

( a + b + c ) = ( f * d ) / e

ตัวอย่างง่ายสำหรับปัญหานี้:

Input : arr [ ] = { 1, 3 } Output : 4 Explanation : (a,b,c,e,f) = 1, d = 3; (a,b,c,d,e) = 1, f = 3; (a,b,c) = 1, (d,e,f) = 3; (a,b,c,d,f) = 3, (e) = 1
Input : arr [ ] = { 2, 5 } Output : 3

วิธีการหาคำตอบ

เราจะใช้วิธี Naive Approach เพื่อหาคำตอบของปัญหาที่กำหนด

Naive Approach

ในปัญหานี้ ดูจาก LHS และ RHS เราสามารถหาผลลัพธ์ที่เป็นไปได้ทั้งหมดของ LHS และเก็บในอาร์เรย์ คล้ายกัน สร้างอาร์เรย์สำหรับ RHS และเติมด้วยผลลัพธ์ที่เป็นไปได้ทั้งหมดของ RHS

ตรวจสอบทั้งสองอาร์เรย์หาค่าที่เหมือนกัน และเพิ่มจำนวนสำหรับแต่ละค่าที่พบ แล้วแสดงผลลัพธ์สุดท้าย

ตัวอย่างโค้ด

#include<bits/stdc++.h>
using namespace std;

int findsamenumbers(int *arr1, int *arr2, int n) {
    int i = 0, j = 0, k = 0, count = 0;
    while((i < n*n*n+1) && (j < n*n*n+1)) {
        if(arr1[i] < arr2[j])
            i++;
        else if(arr1[i] == arr2[j]) {
            count++;
            int temp = arr1[i];
            while(temp == arr1[++i])
                count++;
            while(temp == arr2[++j])
                count++;
        } else
            j++;
    }
    return count;
}

int main() {
    int arr[] = {2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // สร้างค่าที่เป็นไปได้ทั้งหมดของอาร์เรย์ LHS
    int index = 0, i;
    int LHS[n*n*n];
    for (i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                LHS[index++] = (arr[i] * arr[j]) / arr[k];
            }
        }
    }
    
    // สร้างค่าที่เป็นไปได้ทั้งหมดของอาร์เรย์ RHS
    int RHS[n*n*n];
    index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                RHS[index++] = (arr[i] + arr[j] + arr[k]);
            }
        }
    }
    
    sort(RHS, RHS + (n*n*n));
    sort(LHS, LHS + (n*n*n));
    int result = findsamenumbers(LHS, RHS, n);
    cout << "Number of sextuplets that satisfy an equation: " << result;
    return 0;
}

ผลลัพธ์

Number of sextuplets that satisfy an equation: 3

คำอธิบายโปรแกรม

ในโปรแกรมนี้ เราสร้างอาร์เรย์สองอาร์เรย์สำหรับเก็บผลลัพธ์ทุกค่าของ LHS และ RHS เราใช้ nested loop 3 ชั้น สำหรับใส่ค่าที่เป็นไปได้ทุกค่าของ (a, b, c) ใน LHS และ (d, e, f) ใน RHS หลังจากนั้น เราจัดเรียง (sort) ทั้งสองอาร์เรย์ เพื่อเปรียบเทียบและหาค่าที่เหมือนกันในทั้งสองอาร์เรย์ ส่งทั้งสองอาร์เรย์ไปยังฟังก์ชัน findsamenumber()

ในฟังก์ชัน findsamenumber() เราตรวจสอบค่าที่เหมือนกันโดยใช้ nested loop 2 ชั้น เมื่อพบสมาชิกสองตัวที่เหมือนกัน เราตรวจสอบความถี่ของตัวเลขนั้นในทั้งสองอาร์เรย์ เพื่อให้ทุกค่าที่เป็นไปได้ถูกนับ

if(arr1[i] == arr2[j]) {
    count++;
    int temp = arr1[i];
    while(temp == arr1[++i])
        count++;
    while(temp == arr2[++j])
        count++;
}

สรุป

ในบทความนี้ เราแก้ปัญหาจำนวนเซ็กซ์ทูเพลตที่ทำให้สมการเป็นจริง โดยในอาร์เรย์ที่กำหนด เราหาค่าที่เป็นไปได้ทุกค่าของตัวแปรในสมการ 6 ตัวแปร (a + b + c) * e / d = f เราสามารถแก้ปัญหานี้ในภาษาโปรแกรมมิ่งอื่นๆ เช่น C, Java, และ Python ได้เช่นกัน