Рубрики

C Программа для головоломки с яйцом | DP-11

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

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

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

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

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

// Программа C ++ на основе динамического программирования для головоломки с яйцом
#include <limits.h>
#include <stdio.h>

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

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

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

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

int eggDrop(int n, int k)

{

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

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

    int eggFloor[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_MAX;

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

int main()

{

    int n = 2, k = 36;

    printf("nMinimum number of trials in worst case with %d eggs and "

           "%d floors is %d \n",

           n, k, eggDrop(n, k));

    return 0;

}

Выход:

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

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

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

C Программа для головоломки с яйцом | DP-11

0.00 (0%) 0 votes