Program C++: Cari subset boleh bahagi terbesar dalam tatasusunan

Tutorial ini akan membincangkan masalah di mana pelbagai integer positif diberikan. Kita perlu mencari subset terbesar supaya setiap pasangan elemen yang lebih besar dibahagikan dengan elemen yang lebih kecil, contohnya -

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

Cara untuk mencari penyelesaian

Kami akan menerangkan dua kaedah berbeza dalam tutorial ini.

Kaedah mudah

Dalam kaedah mudah, kita boleh menggunakan rekursi untuk menyelesaikan masalah ini. Kami akan mendapatkan setiap elemen dan menyemak sama ada ia perlu disertakan dalam subset. Katakan kita mulakan dengan elemen pertama. Kami akan mempunyai dua pilihan, sama ada untuk dimasukkan ke dalam subset atau tidak untuk dimasukkan ke dalam elemen pertama. Mari masukkan elemen pertama. Kemudian, untuk elemen kedua dimasukkan ke dalam subset, ia hendaklah boleh dibahagikan atau dibahagikan dengan elemen dalam subrentetan (iaitu elemen pertama). Beginilah cara kita mengulangi tatasusunan. Oleh itu, akan terdapat 2^n laluan yang mungkin dengan kerumitan masa O(2^n). Mari kita lihat penyelesaian yang mungkin untuk masalah ini.

Cara yang berkesan

boleh diselesaikan dengan menggunakan pengaturcaraan dinamik.

• Isih tatasusunan supaya elemen kiri boleh dibahagikan dengan elemen yang betul. Kita kena periksa kebolehbahagiaan sekali.

• Kami akan mengambil urutan yang paling lama meningkat, tatasusunan dp[ ] kami, untuk menyimpan subset boleh bahagi terbesar sehingga indeks ke-i. Kami akan memulakan setiap indeks dengan 1 kerana setiap elemen akan membahagikan dirinya sendiri.

• Sekarang kita akan beralih bermula dari indeks kedua dan menyemak untuk setiap elemen sama ada terdapat subset boleh bahagi maksimum yang berakhir pada indeks semasa. Dengan cara ini, kami mencari subset terbesar untuk setiap indeks.

• Sekarang lelaran melalui tatasusunan dan untuk setiap elemen cari pembahagi dengan pembahagian terbesar. Dan menukar nilai kiraan boleh bahagi indeks semasa kepada kiraan boleh bahagi unsur itu + 1. . subset. Kami membincangkan pendekatan rekursif yang menghasilkan kerumitan masa eksponen, jadi kami membincangkan penyelesaian pengaturcaraan dinamik. Kami juga membincangkan program C++ untuk menyelesaikan masalah ini, yang boleh kami laksanakan menggunakan bahasa pengaturcaraan seperti C, Java, Python, dll. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Program C++: Cari subset boleh bahagi terbesar dalam tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!