Задача про 100-этажный дом

Имеется 100-этажное здание и две стеклянные бутылки. Если выбросить бутылку из окна какого-нибудь этажа, то она или разобьется или нет. За какое минимальное количество бросков можно определить этаж, начиная с которого, бутылки разбиваются? Не разбившуюся бутылку можно бросать повторно.

1. Бинарный поиск не подходит т.к. бутылки всего две.

2. Решение в общем виде сводится к следующему:

— мы разделяем здание на секции (например, 10 секций по 10 этажей).

— используем первую бутылку, чтобы определить в какой секции бутылки начинают разбиваться, (т.е. бросаем бутылку с 10, 20, 30, … , 100 этажа, пока не разобьется, или же если не разбивается на 100-м этаже, значит крепкие бутылки оказались).

— используем вторую бутылку, чтобы определить конкретный этаж секции (т.е. например бутылка разбилась на 40 этаже; начиная с 31 этажа и выше последовательно бросаем вторую бутылку, пока не определим искомый этаж).

В данном примере максимальное количество бросков составит 19 раз (т.е. в худшем случае 10 секций = 10 раз + 9 раз для перебора всех этажей в секции).

Теперь рассмотрим вариант более оптимального разделения этажей здания.

Упростим задачу. Пусть будет одноэтажный дом. Сколько потребуется бросков? Один. А если два этажа? Два броска. А если три?

| 1 | 2 | 3 |

Если будет одна секция (т.е. все три этажа в одной секции), то следуя вышеуказанному алгоритму, бросаем с 3, этажа, если разбивается, бросаем с 1-го, если не разбивается, бросаем со 2-го. Получается 3 броска.

Разделим на две секции

| 1 | 2 |    | 3 |     (можно и так    | 1 |     | 2 | 3 |  но в данном случае все равно 3 броска — с 1-го, 3-го, 2-го, т.е. не годится)

Итак, бросаем со 2-го, не разбилась — бросаем с 3-го, разбилась — бросаем с 1-го. Итого 2 броска.

Далее, путем увеличения количества этажей и перебора возможных вариантов их разделения на секции, можно сделать несколько выводов:

1. Наиболее оптимальным является такое разделение, что каждая последующая секция содержит на 1 этаж меньше, чем предыдущая (если секция последняя, то она содержит все оставшиеся этажи).

2. Максимальное количество бросков равно количеству этажей в самой первой секции.

3. Появляется некая закономерность, не ясно только как ее вычислить

Кол-во этажей | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | … | 100 |…

—————————————————————————————————————————————

Кол-во бросков | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 |  4  |  5  |  5  |  5  |  5  |  5  |  6  |  6  |  6  |  6  |  6  |  6  |  7  | … |  14  |…

Таким образом, 100-этажное здание мы разделяем, на следующие 12 секций (первая секция 14 этажей, вторая 13, и т.д., последняя 1 этаж)

| 1 .. 14 |  | 15 .. 27 |  | 28 .. 39 |  | 40 .. 50 | | 51 .. 60 |  | 61 .. 69 | | 70 .. 77 |  | 78 .. 84 |  | 85 .. 90 |  | 91 .. 95 | | 96 .. 99 | | 100 |

При таком разделении максимальное число бросков будет равно 14.

А сам метод поиска минимального количества бросков может выглядеть как-то так


int CalculateAttempts(int floors)
{
int sum = 0, i = 1;
for (; i <= floors; i++)
{
sum += i;
if (sum >= floors) return i;
}
return -1;
}

Реклама
Задача про 100-этажный дом

Задача про 100-этажный дом: Один комментарий

  1. Александр:

    Эту задачу можно обобщить на любое произвольное бутылок и произвольное число этажей. Только решать её нужно с другой стороны: задавать не число этажей, а число бросаний, которые разрешено сделать. В этом случае можно вычислить наибольшее число этажей, которое может иметь дом, чтобы заданного числа бутылок и заданного числа бросков хватило для определения этажа, бросок с которого разбивает бутылку. А если бутылки такие прочные, что им нужно более высокое здание, то нужно требовать увеличения числа допустимых бросков или числа разбитых бутылок. Понятно, что число бутылок не должно превышать число бросков. Для двух бутылок и четырнадцати бросков здание может иметь высоту не более 105 этажей, а например, для четырёх бутылок и восьми бросков высота может быть 162 этажа.

    Нравится

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s