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

Question

[rd100]

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

Нужен пример, каким образом можно это устроить, при наличии всего 2 неудачных попыток.
И сколько для этого понадобится максимальное число попыток?

Comments

[Adamos]

А в теги этот текст заключен специально, чтобы читатели колупались с прокруткой?
Да шоб вам отвечали в одну строчку...

[WbICHA]

Можно начать с бинарного поиска до первого разбитого предмета, а далее с минимального значения в диапазоне идти вверх до того момента, пока второй предмет не разобьётся.
Впрочем, лучше тогда сразу поделить на 3/4/10 частей и начинать с минимальной, тогда диапазон гарантированно будет меньше.

[Сергей Соколов]

Не полностью текст задачи привели? Задача-то, наверное, на оптимизацию.
Нужна «стоимость» разбитой детали и стоимость лишней попытки.
Что лучше: 1000 раз сбросить или 1 разбить?

[rd100]

Сергей Соколов, нужен пример, каким образом можно это устроить, при наличии всего 2 неудачных попыток. И сколько для этого понадобится максимальное число попыток?

[rd100]

Сергей Соколов, нужен пример, каким образом можно это устроить, при наличии всего 2 неудачных попыток. И сколько для этого понадобится максимальное число попыток?

[Akina]

Так... а где критерий? что оптимизировать-то?

[rd100]

Akina, есть 2 попытки всего разбить.
Нужно узнать, сколько максимально попыток нам может понадобится.

[Akina]

Нужно узнать, сколько максимально попыток нам может понадобится.

Максимально - не ограничено. Стоим и, как дураки, кидаем с метра... миллион раз.
А вот минимальное количество бросков. за которое гарантированно определяется лимит - это имеет смысл. Впрочем, это есть в моём ответе.

Answer 1

[Rsa97]

Какой угодно. Раз у задачи нет цели на минимизацию чего-либо, значит можно просто кидать один предмет с метра, двух, трёх и т.д., пока не разобъётся.

Comments

[rd100]

Нужен пример, каким образом можно это устроить, при наличии всего 2 неудачных попыток.
И сколько для этого понадобится максимальное число попыток?

[Rsa97]

rd100, Бросаем предмет с одного метра. Если не разбился, то бросаем с двух метров. Если не разбился, то бросаем с трёх метров... Если не разбился, то бросаем с 5000 метров.
Максимально 5000 попыток.
Но, раз в задаче нет требований минимизации, то и такой алгоритм сойдёт.

Answer 2

[Akina]

Для бОльшей понятности условия будем считать что у нас есть 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.

Answer 3

[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.

Comments

[rd100]

Если я правильно понял, то каждую предыдущую попытку мы просто умножаем на 2, пока не получим неудачу?
А уже после неудачи начинаем от предыдущей прибавлять по 1?

[Wataru]

rd100, Нет. Напишите программу, подсчитайте С для k=2 Найдите формулу, посмотрите при каких i находится минимальное значение.