Chương trình C cho bài toán rơi trứng - DP

Đâ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 chúng ta có m quả trứng, 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ỡ ở 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ỡ ở 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 chúng ta có thể dùng lại nó.

Input - Số quả trứng và tầng tối đa. Giả sử số trứng là 4 và tầng tối đa là 10.

Output - Số lần thử tối thiểu 4.

Thuật toán

eggTrialCount(eggs, floors)

Input - Số quả trứng, tầng tối đa.

Output - Lấy số lần thử tối thiểu.

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

Ví dụ

#include<stdio.h>
#define MAX_VAL 9999

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

int eggTrialCount(int eggs, int floors) {
  //minimum trials for worst case
  int minTrial[eggs+1][floors+1]; //to store minimum trials for i-th egg and jth floor
  int res, i, j, k;
  for (i = 1; i <= eggs; i++) { //one trial to check from first floor, and no trial for 0th floor
    minTrial[i][1] = 1;
    minTrial[i][0] = 0;
  }
  for (j = 1; j <= floors; j++) //when egg is 1, we need 1 trials for each floor
    minTrial[1][j] = j;
  for (i = 2; i <= eggs; i++){ //for 2 or more than 2 eggs
    for (j = 2; j <= floors; j++) { //for second or more than second floor
      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]; //number of trials for asked egg and floor
}

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

Kết quả

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