Интересные ссылки

Алгоритмическая задача Песочные часы

Продолжаем решать интересные задачи. Но это алгоритмическая задача. На этот раз используем песочные часы.

Профессор. Предположим, у нас есть двое песочных часов, позволяющих отмерить соответственно 7 и 11 минут. Возможно ли с их помощью отмерить временной интервал в 15 минут? Если да, то как?

Простак. К сожалению, мы не можем отмерить с помощью одних часов половину или какую-нибудь другую часть того интервала, на который они рассчитаны. Поэтому мы можем отмерить только 7, 11 и 7 + 11 = 18 минут.

Зануда. Не только. Кроме того, мы можем отмерить еще и интервал, равный 11 - 7 = 4 минутам. Для этого достаточно запустить двое часов одновременно, и как только весь песок в 7-минутных часах высыпется, в 11-минутных его еще останется на 4 минуты. В этот момент вы можете положить песочные часы набок, чтобы прекратить утечку песка, а затем, когда понадобится, снова поставить их в вертикальное положение. При этом остаток песка на 4 минуты, разумеется, должен находиться в верхней полуколбе часов.

Простак. Но этот 4-минутный остаток песка находится в 11-минутных часах. Следовательно, мы не сможем сначала отмерить 11 минут и вслед за этим еще 4 минуты, чтобы в сумме получилось 15.

Зануда. Значит необходимо "перенести" этот 4-минутный остаток в 7-минутные часы.

Простак. А как это сделать?

Зануда. Просто запустить 7-минутные песочные часы заново, когда в 11-минутных часах в верхней колбе останется песка на 4 минуты. Как только весь песок в 11-минутных часах окажется в нижней полуколбе, в 7-минутных часах внизу будет песка ровно на 4 минуты. Можете положить эти часы набок, чтобы сохранить их состояние до нужного момента. Теперь все готово к тому, чтобы отмерить 15 минут. Для этого следует сначала запустить 11-минутные часы, а после, когда весь их песок окажется внизу, привести в действие 7-минутные песочные часы с остатком песка в верхней полуколбе на 4 минуты. Вот и все!

Профессор. Отлично! Теперь я знаю, что вам не составит ocoбого труда отмерить 10 минут. Попробуйте на досуге разработать соответствующий алгоритм.

Статья подготовлена по материалам книги Вадима Дунаева                «Занимательная математика. Множества и отношения». И еще одна алгоритмическая задача! Читайте ЗДЕСЬ! До встречи!