Python - แบ่งและพิชิต

ในแนวทางการแบ่งแยกและพิชิตปัญหาในมือจะแบ่งออกเป็นปัญหาย่อยที่เล็กกว่าจากนั้นแต่ละปัญหาจะได้รับการแก้ไขอย่างอิสระ เมื่อเราแบ่งปัญหาย่อยออกเป็นปัญหาย่อย ๆ ไปเรื่อย ๆ ในที่สุดเราก็อาจถึงขั้นตอนที่ไม่มีการแบ่งแยกอีกต่อไป ปัญหาย่อย (เศษส่วน) "อะตอม" ที่เล็กที่สุดที่เป็นไปได้เหล่านั้นได้รับการแก้ไข ในที่สุดการแก้ปัญหาย่อยทั้งหมดจะถูกรวมเข้าด้วยกันเพื่อให้ได้วิธีการแก้ปัญหาเดิม

ในวงกว้างเราสามารถเข้าใจได้ divide-and-conquer แนวทางในกระบวนการสามขั้นตอน

แบ่ง / แบ่ง

ขั้นตอนนี้เป็นการแบ่งปัญหาออกเป็นปัญหาย่อยที่เล็กกว่า ปัญหาย่อยควรแสดงถึงส่วนหนึ่งของปัญหาเดิม โดยทั่วไปขั้นตอนนี้จะใช้วิธีการวนซ้ำเพื่อแบ่งปัญหาจนกว่าจะไม่มีปัญหาย่อยใดมาหารได้อีก ในขั้นตอนนี้ปัญหาย่อยกลายเป็นปรมาณูในธรรมชาติ แต่ยังคงเป็นตัวแทนบางส่วนของปัญหาที่แท้จริง

พิชิต / แก้

ขั้นตอนนี้ได้รับปัญหาย่อยที่เล็กกว่าจำนวนมากที่ต้องแก้ไข โดยทั่วไปในระดับนี้ปัญหาจะถือว่า 'แก้ไข' ได้ด้วยตัวเอง

ผสาน / รวม

เมื่อปัญหาย่อยที่เล็กกว่าได้รับการแก้ไขขั้นตอนนี้จะรวมปัญหาเหล่านี้ซ้ำ ๆ จนกว่าจะกำหนดวิธีการแก้ปัญหาเดิม วิธีการอัลกอริทึมนี้ทำงานแบบวนซ้ำและขั้นตอนการพิชิตและผสานทำงานใกล้เคียงกันมากจนปรากฏเป็นหนึ่ง

ตัวอย่าง

โปรแกรมต่อไปนี้เป็นตัวอย่างของ divide-and-conquer แนวทางการเขียนโปรแกรมที่ใช้การค้นหาไบนารีโดยใช้ python

การใช้งานการค้นหาแบบไบนารี

ในการค้นหาแบบไบนารีเราจะจัดเรียงรายการองค์ประกอบและเริ่มมองหาองค์ประกอบที่อยู่ตรงกลางรายการ หากค่าการค้นหาตรงกับค่ากลางในรายการเราทำการค้นหาให้เสร็จสิ้น มิฉะนั้นเราจะแบ่งครึ่งหนึ่งของรายการองค์ประกอบโดยเลือกว่าจะประมวลผลด้วยครึ่งขวาหรือซ้ายของรายการขึ้นอยู่กับมูลค่าของรายการที่ค้นหา สิ่งนี้เป็นไปได้เมื่อมีการจัดเรียงรายการและรวดเร็วกว่าการค้นหาเชิงเส้นมาก ที่นี่เราแบ่งรายการที่กำหนดและพิชิตโดยเลือกครึ่งหนึ่งของรายการที่เหมาะสม เราทำซ้ำ Approcah นี้จนกว่าเราจะพบองค์ประกอบหรือสรุปว่าไม่มีอยู่ในรายการ

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))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังต่อไปนี้:

5
None