C-Programm Egg Drop Puzzle – DP-11

Das ist ein berühmtes Rätsel. Angenommen, es gibt ein Gebäude mit n Etagen. Wenn wir m Eier haben, wie finden wir dann die Mindestanzahl an Tropfen, die erforderlich sind, um eine Etage zu erreichen, in der wir die Eier sicher fallen lassen können, ohne sie zu zerbrechen?

Es gibt einige wichtige Punkte, die Sie beachten sollten:

• Wenn ein Ei von einem bestimmten Boden aus nicht zerbricht, dann zerbricht es auch von keinem darunter liegenden Boden aus.
• Wenn ein Ei von einem bestimmten Stockwerk aus zerbricht, dann zerbricht es auch in allen darüber liegenden Stockwerken.
• Wenn das Ei zerbricht, muss es entsorgt werden, sonst können wir es wieder verwenden.

Geben Sie ein: die Anzahl der Eier und den maximalen Boden. Angenommen, die Anzahl der Eier beträgt 4 und der maximale Boden beträgt 10.

Ausgabe – Mindestanzahl an Versuchen 4.

Algorithmus

eggTrialCount(ei, Boden)

Eingabe− Anzahl der Eier, maximaler Boden.

Ausgabe − Ermitteln Sie die Mindestanzahl an Eiertests.

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

Beispiel

Echtzeitdemonstration

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

Ausgabe

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

Das obige ist der detaillierte Inhalt vonC-Programm Egg Drop Puzzle – DP-11. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!