Поздравляю всех с началом учебного года!
Раз такое дело, то давайте и мы узнаем продолжение решения задачи о взвешиваниях.
Мы остановились на том, что меньше четырёх гирек заведомо мало, а шести хватает. Давайте попробуем найти способ представить любой вес от 1 до 40 четырьмя гирьками.
Пусть одна гирька весит x килограммов. Тогда она одна поможет нам взвесить x, 0 или -x килограммов. В самом деле, гирьку ведь можно класть на ту же чашу весов, что и груз!
Можно считать, что положение наших гирек описывается троичными битами (битами с тремя состояниями). Тогда сразу возникает желание сделать и веса гирек степенями тройки (1, 3, 9, 27) и подумать. И оказывается, что думать-то после этого уже не надо :)
Легко убедится, что этих гирек хватит, чтобы выразить любой целый вес от 1 до 40 :)
Скоро я вернусь с кучей впечатлений, буду делиться :)
До встречи! И хорошей недели!
Здравствуйте, а не могли бы вы по подробней объяснить как "x, 0 или -x килограммов" увязывается со степенями чила 3. Спасибо.
ОтветитьУдалитьkrilya, спасибо за вопрос. Я подготовлю понятную иллюстрацию, потому что словами коротко объяснить не получается. В одной из следующих заметок мы обсудим детали решения.
ОтветитьУдалитьЛучше поздно, чем никогда - обещанное объяснение (я не смог придумать хорошую иллюстрацию, поэтому всё текстом)
ОтветитьУдалитьК решению можно прийти из более прозрачных (как по мне) размышлений.
ОтветитьУдалитьЕстественно нужно взять гирю в 1кг. Далее будем рассматривать вес по нарастанию и, если не хватает нашего набора, будем получать его вычитанием наших гирь из новой гири.
На деле:
набор {1}
2=3-1 (набор {1,3}, из него имеем 1-4)
5=9-4 ({1,3,9}, имеем 1-13)
14=27-13 ({1,3,9,27}, имеем 1-40)
Уважаемый аноним, спасибо за короткое изложение подхода к задаче!
ОтветитьУдалить