给定N个大理石和M个楼层,找到算法找到大理石破碎的最低楼层

Question

它与这个问题有关:两个大理石和一个100层的建筑, 但它不一样......我们要弄清楚最好的算法来弄清楚,最小化找到最低楼层所需的最大跌幅的策略.

这就是我的想法

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

其余的弹珠将选择一跳(比如hop-n)

例如.因此,当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