Last active
January 14, 2017 04:12
-
-
Save jonpchin/4704734f6a696ba04d885d068f16360e to your computer and use it in GitHub Desktop.
Classical Egg Drop problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Jonathan Chin | |
| // 11/15/15 | |
| // Classical Egg drop problem, using dynamic programming | |
| #include <stdio.h> | |
| #include <limits.h> | |
| #define MAX(a, b)( ((a)>(b)) ? (a) : (b)) | |
| void eggdrop(int eggs, int height); | |
| int main(){ | |
| int eggs; | |
| int floor; | |
| printf("Please enter the total number of eggs and floors.\n"); | |
| scanf("%d %d", &eggs, &height); | |
| eggdrop(eggs, height); | |
| return 0; | |
| } | |
| void eggdrop(int eggs, int height){ | |
| int floors[eggs+1][height+1]; | |
| int result; | |
| int i, j, k; | |
| //there will be one trial for one floor and zero trials for zero floors | |
| for(i=1; i<=eggs; i++){ | |
| floors[i][1]=1; | |
| floors[i][0]=0; | |
| } | |
| //always need j trials for j floors and one egg | |
| for(i=1; i<=height; i++){ | |
| floors[1][i]=i; | |
| } | |
| for(i=2; i<=eggs; i++){ | |
| for(j=2; j<=height; j++){ | |
| floors[i][j] = INT_MAX; | |
| for(k=1; k<=j; k++){ | |
| result = 1 + MAX(floors[i-1][k-1], floors[i][j-k]); | |
| if(floors[i][j] > result){ | |
| floors[i][j] = result; | |
| } | |
| } | |
| } | |
| } | |
| printf("The minnimum number of trials to drop the egg with %d eggs and %d floors is %d\n", eggs, height, floors[eggs][floor]); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment