给定N个弹珠和M层，发现该算法找到从大理石将打破最低楼层 [英] Given N marbles and M floors, find the algorithm to find the lowest floor from which marble would break

问题描述

这是关系到这个问题：两个弹珠 但它是不一样的... 我们要找出最好的算法计算出，策略，减低找到最底层所需的最大滴..

下面是我在我的脑海顶部

  

最后一个大理石已经在逐步的方式被丢弃

     

休息弹珠会选择跳（比如跳-N）

     

如。因此，当N = 2，M = 100，我们知道，最大滴= 14   和跳-1 =地板从第一大理石将被丢弃的第一次。

解决方案

下面是用Java编写的简单的蛮力解决方案：

  / **
 楼层，可以用给定数目的被检查*返回最大数目
 *大理石和滴。
 * /
私有静态诠释getMaximumFloors（INT marblesCount，INT dropsCount）
{
    如果（marblesCount == 0）返回0;
    其他
    {
        INT结果为0;

        的for（int i = 0; I＆LT; dropsCount;我++）
        {
            结果+ = getMaximumFloors（marblesCount  -  1，I）+ 1;
        }

        返回结果;
    }
}

/ **
 *滴是绝对够检查返回最小数
 *楼层给定数量的具有给定的弹珠数量。
 * /
私有静态诠释getMinimumDrops（INT marblesCount，INT floorsCount）
{
    INT dropsCount = 0;
    而（getMaximumFloors（marblesCount，dropsCount）＆LT; floorsCount）
        dropsCount + = 1;
    返回dropsCount;
}

公共静态无效的主要（字串[] args）
{
    的System.out.println（getMinimumDrops（2，100））;
}
 

这应该很容易将它移植到C / C ++。

下面是一些结果：

  2弹珠，100楼 - ＆GT; 14
3弹珠，100楼 - ＆GT; 9
4弹珠，100楼 - ＆GT; 8
5弹珠，100楼 - ＆GT; 7
6弹珠，100楼 - ＆GT; 7
 

It is related to this questioN : Two marbles BUT it is not the same ... We are to figure out best algorithm to figure out, strategy to minimize maximum drops required to find lowest floor ..

Here is what I have on top of my mind

The last marble has to be dropped in stepwise fashion

Rest of the marbles will choose a hop (say hop-n)

e.g.. So when N = 2, M = 100, We know that maximum drops=14 and hop-1 = the floor from which first marble will be dropped for very first time.

解决方案

Here is simple brute-force solution written in 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));
}

It should be easy to port it to C/C++.

Here are some results:

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

这篇关于给定N个弹珠和M层，发现该算法找到从大理石将打破最低楼层的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！