28 авг. 2008 г.

Оптимизируем

В прошлой заметке была сформулирована оптимизационная проблема: надо выбрать как можно меньше гирек, чтобы иметь возможность отвесить любое целое количество килограммов от 1 до 40.

Ясно, что если взять гири 1, 2, 4, 8, 16 и 32 килограмма, то можно работать с любым весом от 1 до 63 килограммов. Но можно ли обойтись меньшим количеством гирек?

Как мы уже разбирали, надо смотреть на количество информации. Гирька может иметь одно из трёх состояний: на одной чаше весов, на другой чаше, стоит на столе. А передать нам надо число от 1 до 40.

Двумя гирьками можно закодировать 3х3=9 состояний, тремя - 3х3х3=27 состояний, четырьмя - 3х3х3х3=81 состояние. Другими словами, меньше четырёх гирек точно не хватит. Но можно ли справиться четырьмя?

Надо подумать. И сделаем мы это в следующей заметке :)

А новым подписчикам я напомню, что интересного было в июне:



Хороших выходных!

3 комментария:

  1. Интересно, что больше сорока, уже нужно пять

    ОтветитьУдалить
  2. а если бы нам нужно было отмерять только сыпучие вещества, хватило бы одной гирьки - в 1кг :)

    ОтветитьУдалить
  3. Plushkin Kot,
    До 42 можно уложиться в 4 взвешивания.

    ОтветитьУдалить