蛋滴跟踪表 [英] Trace table for egg drop

问题描述

两个蛋的问题:

您将获得2个鸡蛋.
您可以访问100层的建筑物.
鸡蛋可能非常坚硬或非常脆弱，这意味着如果从一楼跌落可能会破裂，甚至从100楼跌落甚至可能不会破裂.两个鸡蛋都是相同的.
您需要弄清楚一栋100层建筑的最高楼层，可以将鸡蛋掉下来而不会破裂.
现在的问题是，您需要滴几滴.在此过程中，您可以打破两个鸡蛋.

You are given 2 eggs.
You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

我知道使用动态编程解决此问题的方法.我想跟踪解决方案以及最少的尝试次数.即我要尝试获得最少尝试次数的楼层.

I know the solution for this problem with dynamic programming. I want to trace the solution along with the minimum number of tries. i.e the floors that I have to try for getting the minimum number of tries.

# include <stdio.h>
# include <limits.h>


// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }


/* Function to get minimum number of trails needed in worst
  case with n eggs and k floors */
int eggDrop(int n, int k)
{
    /* A 2D table where entery eggFloor[i][j] will represent minimum
       number of trials needed for i eggs and j floors. */
    int eggFloor[n+1][k+1];
    int res;
    int i, j, x;

    // We need one trial for one floor and0 trials for 0 floors
    for (i = 1; i <= n; i++)
    {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }

    // We always need j trials for one egg and j floors.
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;

    // Fill rest of the entries in table using optimal substructure
    // property
    for (i = 2; i <= n; i++)
    {
        for (j = 2; j <= k; j++)
        {
            eggFloor[i][j] = INT_MAX;
            for (x = 1; x <= j; x++)
            {
                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                if (res < eggFloor[i][j])
                    eggFloor[i][j] = res;
            }
        }
    }

    // eggFloor[n][k] holds the result
    return eggFloor[n][k];
}

/* Driver program to test to pront printDups*/
int main()
{
    int n = 2, k = 36;
    printf ("\nMinimum number of trials in worst case with %d eggs and "
             "%d floors is %d \n", n, k, eggDrop(n, k));
    return 0;
}

推荐答案

您只需要存储x的值即可为您提供最佳解决方案:

You just need to store the value of x that gives you the optimal solution:

int eggDrop(int n, int k)
{
    /* A 2D table where entery eggFloor[i][j] will represent minimum
       number of trials needed for i eggs and j floors. */
    int eggFloor[n+1][k+1];
    int floor[n+1][k+1];
    int res;
    int i, j, x;

    // We need one trial for one floor and0 trials for 0 floors
    for (i = 1; i <= n; i++)
    {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }

    // We always need j trials for one egg and j floors.
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;

    // Fill rest of the entries in table using optimal substructure
    // property
    for (i = 2; i <= n; i++)
    {
        for (j = 2; j <= k; j++)
        {
            eggFloor[i][j] = INT_MAX;
            for (x = 1; x <= j; x++)
            {
                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                if (res < eggFloor[i][j]) {
                    eggFloor[i][j] = res;
                    floor[i][j] = x;
                }                        
            }
        }
    }

    // eggFloor[n][k] holds the result
    return eggFloor[n][k];
}

最后， floor [i] [j] 包含当您拥有 i 鸡蛋和 j 地板时需要尝试的地板

In the end, floor[i][j] contains the floor you need to try when you have i eggs and j floors.

这篇关于蛋滴跟踪表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！