Имея N шариков и M этажей, найдите алгоритм нахождения нижнего этажа, от которого мог бы разбиться шарик.

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

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

Последний шарик нужно бросать поэтапно.

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

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


algorithm puzzle
person Ajeet Ganga    schedule 17.02.2013    source источник
comment
Это математическая задача, а не задача разработки, и размещение ответа здесь, вероятно, сделает ее менее интересной для других.   -  person Mikhail Vladimirov    schedule 17.02.2013
comment
Вероятно, вы хотите std::find_lowest_marble_break_floor. Ой, подождите, C++ ничего не знает о проблемах мрамора.   -  person juanchopanza    schedule 17.02.2013
comment
@MikhailVladimirov: я тебя не понял. Вы думаете, что алгоритм для вывода этого будет чисто математической работой?   -  person Ajeet Ganga    schedule 17.02.2013
comment
@Ajeet Суть в том, что это математическая / логическая / алгоритмическая проблема, и SO занимается в первую очередь проблемами реализации или проблемами, связанными с кодом, поэтому это скорее не по теме.   -  person Karthik T    schedule 17.02.2013

Ответы (2)


arrow_upward
6
arrow_downward

Вот простое решение грубой силы, написанное на 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
person Mikhail Vladimirov    schedule 17.02.2013
comment
Я не java-парень; можете ли вы разделить сумму на (2, 100) и (3, 100). также Сложность. - person SparKot; 17.02.2013
comment
Конечно, добавлено к ответу. Сложность — это, конечно, плохо, потому что это грубая сила. Я думаю, что свести этот алгоритм к прямой формуле — хорошая математическая задача. По крайней мере, для одного и двух шариков это легко. - person Mikhail Vladimirov; 17.02.2013
comment
В качестве объяснения того, что делает код: максимальное количество этажей, которые можно исследовать с помощью n шариков и m капель, равно Sum[i1 = 1..m] (Sum [i2 = 1..i1] (... Sum[in = 1..i(n-1)](in))...) (n слоев сумм). Стратегия для 1-го шарика, мы начнем падать с пола, рассчитанного путем установки i1 = m, затем i1 = m-1..m и т. д. в уравнении, пока он не сломается. Последующий мрамор также падает с большего этажа на меньший, рассчитанный по приведенному выше уравнению, но зачищенный от внешних слоев. - person nhahtdh; 17.02.2013

arrow_upward
4
arrow_downward

Количество этажей 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 */

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

person n. 1.8e9-where's-my-share m.    schedule 17.02.2013