valchkou wrote:
Может математики подскажут формулу для правильно расчета распределения.
Я для себя считаю упрощенной формулой n = sqrt(2*m)
где n начальный этаж и соотв макс кол-во попыток, а m кол-во этажей.
100 - 14 (14.14...)
30 - 8 (7.7...)
Я изложу общее решение.
Решим немного другую задачу. Найдем максимальное количество этажей, которые можно гарантированно проверить за К бросков. Назовем эту величину N(K).
Если всего бросков К, то с какого этажа нужно сделать первый бросок? Нельзя бросать с K+1-го этажа или выше, потому что если диск разобьется, то оставшихся K-1 бросков может не хватить на проверку >=К этажей. Если сбросить с К-го этажа и диск разобьется, то останется ровно необходимые К-1 бросков на проверку оставшихся этажей с 1-го по К-1-й. Ну а бросать с К-1-го и ниже не имеет смысла, если можно бросить с более высокого. Следовательно, первый бросок нужно делать именно с К-го этажа.
Далее рассуждаем аналогично. Если после первого броска у нас по прежнему два целых диска, то остается К-1 бросок и, следовательно, второй бросок нам нужно следать с (К+К-1)-го этажа. Если диск разобьется, то остается К-2 броска и (К+К-1)-K-1 = К-2 этажей для проверки. Третий бросок нужно делать с (К+К-1+К-2)-го этажа и т.д.
Последний, К-й бросок нужно сделать с (K+(K-1)+(К-2)+...+1)-го этажа.
Итак, мы нашли форумулу -
N(K) = K+(K-1)+(К-2)+...+1 = (К+1)К/2
При данном N и неизвестном К нужно найти такое К, чтобы выполнялось неравенство К(К-1)/2 < N <= (К+1)К/2.
Для N=30 будет К=8, для N=100 будет К=14.
Ну и легко заметить, что величина K^2/2 всегда будет удовлетворять неравенству, так что ваша формула n = sqrt(2*m) выглядит верной.
П.С. Задачка со звездочкой. Найти общее решение для случае N этажей и К дисков.
не вижу проблем, часть с хешмепом обычно за 30 секунд заканчиватеся.
