algorithm - 给定 N 个弹珠和 M 个楼层，找出算法找出弹珠会从哪个最低楼层破裂

Question

它与这个问题有关：两颗弹珠和一座 100 层的建筑 ，但它不一样......我们要找出最好的算法来找出答案，最小化找到最低楼层所需的最大下降的策略..

这是我的想法

最后一块大理石必须以逐步的方式掉落

其余的弹珠会选择一跳（比如 hop-n）

例如。因此，当 N = 2，M = 100 时，我们知道最大掉落数 = 14，并且 hop-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

可以用 M 个弹珠和 D 个掉落物探索的楼层 F 为

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 */

此函数与您要计算的相反，但这不是问题。该函数是单调的，因此只需在结果空间中进行二进制搜索。