: Есть здание высотой 90 этажей. И есть две одинаковые тарелки. При сбрасывании с определенного этажа тарелка бьется или не бьется. Нужно определить с какого этажа тарелки начинают биться. Самый простой способ сделать это - это начать с первого этажа и идти вверх бросая тарелку пока она не разобьется. Но таким методом в худшем случае мы будем вынуждены сделать 90 бросков (если тарелка очень прочная). Нужно придумать алгоритм бросания, чтобы гарантированно минимизировать число бросков за которые мы определим этаж с которого тарелки начинают биться.
:
Разбиваем все этажи на P групп по K этажей, в группу с номером P+1 попадают последние этажи, невошедшие в первые P групп. Стратегия: кидаем первую тарелку с последнего этажа каждой группы, начиная с группы 1. Если тарелка бьется, то "проходим" второй тарелкой все этажи этой группы снизу вверх. Итак, максимальное количество бросков первой тарелки равно очевидно P, тогда всего для определения искомого этажа потребуется P+K-1 бросок, число P вычисляем по формуле P=\целая_часть(90/K).
Итого при K=1 бросков 90
K=2 бросков 46
K=3 бросков 32
K=4 бросков 25
K=5 бросков 22
K=6 бросков 20
K=7 бросков 18
K=8 бросков 18
K=9 бросков 18
K=10 бросков 18
K=11 бросков 18
K=12 бросков 18
K=13 бросков 18
K=14 бросков 18
K=15 бросков 19
......
K=89 бросков 89
K=90 бросков 90
| Задача про тарелки. - Drauk , 30.11.2004 18:56 MSK |
