หาจำนวนควอดรูเพิล (Quadruples) ที่ 3 พจน์แรกเป็น AP และ 3 พจน์ท้ายเป็น GP ด้วย C++

ในบทความนี้ เราจะอธิบายทุกวิธีที่เป็นไปได้ในการหาจำนวนควอดรูเพิล (quadruples) ที่ 3 พจน์แรกอยู่ในลำดับเลขคณิต (A.P.) และ 3 พจน์ท้ายอยู่ในลำดับเรขาคณิต (G.P.) ก่อนอื่น เราจะอธิบายความหมายพื้นฐานของลำดับเลขคณิต (A.P.) และลำดับเรขาคณิต (G.P.)

ลำดับเลขคณิต (Arithmetic Progression - A.P.) - เป็นลำดับของตัวเลขที่ความต่างร่วม (d) เหมือนกันหรือคงที่ กล่าวคือ ความต่างของตัวเลขที่ติดกันสองตัวคงที่ ตัวอย่าง: 1, 3, 5, 7, 9 | d = 2

ลำดับเรขาคณิต (Geometric Progression - G.P.) - เป็นลำดับของตัวเลขที่อัตราส่วนร่วม (r) เหมือนกัน กล่าวคือ เราสามารถหาพจน์แต่ละพจน์ได้โดยการคูณตัวเลขก่อนหน้าด้วยตัวเลขคงที่ ตัวอย่าง: 3, 6, 12, 24, ... | r = 2

ในโจทย์นี้ เราต้องหาว่ามีควอดรูเพิลดัชนี (a, b, c, d) กี่ชุดจากอาร์เรย์ arr[] ของ N จำนวนเต็ม ซึ่งทำให้ arr[a], arr[b], arr[c] อยู่ใน A.P. และ arr[d], arr[c], arr[b] อยู่ใน G.P. โดยควอดรูเพิลทั้งหมดต้องแน่นอน ตัวอย่าง:

Input : arr[ ] = { 9, 6, 4, 2, 1, 2 } Output : 2 Explanation: สมาชิกในควอดรูเพิลอยู่ที่ดัชนี {3, 2, 1, 0} และ {5, 2, 1, 0} โดยควอดรูเพิลคือ {2, 4, 6, 9} สำหรับทั้งสองตำแหน่ง
Input : arr[ ] = { 2, 6, 1, 4, 2 } Output : 2 Explanation: สมาชิกในควอดรูเพิลอยู่ที่ดัชนี {1, 3, 0, 2} และ {1, 3, 4, 2} โดยควอดรูเพิลคือ {6, 4, 2, 1} สำหรับทั้งสองตำแหน่ง

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

ตอนนี้ เราจะอธิบายสองวิธีที่แตกต่างกันในการหาคำตอบ:

1. วิธี Brute Force

เป็นวิธีง่ายๆ ในการแก้ปัญหานี้โดยใช้ nested loop 4 ชั้น แล้วตรวจสอบว่าพจน์แรก 3 ตัวอยู่ใน A.P. หรือไม่ หากใช่ ตรวจสอบต่อว่าพจน์ท้าย 3 ตัวอยู่ใน G.P. หรือไม่ หากใช่ ให้เพิ่มตัวนับ count ขึ้น 1 แต่วิธีนี้ใช้เวลานาน เพราะ ความซับซ้อนด้านเวลาคือ O(n⁴)

2. วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราหาจำนวนของสมาชิกแต่ละตัวในอาร์เรย์ก่อน แล้วพิจารณาสมาชิกทั้งสองตัวเป็นพจน์ที่สองและสาม และรัน nested loop 2 ชั้น พจน์แรกจะเป็น arr[b] - (arr[c] - arr[b]) และพจน์ที่สี่จะเป็น arr[c] * arr[c] / arr[b]

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

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

int main() {
    unordered_map<int, int> map;
    int arr[] = { 2, 6, 1, 4, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    // ประมวลผลทุกสมาชิกและเพิ่มจำนวน
    for (int a = 0; a < size; a++)
        map[arr[a]]++;
    
    int count = 0;
    // รัน nested loop 2 ชั้นสำหรับพจน์ที่สองและสาม
    for (int b = 0; b < size; b++) {
        for (int c = 0; c < size; c++) {
            if (b == c)
                continue;
            
            // ลดจำนวนลง
            map[arr[b]]--;
            map[arr[c]]--;
            
            // หาพจน์แรกโดยใช้ความต่างร่วม
            int first = arr[b] - (arr[c] - arr[b]);
            // หาพจน์ที่สี่โดยใช้ GP
            int fourth = (arr[c] * arr[c]) / arr[b];
            
            if ((arr[c] * arr[c]) % arr[b] == 0) {
                // เพิ่ม count หากไม่เท่ากัน
                if (arr[b] != arr[c])
                    count += map[first] * map[fourth];
                else
                    count += map[first] * (map[fourth] - 1);
            }
            
            map[arr[b]]++;
            map[arr[c]]++;
        }
    }
    
    cout << "Number of quadruples: " << count;
    return 0;
}

ผลลัพธ์

Number of quadruples: 2

คำอธิบายโค้ด

ในโค้ดนี้ เราใช้คณิตศาสตร์การจัดหมู่ (Combinatorics) และใช้ nested loop 2 ชั้นสำหรับพจน์ที่สองและสาม และหาพจน์แรกด้วย arr[a] - (arr[c] - arr[b]) และพจน์ที่สี่ด้วย arr[c] * arr[c] / arr[b] ดังนั้น จำนวนควอดรูเพิลจากดัชนี A และ B คือ จำนวนของพจน์แรก * พจน์ที่สี่ โดยคงพจน์ที่สองและสามไว้ ที่นี่ ความซับซ้อนด้านเวลา ของโค้ดข้างต้นคือ O(n²)

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนควอดรูเพิลที่ 3 พจน์แรกอยู่ใน AP และ 3 พจน์ท้ายอยู่ใน GP และเราอภิปรายสองวิธีในการแก้ปัญหา คือ Brute Force [O(n⁴)] และ Efficient Approach [O(n²)]

เราแก้ปัญหานี้ด้วย C++ และสามารถแก้ปัญหานี้ในภาษาอื่นๆ เช่น Java, Python, C หรือภาษาโปรแกรมมิ่งอื่นๆ ได้เช่นกัน