Рубрики

C # Программа для пазла с яйцом DP-11

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

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

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

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

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

// Программа C # на основе динамического программирования
// для головоломки с яйцом

using System;

  

class GFG {

  

    // Функция полезности, чтобы получить максимум

    // два целых числа

    static int max(int a, int b)

    {

        return (a > b) ? a : b;

    }

  

    / * Функция для получения минимального количества

    испытания нужны в худшем случае с п

    яйца и k этажей * /

    static int eggDrop(int n, int k)

    {

  

        / * 2D-таблица, где Entery eggFloor [i] [j]

        будет представлять минимальное количество испытаний

        нужны для яиц и 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] = int.MaxValue;

                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];

    }

  

    // Функция драйвера

    public static void Main()

    {

        int n = 2, k = 36;

        Console.WriteLine("Minimum number of trials "

                          + "in worst case with " + n + " eggs and "

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

    }

}

  
// Этот код предоставлен Sam007.

Выход:

Minimum number of trials in worst case with 2 eggs and 36floors is 8

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

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

C # Программа для пазла с яйцом DP-11

0.00 (0%) 0 votes