3

これは、この質問に関連しています: 2 つのビー玉と 100 階建ての建物 ですが、同じではありません ... 最下階を見つけるために必要な最大ドロップを最小限に抑えるための戦略を理解するための最良のアルゴリズムを見つけなければなりません..

これが私の頭にあるものです

最後のビー玉は段階的に落とさなければならない

残りのビー玉はホップを選択します (ホップ-n と言います)

例えば。したがって、N = 2、M = 100 の場合、最大ドロップ数 = 14、ホップ 1 = 最初のビー玉が最初にドロップされるフロアであることがわかります。

4

2 に答える 2

6

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
于 2013-02-17T09:27:37.627 に答える
4

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

この関数は、計算したいものの逆ですが、これは問題ではありません。関数は単調であるため、結果スペースでバイナリ検索を実行するだけです。

于 2013-02-17T10:46:30.280 に答える