Python - Bagilah dan taklukkan

Dalam pendekatan divide and conquer, masalah yang ada, dibagi menjadi sub-sub masalah yang lebih kecil dan kemudian setiap masalah diselesaikan secara mandiri. Ketika kita terus membagi sub-masalah menjadi sub-masalah yang lebih kecil lagi, kita pada akhirnya mungkin mencapai tahap di mana tidak ada lagi pembagian yang memungkinkan. Sub-masalah (pecahan) sekecil mungkin yang "atomik" terpecahkan. Solusi dari semua sub masalah akhirnya digabungkan untuk mendapatkan solusi dari masalah asli.

Secara luas, kita bisa mengerti divide-and-conquer pendekatan dalam proses tiga langkah.

Bagilah / Pecahkan

Langkah ini melibatkan pemecahan masalah menjadi sub-masalah yang lebih kecil. Sub-masalah harus mewakili bagian dari masalah asli. Langkah ini umumnya mengambil pendekatan rekursif untuk membagi masalah sampai tidak ada sub-masalah yang dapat dibagi lagi. Pada tahap ini, sub-masalah menjadi bersifat atomik tetapi masih mewakili sebagian dari masalah yang sebenarnya.

Taklukkan / Pecahkan

Langkah ini menerima banyak sub-masalah kecil yang harus diselesaikan. Umumnya, pada level ini, masalah dianggap 'terselesaikan' dengan sendirinya.

Gabung / Gabungkan

Ketika sub-masalah yang lebih kecil diselesaikan, tahap ini secara rekursif menggabungkan mereka sampai mereka merumuskan solusi dari masalah aslinya. Pendekatan algoritmik ini bekerja secara rekursif dan langkah-langkah menaklukkan & menggabungkan bekerja sangat dekat sehingga tampak sebagai satu kesatuan.

Contoh

Program berikut adalah contoh dari divide-and-conquer pendekatan pemrograman dimana pencarian biner diimplementasikan menggunakan python.

Implementasi Pencarian Biner

Dalam pencarian biner kita mengambil daftar elemen yang diurutkan dan mulai mencari elemen di tengah daftar. Jika nilai pencarian cocok dengan nilai tengah dalam daftar, kami menyelesaikan pencarian. Jika tidak, kami menghilangkan setengah dari daftar elemen dengan memilih apakah akan memproses dengan bagian kanan atau kiri daftar tergantung pada nilai item yang dicari. Ini dimungkinkan karena daftar diurutkan dan jauh lebih cepat daripada pencarian linier. Di sini kita membagi daftar yang diberikan dan menaklukkan dengan memilih separuh daftar yang tepat. Kami ulangi pendekatan ini sampai kami menemukan elemen atau menyimpulkan tentang ketidakhadirannya dalam daftar.

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Ketika kode di atas dijalankan, menghasilkan hasil sebagai berikut:

5
None