Teka-teki Titisan Telur C Program

Teka-teki Titisan Telur C Program - DP-11

王林

Lepaskan： 2023-08-30 11:53:03

ke hadapan

571 orang telah melayarinya

C程序的蛋掉落谜题 - DP-11

Ini adalah teka-teki yang terkenal. Katakan terdapat sebuah bangunan dengan n tingkat, jika kita mempunyai m telur, maka bagaimana kita mencari bilangan titisan minimum yang diperlukan ke lantai di mana kita boleh menjatuhkan telur dengan selamat tanpa memecahkannya.

Ada beberapa perkara penting yang perlu diingat -

Apabila telur tidak retak dari lantai tertentu, maka ia tidak akan retak dari mana-mana tingkat bawah pun.
Jika telur pecah dari lantai tertentu, maka ia juga akan pecah pada semua tingkat di atas.
Bila pecah telur mesti dibuang atau kita boleh guna semula.

Masukkan- bilangan telur dan lantai maksimum. Andaikan bilangan telur ialah 4 dan tingkat maksimum ialah 10.

Output- Bilangan minimum percubaan 4.

Algoritma

eggTrialCount(telur, lantai)

Input− bilangan telur, lantai maksimum.

Output − Dapatkan bilangan minimum ujian telur.

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] := &infin;
         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

Salin selepas log masuk

Contoh

Demonstrasi masa nyata

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

Salin selepas log masuk

Output

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

Salin selepas log masuk

Atas ialah kandungan terperinci Teka-teki Titisan Telur C Program - DP-11. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!