Bài toán rơi trứng (Egg Dropping Puzzle)

Đây là một bài toán nổi tiếng. Giả sử có một tòa nhà n tầng, nếu ta có m quả trứng, thì làm thế nào để tìm số lần rơi tối thiểu cần thiết để tìm một tầng mà từ đó rơi trứng xuống mà không bị vỡ.

Có một số điểm quan trọng cần nhớ:

• Khi một quả trứng không vỡ từ một tầng cho trước, thì nó sẽ không vỡ cho bất kỳ tầng thấp hơn nào.
• Nếu một quả trứng vỡ từ một tầng cho trước, thì nó sẽ vỡ cho tất cả các tầng trên.
• Khi một quả trứng vỡ, nó phải bị loại bỏ, ngược lại ta có thể dùng lại nó.

Đầu vào và Đầu ra

Đầu vào: Số lượng trứng và tầng tối đa. Giả sử số trứng là 4 và tầng tối đa là 10.
Đầu ra: Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4

Thuật toán

eggTrialCount(eggs, floors)
Đầu vào: Số lượng trứng, tầng tối đa.
Đầu ra: Lấy số lần thử tối thiểu.
Bắt đầu
  định nghĩa ma trận kích thước [eggs+1, floors+1]
  với i:= 1 đến eggs, làm
    minTrial[i, 1] := 1
    minTrial[i, 0] := 0
  kết thúc
  với j := 1 đến floors, làm
    minTrial[1, j] := j
  kết thúc
  với i := 2 đến eggs, làm
    với j := 2 đến floors, làm
      minTrial[i, j] := ∞
      với k := 1 đến j, làm
        res := 1 + max của minTrial[i-1, k-1] và minTrial[i, j-k]
        nếu res < minTrial[i, j] thì
          minTrial[i,j] := res
      kết thúc
    kết thúc
  kết thúc
  trả về minTrial[eggs, floors]
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

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

int eggTrialCount(int eggs, int floors) {
  // số lần thử tối thiểu cho trường hợp xấu nhất
  int minTrial[eggs+1][floors+1];
  // lưu số lần thử tối thiểu cho trứng thứ i và tầng thứ j
  int res;
  
  for (int i = 1; i <= eggs; i++) {
    // một lần thử kiểm tra từ tầng 1, và không thử cho tầng 0
    minTrial[i][1] = 1;
    minTrial[i][0] = 0;
  }
  
  for (int j = 1; j <= floors; j++)
    // khi trứng là 1, cần j lần thử cho mỗi tầng
    minTrial[1][j] = j;
  
  for (int i = 2; i <= eggs; i++) {
    // cho 2 hoặc nhiều hơn 2 trứng
    for (int j = 2; j <= floors; j++) {
      // cho tầng 2 hoặc cao hơn
      minTrial[i][j] = INT_MAX;
      for (int 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]; // số lần thử cho trứng và tầng được hỏi
}

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

Đầu ra

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