โปรแกรม C สำหรับ Egg Dropping Puzzle (Dynamic Programming)

นี่คือปริศนาที่มีชื่อเสียง: ตึกสูง n ชั้น มี m ฟองไข่ ต้องการหาจำนวนครั้งทดสอบน้อยที่สุด เพื่อหาชั้นที่ปลอดภัยสูงสุดที่ทิ้งไข่ไม่แตก

เงื่อนไขสำคัญ:

• ถ้าไข่ไม่แตกที่ชั้นหนึ่ง จะไม่แตกที่ชั้นต่ำกว่าด้วย
• ถ้าไข่แตกที่ชั้นหนึ่ง จะแตกที่ชั้นสูงกว่าทุกชั้น
• ไข่ที่แตกต้องทิ้ง ไข่ที่ไม่แตกใช้ซ้ำได้

Input - จำนวนไข่ และชั้นสูงสุด เช่น 4 ฟอง 10 ชั้น

Output - จำนวนครั้งทดสอบน้อยที่สุด = 4

อัลกอริทึม (Dynamic Programming)

eggTrialCount(eggs, floors)

Begin
    define matrix of size [eggs+1, floors+1]
    for i := 1 to eggs, do
        minTrial[i, 1] := 1
        minTrial[i, 0] := 0
    done
    for j := 1 to floors, do
        minTrial[1, j] := j
    done
    for i := 2 to eggs, do
        for j := 2 to floors, do
            minTrial[i, j] := ∞
            for k := 1 to j, do
                res := 1 + max of minTrial[i-1, k-1] and minTrial[i, j-k]
                if res < minTrial[i, j], then minTrial[i,j] := res
            done
        done
    done
    return minTrial[eggs, floors]
End

ตัวอย่างโค้ด (C)

#include <stdio.h>
#define MAX_VAL 9999

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

int eggTrialCount(int eggs, int floors) {
    int minTrial[eggs+1][floors+1];
    int res, i, j, k;
    for (i = 1; i <= eggs; i++) {
        minTrial[i][1] = 1;
        minTrial[i][0] = 0;
    }
    for (j = 1; j <= floors; j++)
        minTrial[1][j] = j;
    for (i = 2; i <= eggs; i++) {
        for (j = 2; j <= floors; j++) {
            minTrial[i][j] = MAX_VAL;
            for (k = 1; k <= j; k++) {
                res = 1 + max(minTrial[i-1][k-1], minTrial[i][j-k]);
                if (res < minTrial[i][j])
                    minTrial[i][j] = res;
            }
        }
    }
    return minTrial[eggs][floors];
}

int main() {
    int egg, maxFloor;
    printf("Enter number of eggs: ");
    scanf("%d", &egg);
    printf("Enter max Floor: ");
    scanf("%d", &maxFloor);
    printf("Minimum number of trials: %d", eggTrialCount(egg, maxFloor));
}

ผลลัพธ์

Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4