Учитывая N мрамора и M этажей, найдите алгоритм, чтобы найти самый нижний этаж, с которого мрамор будет разбиваться

Question

Это связано с этим вопросом: два мрамора и 100-этажное здание, НО это не одно и то же... Мы должны выяснить лучший алгоритм, чтобы выяснить, стратегия, чтобы минимизировать максимальное количество падений, необходимое для нахождения нижнего этажа.

Вот что у меня на уме

Последний мрамор должен быть сброшен поэтапно

Остальные шарики выберут хмель (скажем, хоп-н)

например. Поэтому, когда N = 2, M = 100, мы знаем, что максимальное падение =14, а прыжок-1 = пол, с которого первый мрамор будет сброшен в самый первый раз.

Answer 1

Вот простое грубое решение, написанное на Java:

/**
 * Return maximum number of floors that could be checked with given number
 * of marbles and drops.
 */
private static int getMaximumFloors (int marblesCount, int dropsCount)
{
    if (marblesCount == 0) return 0;
    else
    {
        int result = 0;

        for (int i = 0; i < dropsCount; i++)
        {
            result += getMaximumFloors (marblesCount - 1, i) + 1;
        }

        return result;
    }
}

/**
 * Return minimum number of drops that is definitely enough to check
 * given number of floors having given number of marbles.
 */
private static int getMinimumDrops (int marblesCount, int floorsCount)
{
    int dropsCount = 0;
    while (getMaximumFloors (marblesCount, dropsCount) < floorsCount)
        dropsCount += 1;
    return dropsCount;
}

public static void main (String [] args)
{
    System.out.println (getMinimumDrops (2, 100));
}

Должно быть легко перенести его на C/C++.

Вот некоторые результаты:

2 marbles, 100 floors -> 14
3 marbles, 100 floors -> 9
4 marbles, 100 floors -> 8
5 marbles, 100 floors -> 7
6 marbles, 100 floors -> 7

Answer 2

Количество этажей F, которые можно исследовать с помощью M мрамора и D капель, составляет

F(0,D) = 0 /* no marbles, no results */
F(M,0) = 0 /* no drops, no results */

F(M,D) = 1 + /* we drop a marble once... */
    F(M-1,D-1) + /* it breaks ... */
    F(M,D-1) /* or it doesn't */

Эта функция противоположна тому, что вы хотите вычислить, но это не проблема. Функция является монотонной, поэтому просто выполните бинарный поиск в пространстве результатов.