ปริศนาทอยไข่ (Egg Dropping Puzzle)

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

กติกาสำคัญ:

• ไข่ไม่แตกที่ชั้น k → ไม่แตกที่ชั้นต่ำกว่า k ทุกชั้น
• ไข่แตกที่ชั้น k → แตกที่ชั้นสูงกว่า k ทุกชั้น
• ไข่แตกต้องทิ้ง ไข่ไม่แตกใช้ซ้ำได้

การรับค่าและแสดงผล

Input: จำนวนไข่ = 4, ชั้นสูงสุด = 10
Output: Minimum number of trials: 4

อัลกอริทึม

eggTrialCount(eggs, floors) - Dynamic Programming

Begin
  สร้างเมทริกซ์ minTrial[eggs+1][floors+1]
  
  for i := 1 ถึง eggs do
    minTrial[i, 1] := 1  // 1 ชั้น ใช้ 1 ครั้ง
    minTrial[i, 0] := 0  // 0 ชั้น ใช้ 0 ครั้ง
  done
  
  for j := 1 ถึง floors do
    minTrial[1, j] := j  // 1 ฟอง ต้องลองทุกชั้น
  done
  
  for i := 2 ถึง eggs do
    for j := 2 ถึง floors do
      minTrial[i, j] := INF
      for k := 1 ถึง j do  // ลองทอยที่ชั้น k
        res := 1 + max(minTrial[i-1, k-1], minTrial[i, j-k])
        if res < minTrial[i, j] then minTrial[i, j] := res
      done
    done
  done
  
  return minTrial[eggs, floors]
End

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

#include <iostream>
using namespace std;

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

int eggTrialCount(int eggs, int floors) {
  int minTrial[eggs+1][floors+1];
  
  for (int i = 1; i <= eggs; i++) {
    minTrial[i][1] = 1;
    minTrial[i][0] = 0;
  }
  
  for (int j = 1; j <= floors; j++)
    minTrial[1][j] = j;
  
  for (int i = 2; i <= eggs; i++) {
    for (int j = 2; j <= floors; j++) {
      minTrial[i][j] = INT_MAX;
      for (int k = 1; k <= j; k++) {
        int 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;
  cout << "Enter number of eggs: "; cin >> egg;
  cout << "Enter max Floor: "; cin >> maxFloor;
  cout << "Minimum number of trials: " << eggTrialCount(egg, maxFloor);
}

ผลลัพธ์

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