alt text

задан 22 Янв '15 1:01

@Leva319, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

(6 Июн '15 13:06) Виталина
10|600 символов нужно символов осталось
3

Несложная же задача. Удивительно, что никто не ответил.

Рассмотрим алгоритм взвешиваний как турнир по олимпийской системе. В первом "туре" все монеты разбиты на пары, кроме, возможно, одной монеты, которая считается сразу "вышедшей во второй тур". Во второй тур выходят более тяжелые монеты. Во втором туре на пары разбиваются все вышедшие в него, и снова в следующий тур выходят более тяжёлые. Так как каждое взвешивание отсеивает ровно одну монету, то для определения победителя турнира (самой тяжелой монеты) нужно ровно n-1 взвешивание. При этом число туров равно log2(n) (возможно,+1).

Теперь дополнительно проделаем еще несколько взвешиваний, чтобы найти вторую по тяжести монету. Ясно, что ей может оказаться только такая монета, которая "проиграла" взвешивание самой тяжёлой монете: все прочие монеты проиграли взвешивание какой-то еще монете, поэтому не могут оказаться вторыми. Таких "кандидатов во вторые монеты" не больше, чем число туров, поскольку самая тяжелая монета в каждом туре выбивала не более одной другой монеты. Значит, достаточно еще log2(n) сравнений на определение второй по весу монеты.

Всё.

ссылка

отвечен 5 Июн '15 13:57

@knop: решение действительно несложное (это всё-таки не получение нижней оценки или чего-то ещё). Я обычно на вопросы такого рода охотно отвечаю, но сейчас посмотрел по дате -- в эти дни лежал в больнице, поэтому условие воспринял сейчас как абсолютно новое.

(5 Июн '15 18:00) falcao

Я сегодня прокомментировал и одну задачку, где была нижняя оценка... math.hashcode.ru/questions/64568/

(5 Июн '15 18:10) knop

@knop: да, я видел это решение. Я когда над ней думал, то в итоге получил этот ответ, и понял, почему он верен, но оформлять в виде решения не стал.

(5 Июн '15 18:40) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×366
×29

задан
22 Янв '15 1:01

показан
487 раз

обновлен
6 Июн '15 13:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru