2 Kreativshik Согласен, есть ошибка в логике взвешиваний, буду думать дальше.
Ваш поиск так же не верен, или я его не до конца понял. Привожу пример. Монеты лежат в следующей последовательности масс: 10,1,2,3,4,5,6,7,8,9,13,12,11 1) взвешиваем монету №1 - 10 (10 это вес) 2) взвешиваем монету №(1+5) - 5 - максимальная монета №1 3) взвешиваем монету №(1+3) - 3 - максимальная монета №1 4) взвешиваем монету №(1+2) - 2 - максимальная монета №1 5) взвешиваем монету №(1+1) - 1 - максимальная монета №1 6) взвешиваем монету №(1+1) - 1 - максимальная монета №1 максимальная монета №1 массой 10, однако ближайшие к ней монеты массой 1 и 11, и это не есть правильный ответ. Давайте думать дальше... (или укажите если я не правильно понял ваш метод).
Сообщение отредактировал freews - Сб, 29.06.13, 23:43
Начиная с третьего пункта вы ошиблись. В моем решении ясно сказано, что монеты отсчитываются в сторону наибольшего шага. Вы же считали монеты все время в сторону меньшего шага. Шаг - это расстояние между соседними взвешенными монетами. Вот давайте рассмотрим Ваш пример. Монеты расположены по кругу и имеют веса указанные вами. Вы выбрали монету вес которой оказался 10 далее мы отсчитываем пять монет в любую сторону и взвешиваем монету на которой остановили счет. В Вашем случае это монета с весом 5. Определяем среди них тяжелую,- это понятно первая монета с весом десять,- от нее в сторону большего шага(шаг меду первой и второй взвешенной монетой составляет четыре невзвешенных монеты в одну сторону, а в другую семь,- вот в эту сторону и отсчитываем) отсчитываем три монеты. Попадаем на монету с весом 13. Она имеет наибольший вес среди уже взвешенных, поэтому отсчитываем уже от нее. Как показывает алгоритм, необходимо отсчитать две монеты в сторону большего шага, в одну сторону он составляет две монеты, а в другую четыре - туда то и считаем. Отсчитываем две монеты, попадаем на монету с весом 8. Среди взвешенных больший вес понятно у какой, от нее и отсчитываем одну монету опять в сторону большего шага, попадаем соответственно на монету с весом 12. Ну и опять отсчитываем от самой тяжелой среди уже взвешенных одну монету в сторону, естественно, наибольшего шага, в одну сторону он составляет 0, а в другую 1. То бишь попадаем мы на монету с весом 9. Определяем среди взвешенных самую тяжелую, она и есть решение. Теперь надеюсь ясности в предложенный алгоритм я внес?! Выбирайте веса на ваш вкус и проверяйте алгоритм пока не надоест, он все равно будет работать как швейцарские часы, ведь математика эт наука точная. Кстати, а причем тут математика, кто знает?
Kreativshik, спасибо, я теперь понял как все реализовано. Данный метод действительно не ищет самую тяжелую монету, а находит более тяжелую относительно двух соседних, именно так как написано в задании (и это не обязательно будет самая тяжелая монета, как повезет). Здесь для поиска монеты используется метод золотого сечения.
