Задача про 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-этажный дом