Temukan pasangan dengan nilai KPK terkecil dalam larik tertentu

Baru-baru ini saya menemukan pertanyaan tentang kontes pemrograman kompetitif. Diberikan sebuah array bilangan bulat, temukan indeks dari sepasang elemen array dengan nilai KPK terkecil.

Saya tahu ada solusi loop ganda O(n^2) yang naif tetapi seperti yang diharapkan, ini memberikan pengecualian batas waktu. Saya pernah mendengar bahwa pemrograman dinamis digunakan untuk mengoptimalkan pendekatan brute force tetapi saya tidak dapat memahami cara membagi masalah ini menjadi submasalah sehingga terdapat substruktur yang optimal.

Bisakah saya mendapatkan arahan untuk mengatasi masalah ini menggunakan DP? Atau pendekatan yang lebih baik? Terima kasih.


arrays algorithm data-structures dynamic-programming
person Mushi Master    schedule 17.04.2019    source sumber
comment
memproses terlebih dahulu setiap bilangan untuk mendapatkan dekomposisi bilangan prima mungkin bisa membantu.   -  person Jarod42    schedule 17.04.2019
comment
masalah apa yang sedang kamu hadapi?   -  person Syed Mehtab Hassan    schedule 17.04.2019
comment
Saya pikir dalam kasus umum (misalnya tidak ada angka dalam array yang memiliki faktor prima), Anda akan selalu mendapatkan O(n²) karena Anda harus menghitung produk dari setiap kombinasi dan membandingkan ukurannya. Satu-satunya kemungkinan untuk meningkatkan kecepatan Anda mungkin adalah dalam kasus khusus (yang mungkin merupakan kasus yang sangat umum) di mana elemen-elemen tersebut memiliki banyak faktor prima yang sama.   -  person Alfe    schedule 17.04.2019
comment
@Alfe jika semua angkanya koprima, Anda cukup mengambil 2 angka terkecil O(n)   -  person maraca    schedule 17.04.2019
comment
@maraca Anda benar jika Anda tahu bahwa semuanya koprima. Jika Anda memiliki asumsi ini, pengujiannya juga hanya O(n), tetapi saya berasumsi kasus normal bahwa beberapa akan menjadi koprima dan beberapa tidak, jadi Anda harus menemukan sesuatu yang dapat mengatasi ini kasus, dan algoritme (tidak terspesialisasi) ini akan memiliki O(n²) pada daftar semua bilangan koprima.   -  person Alfe    schedule 17.04.2019

Jawaban (1)


arrow_upward
0
arrow_downward

(Dengan asumsi bilangan positif.)

KPK terkecil kemungkinan besar berasal dari elemen terkecil, oleh karena itu untuk memangkas nilai percobaan, kita dapat mengurutkan array.

int[] v = { ... };

int minLCM = Integer.MAX_VALUE;
int bestVi = -1;
int bestVj = -1;
Arrays.sort(v);
for (int i = 0; i < v.length; ++i) {
    int vi = v[i];
    //                                  _____________
    for (int j = i + 1; j < v.length && v[j] < minLCM; ++j) {
        int vj = v[j];
        int lcm = lcm(vi, vj);
        if (lcm < minLcm) {
            minLCM = lcm;
            bestVi = vi;
            bestVj = vj;
        }
    }
}

Untuk pemangkasan:

lcm(vi, vj) >= vi
lcm(vi, vj) >= vj
(lcm(vi, vj) <= vi*vj

Pemangkasan ini dapat dilakukan di loop for-j hanya sebagai vj >= vi.

Pemangkasan yang lebih baik dapat dilakukan jika Anda memiliki daftar (paling banyak ²log value) faktor prima. Karena faktorisasi juga memerlukan biaya, kita bisa mencoba (2, 3, 5, 7) misalnya.

Perulangan yang lebih baik juga dapat dicapai dengan mengganti kedua perulangan bersarang sehingga yang terkecil (vi, vj) didahulukan. Di atas (v0, v100) muncul sebelum (v1, v2). Ulangi i+j yang semakin meningkat.

i j
0 1
0 2
0 3
1 2
0 4
1 3
0 5
1 4
2 3
...

(Perhitungan untuk penghitung loop menggunakan diagonal adalah teka-teki yang bagus. Harus benar-benar diselesaikan.)

Meskipun masih O(n²) ini mungkin berhasil.

Terkadang bahasa pemrograman juga penting, dan dalam konteks tersebut sering kali kita melihat kontribusi C. Dalam kasus seperti itu, penggunaan Ruby mungkin kontraproduktif.

person Joop Eggen    schedule 17.04.2019