Java : รูปแบบการเขียนโปรแกรมแบบ Divide and conquer

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

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

ลักษณะการแก้ปัญหาแบบนี้จะพบได้ในการเขียนโปรแกรมแบบ recursive เช่นโปรแกรมหา factorial ดังตัวอย่างด้านล่าง

package com.company;

class FactorialExample2{
    static int factorial(int n){
        if (n == 0)
            return 1;
        else
            return(n * factorial(n-1));
    }
    public static void main(String args[]){
        int i,fact=1;
        int number=4; //It is the number to calculate factorial
        fact = factorial(number);
        System.out.println("Factorial of "+number+" is: "+fact);
    }
}

จากตัวอย่างจะเห้นว่าปัญหาคือ factorial(int n) ถูกแบ่งย่อยลงมาเป็น n * factorial(n-1) ซึ่งก็จะถูกแบ่งย่อยลงไปอีกจากการเรียกใช้เมธอดของตัวเอง จากนั้นผลลัพธ์ในขั้นตอนย่อยสุดจะถูกส่งต่อๆขึ้นมาจนกลายเป็นผลลัพธ์ของปัญหาเดิมในที่สุด