Рубрики

Java-программа для головоломки с яйцом DP-11

Ниже приведено описание случая этой знаменитой головоломки с n = 2 яйцами и зданием с k = 36 этажами.

Предположим, что мы хотим знать, из каких историй в 36-этажном здании безопасно бросать яйца, а какие разбивают яйца при приземлении. Мы делаем несколько предположений:

… Яйцо, которое переживает падение, может быть использовано снова.
… ..Разбитое яйцо нужно выбросить.
… Эффект падения одинаков для всех яиц.
… ..Если яйцо разбивается при падении, то оно сломается при падении с верхнего этажа.
… Если яйцо переживет падение, то оно переживет более короткое падение.
… ..Не исключено, что окна первого этажа разбивают яйца, и не исключено, что на 36-м этаже не разбиваются яйца.

Если доступно только одно яйцо, и мы хотим быть уверенными в получении правильного результата, эксперимент можно провести только одним способом. Бросьте яйцо из окна первого этажа; если он выживет, бросьте его из окна второго этажа. Продолжайте вверх, пока не сломается. В худшем случае этот метод может потребовать 36 помет. Предположим, 2 яйца доступны. Какое наименьшее количество помета для яиц гарантированно работает во всех случаях?
Проблема на самом деле не в том, чтобы найти критический этаж, а просто в определении этажей, с которых следует сбрасывать яйца, чтобы минимизировать общее количество испытаний.

Источник: Wiki для динамического программирования

// Java-программа на основе динамического программирования для головоломки с яйцом

class EggDrop {

    // Вспомогательная функция для получения максимум двух целых

    static int max(int a, int b) { return (a > b) ? a : b; }

  

    / * Функция для получения минимального количества испытаний, необходимых в худшем случае

    ящик с n яйцами и k этажами * /

    static int eggDrop(int n, int k)

    {

        / * 2D-таблица, где entery eggFloor [i] [j] будет представлять минимум

       количество испытаний, необходимых для яиц и я этажей. * /

        int eggFloor[][] = new int[n + 1][k + 1];

        int res;

        int i, j, x;

  

        // Нам нужно одно испытание для одного этажа и 0 испытаний для 0 этажей

        for (i = 1; i <= n; i++) {

            eggFloor[i][1] = 1;

            eggFloor[i][0] = 0;

        }

  

        // Нам всегда нужны j испытаний для одного яйца и j этажей.

        for (j = 1; j <= k; j++)

            eggFloor[1][j] = j;

  

        // Заполняем остальные записи в таблице, используя оптимальную подструктуру

        // свойство

        for (i = 2; i <= n; i++) {

            for (j = 2; j <= k; j++) {

                eggFloor[i][j] = Integer.MAX_VALUE;

                for (x = 1; x <= j; x++) {

                    res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x]);

                    if (res < eggFloor[i][j])

                        eggFloor[i][j] = res;

                }

            }

        }

  

        // eggFloor [n] [k] содержит результат

        return eggFloor[n][k];

    }

  

    / * Программа драйвера для проверки на печать printDups * /

    public static void main(String args[])

    {

        int n = 2, k = 10;

        System.out.println("Minimum number of trials in "+

                           "worst case with "

                           + n + "  eggs and " + k + " floors is " + eggDrop(n, k));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

Minimum number of trials in worst case with 2  eggs and 10 floors is 4

Пожалуйста, ознакомьтесь с полной статьей о яйце капли головоломки | DP-11 для более подробной информации!

Рекомендуемые посты:

Java-программа для головоломки с яйцом DP-11

0.00 (0%) 0 votes