Bertemu di Tengah
Bahagikan eksponen kepada separuh dengan membahagi carian.
Bertemu di Tengah ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apabila Percubaan Menyeluruh Terlalu Perlahan
Sesetengah masalah mempunyai N sekitar 40, dan mencuba semua subhimpunan 2^N adalah mustahil secara praktikal. Temu di tengah menyelesaikan kes bersaiz sederhana ini. 🤝
Idea Teras
Bahagikan masukan kepada dua separuh. Selesaikan setiap separuh dengan percubaan menyeluruh, kemudian gabungkan kedua-dua hasil separa itu dengan bijak.
Membahagi Dua Eksponen
Dua separuh bersaiz N/2 masing-masing memerlukan 2^(N/2), bukannya jumlah 2^N. Pengecilan sebanyak punca kuasa dua ini menukar 2^40 kepada 2^20 yang lebih mudah diurus.
Sasaran Klasik: Jumlah Subhimpunan
Tentukan sama ada ada subhimpunan yang jumlahnya sama dengan sasaran T. Jumlah subhimpunan dengan N sekitar 40 ialah masalah temu di tengah yang menjadi contoh klasik.
Senaraikan Separuh Pertama
Senaraikan setiap jumlah subhimpunan daripada separuh kiri dan simpannya. Dengan N/2 item, terdapat hanya 2^(N/2) jumlah.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Senaraikan Separuh Kedua
Lakukan perkara yang sama untuk separuh kanan dengan membina senarai penuh jumlah subhimpunannya. Kini anda mempunyai dua senarai yang mudah diurus.
Gabungkan dengan Carian
Bagi setiap jumlah kanan r, anda memerlukan jumlah kiri yang sama dengan T tolak r. Himpunan atau senarai terisih menjadikan semakan itu pantas.
need = T - r
found = need in left_setDua Cara Memadankan
Untuk sasaran tepat, gunakan himpunan cincang. Untuk mengira atau mencari jumlah terdekat, isih satu separuh dan lakukan carian binari terhadapnya.
Kos Masa
Jumlah kerja ialah kira-kira 2^(N/2) didarab dengan faktor log bagi carian atau pengisihan. Kerumitan itulah yang menjadikan N sekitar 40 boleh dilaksanakan.
Pertukaran Kos Memori
Anda menyimpan satu separuh penuh, jadi memori berkembang hingga 2^(N/2). Simpan hanya perkara yang perlu supaya kekal dalam had.
Kegunaan Lain
Selain jumlah subhimpunan, gunakan kaedah ini untuk subhimpunan maksimum di bawah had, mengira pasangan dan masalah gaya logaritma diskret. Kaedah ini sesuai dengan pembahagian yang jelas.
Semakan Pantas
Anda menggunakan temu di tengah untuk masalah subhimpunan dengan N item. Apakah anggaran kos masanya?
Rumusan
Bahagikan kepada dua separuh, lakukan percubaan menyeluruh bagi setiap satu, kemudian padankan jumlah kiri dan kanan. Anda menukar sedikit memori untuk peningkatan kelajuan yang sangat besar. 🚀
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Bertemu di Tengah” percuma?
Ya — teks penuh “Bertemu di Tengah” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Bertemu di Tengah”?
Bahagikan eksponen kepada separuh dengan membahagi carian. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Bertemu di Tengah” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Keadaan Menang dan Kalah dalam Permainan
- Nim dan Nombor Grundy
- Bertemu di Tengah
- Nyahpepijat dengan Pantas: Ujian Tekanan dan Triage