การใช้งาน Longest common subsequent ในภาษา C แบบง่ายๆ พร้อมตัวอย่าง

## บทความ: การประยุกต์ใช้งาน Longest Common Subsequence (LCS) ในโลกจริงและตัวอย่างโค้ดด้วยภาษา C

ความสำคัญของ LCS ในวิชาการเขียนโปรแกรม

Longest Common Subsequence (LCS) คือ หัวข้อที่สำคัญในวิชาการเขียนโปรแกรมและเป็นส่วนหนึ่งของ Dynamic Programming ที่นักเรียนภาษา C และภาษาโปรแกรมอื่นๆ ควรศึกษา เพราะเป็นพื้นฐานที่สำคัญในการแก้ไขปัญหาที่ซับซ้อนต่างๆ เช่น การแก้ปัญหา diff ในระบบเวอร์ชันคอนโทรล, การเปรียบเทียบ DNA หรือการแปลภาษาที่จำเป็นต้องหาความเหมือนในลำดับของข้อมูลที่มีความยาวมหาศาล

อธิบายการทำงานของ LCS

ก่อนที่จะพูดถึงตัวอย่างโค้ด มาทำความเข้าใจว่า LCS ทำงานอย่างไร LCS คือการค้นหาลำดับย่อยที่ยาวที่สุดซึ่งอยู่ในทั้งสองสายอักขระ โดยไม่จำเป็นต้องมีตำแหน่งติดกัน ตัวอย่างเช่น ถ้ามีสายอักขระ A = "ABCDE" และ B = "ACBE" นั่นคือ LCS คือ "ACE" ซึ่งมีความยาว 3

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

การประยุกต์ใช้งาน LCS ในโลกจริง

ในโลกจริงนั้น LCS มีความสำคัญมาก เช่น

- การพัฒนาซอฟต์แวร์: เมื่อนักพัฒนาต้องการเปรียบเทียบซอร์ซโค้ดเวอร์ชันต่างๆ เพื่อเห็นความแตกต่าง (diff)

- ชีววิทยา: เมื่อนักวิทยาศาสตร์ต้องการเปรียบเทียบลำดับของ DNA, RNA หรือโปรตีน

- ระบบอัตโนมัติ: เช่น ระบบตรวจสอบการละเมิดลิขสิทธิ์ทางอินเทอร์เน็ตที่ค้นหาชุดข้อมูลที่คล้ายคลึงกัน

ตัวอย่างโค้ดด้วยภาษา C

ที่ EPT, เราหวังว่าผู้เรียนจะสามารถนำความรู้ไปใช้ได้จริง ต่อไปนี้คือตัวอย่างโค้ด LCS สามตัวอย่างในภาษา C:

โค้ดตัวอย่างที่ 1: LCS พื้นฐาน

 #include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b)? a : b;
}

int lcs(char *X, char *Y, int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    } else if (X[m-1] == Y[n-1]) {
        return 1 + lcs(X, Y, m-1, n-1);
    } else {
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
    }
}

int main() {
    char X[] = "ABCDE";
    char Y[] = "ACBE";
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d\n", lcs(X, Y, m, n));

    return 0;
}

แม้ว่าโค้ดนี้จะถูกต้อง แต่มีประสิทธิภาพต่ำเพราะมีการเรียกฟังก์ชัน lcs ซ้ำๆ ซึ่งทำให้มี Time Complexity เป็น O(2^n)

โค้ดตัวอย่างที่ 2: LCS โดยใช้ Dynamic Programming

 #include <stdio.h>
#include <string.h>

void printLCS(char *X, char *Y, int m, int n) {
    int L[m+1][n+1];
    // Build L[m+1][n+1] in bottom up fashion
    for (int i=0; i<=m; i++) {
        for (int j=0; j<=n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }

    // Following code is used to print LCS
    int index = L[m][n];

    // Create a character array to store the lcs string
    char lcs[index+1];
    lcs[index] = '\0'; // Set the terminating character

    // Start from the right-most-bottom-most corner and
    // one by one store characters in lcs[]
    int i = m, j = n;
    while (i > 0 && j > 0) {
        // If current character in X[] and Y are same, then
        // current character is part of LCS
        if (X[i-1] == Y[j-1]) {
            lcs[index-1] = X[i-1]; // Put current character in result
            i--; j--; index--;     // reduce values of i, j and index
        }
        // If not same, then find the larger of two and
        // go in the direction of larger value
        else if (L[i-1][j] > L[i][j-1])
            i--;
        else
            j--;
    }

    // Print the lcs
    printf("%s\n", lcs);
}

int main() {
    char X[] = "ABCDE";
    char Y[] = "ACBE";
    int m = strlen(X);
    int n = strlen(Y);
    printLCS(X, Y, m, n);
    return 0;
}

โค้ดนี้ได้ประสิทธิภาพที่ดีกว่าโดยมี Time Complexity เป็น O(m*n) เพราะหลีกเลี่ยงการคำนวณซ้ำในปัญหาย่อยๆ

โค้ดตัวอย่างที่ 3: LCS ที่สามารถรับข้อมูลจากผู้ใช้

 #include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b)? a : b;
}

int lcs(char *X, char *Y, int m, int n) {
    int L[m+1][n+1];
    for (int i=0; i<=m; i++) {
        for (int j=0; j<=n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    return L[m][n];
}

int main() {
    char X[1024];
    char Y[1024];

    printf("Enter first sequence: ");
    scanf("%s", X);

    printf("Enter second sequence: ");
    scanf("%s", Y);

    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS: %d\n", lcs(X, Y, m, n));

    return 0;
}

ตัวอย่างโค้ดที่ 3 นี้ช่วยให้ผู้ใช้สามารถป้อนข้อมูลสายอักขระได้โดยตรงและคำนวณหา LCS ได้ทันที

สรุป

Longest Common Subsequence เป็นเครื่องมือที่มีประสิทธิภาพในการแก้ไขปัญหาทางคอมพิวเตอร์ที่หลากหลาย และภาษา C ทำให้เราสามารถเข้าใจและประยุกต์ใช้แนวคิดนี้ได้อย่างมีประสิทธิภาพ ที่ Expert-Programming-Tutor เรามุ่งมั่นที่จะสนับสนุนและช่วยนักเรียนของเราในการรับมือกับทักษะที่จำเป็นเหล่านี้ เพื่ออนาคตที่สดใสในการเป็นนักโปรแกรมเมอร์ที่คล่องตัวและประสบความสำเร็จ!

ถ้าคุณคือคนที่หลงใหลในการเข้าใจและใช้แนวคิดใหม่ๆ ทางโปรแกรมมิ่งให้เป็นประโยชน์ ไม่ควรพลาดโอกาสในการเรียนรู้กับเราที่ Expert-Programming-Tutor โดยคุณจะได้สัมผัสกับการเรียนการสอนที่เน้นทักษะปฏิบัติและการวิเคราะห์ปัญหาอย่างลึกซึ้ง พร้อมทั้งมีโอกาสนำความรู้เหล่านี้ไปใช้งานได้จริงในโลกการทำงานที่เปี่ยมไปด้วยความท้าทาย!

ติดต่อเราที่ Expert-Programming-Tutor วันนี้เพื่อเริ่มเดินทางในโลกโปรแกรมมิ่งที่ไม่สิ้นสุด ด้วยหลักสูตรที่ตอบโจทย์ความต้องการของตลาดงานและสอดคล้องกับอุตสาหกรรมเทคโนโลยีปัจจุบัน!

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