@rd100

Какой алгоритм используется при возможности 2 неудачных попыток?

Ученые разработали новый материал неизвестной прочности.
Они знают, что материал разбивается при падении с высоты от 1 метра до 5000 метров. Но не знают, с какой именно высоты.
Чтобы определить прочность, ученые поднимают предмет на некоторую высоту и сбрасывают его оттуда.
Их задача определить начиная с какой именно высоты предмет начнет разбиваться.
Специальная платформа, с помощью которой они осуществляют эксперимент скидывает предмет только с дискретных высот (1, 2, 3 ... 4999, 5000 метров - платформа не может скинуть предмет, например, с 2.5 метров. Точности в 1 метр ученым вполне достаточно).
При падении с высоты "n" метров предмет уничтожается. Если же его сбрасывали с высоты ниже "n", то его можно использовать в повторных экспериментах.


Нужен пример, каким образом можно это устроить, при наличии всего 2 неудачных попыток.
И сколько для этого понадобится максимальное число попыток?
  • Вопрос задан
  • 624 просмотра
Решения вопроса 3
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Какой угодно. Раз у задачи нет цели на минимизацию чего-либо, значит можно просто кидать один предмет с метра, двух, трёх и т.д., пока не разобъётся.
Ответ написан
@Akina
Сетевой и системный админ, SQL-программист.
Для бОльшей понятности условия будем считать что у нас есть 2 предмета. Оба разбились - эксперименты кончились. И будем считать, что задача - получить ответ за минимальное количество бросков.

Рассмотрим, что у нас есть только один предмет. Очевидно, что придётся его кидать с 1 метра, с 2, с 3... пока не разобьётся. Максимум будет 5000 бросков.

Но у нас есть 2 предмета.

Тогда мы можем бросить первый не с 1 метра, а сразу с какого-то N. Если он разобьётся, то придётся второй кидать с 1, 2, ... и по максимуму второй кинем N-1 раз. а всего будет N бросков.

Но если он не разбился, то мы можем бросить первый уже с бОльшей высоты. Какой? Допустим, он разобьётся. Чтобы получить по максимуму те же N бросков, второй предмет мы уже может бросить N-2 раз, а, значит, первый предмет надо сбрасывать с высоты N+(N-1).

Если первый снова не разбился, на следующем шаге его можно сбросить с высоты N+(N-1)+(N-2)... и так далее.

Лишнего нам тоже не надо. А, значит, надо подобрать такое наименьшее N, при котором N-й бросок первого предмета будет с 5000 метров или выше.

Итого - имеем N+(N-1)+(N-2)+...+1 >= 5000. Сумму арифметической прогрессии знаем, квадратные уравнения решать умеем. Получаем N=100.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Предполагаю, что это известная задача, где надо минимизировать количество бросков в хужшем сулчае. Задача решается динамическим программированием.

Пусть C(n,k) - сколько надо в худшем случае бросков, если мы знаем, что предмет разбивается при бросании с 1..n и можно сделать k неудачных бросков.

С(n,k) = min_i=1..n-1 ( max(C(i,k-1), C(n-i, k)) )) + 1


База - C(1, k) = 0; C(n, 1) = n-1.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы