C Chương trình Xếp hình thả trứng - DP-11?

Đây là một bài toán đố nổi tiếng. Giả sử có một tòa nhà có n tầng, nếu chúng ta có m quả trứng, thì làm thế nào để có thể tìm được số giọt tối thiểu cần thiết để tìm được một tầng mà từ đó có thể thả một quả trứ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 nhất định thì quả trứng cũng sẽ không vỡ đối với bất kỳ tầng nào thấp hơn.
• Nếu một quả trứng bị vỡ từ một tầng nhất định thì quả trứng đó sẽ vỡ cho tất cả các tầng trên.
• Khi trứng bị vỡ thì phải bỏ đi, nếu không chúng ta có thể sử dụng lại.

Đầu vào - Số lượng trứng và tầng tối đa. Giả sử số lượng trứng là 4 và tầng tối đa là 10.

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

Thuật toán

eggTrialCount (trứng, tầng)

Đầu vào - Số lượng trứng, tầng tối đa.

Đầu ra - Nhận số lần dùng 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));
}

Đầu ra

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