Предлагаю вашему вниманию некоторые упражнения из учебника информатики 1990 года. Возможно, кому-то они покажутся интересными, а кому-то окажутся даже полезны.

Опишите точный план действий, приводящий к решению следующих задач:

1.     Волк, коза и капуста. На берегу реки стоит крестьянин, а рядом с ним - волк, коза и капуста. Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако, в лодку, кроме крестьянина, помещается либо только коза, либо только волк, либо только капуста. Оставлять же волка с козой или козу с капустой без присмотра нельзя - волк может съесть козу, а коза - капусту. Как должен вести себя крестьянин?
Ответ от меня: он должен хорошо себя вести. :-)


2.     Два встречных поезда, в каждом из которых паровоз и 21 вагон, встретились на дороге с одним тупиком. В тупик вмещается 11 вагонов или 10 вагонов и паровоз. Как поездам разъехаться (т.е. как должны маневрировать машинисты, чтобы каждый поезд продолжил движение в своем направлении)?


3.     Ханойская башня. На подставке укреплены три стержня, на левый стержень нанизано несколько колец уменьшающегося размера - внизу самое большое кольцо, на нем поменьше, сверху еще меньше и т.п. (см. рис.).

Надо, перемещая по одному кольцу со стержня на стержень, переместить все кольца на правый стержень, но при этом ни в какой момент времени большое кольцо на меньшее класть нельзя. Опишите, как надо перекладывать кольца, если в начальный момент на левом стержне: а) 1; б) 2; в) 3; г) 4; д) 64 кольца. (По преданию, перекладыванием 64 колец занимаются монахи в одном из буддийских монастырей. Согласно легенде, в момент, когда они кончат перекладывать кольца, наступит конец света. Прикиньте приблизительно, когда это произойдет, если считать, что монахи перекладывают примерно 1 кольцо в секунду.)
Примечание от меня: Ни в коем случае нельзя давать этим монахам в руки даже какой-нибудь "Урал-16"!!! :-)


4.     Фирма "Электронные приборы" выпустила автоматизированную ванну "Банный комплекс-10", управляемую с помощью 10 кнопок "долить 1 л", "долить 2 л", ..., "долить 5 л", "слить 1 л", "слить 2 л", ..., "слить 5 л", при нажатии на которые доливается или сливается указанное еоличество литров воды. Однако, в результате ошибки фирмы, все кнопки, кроме "долить 5 л" и "слить 3 л", не работают. Как долить в ванну 3 воды? Сколько воды при этом пропадет впустую из-за брака фирмы?


5.     Два солдата подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата, либо двух мальчиков, а солдата и мальчика уже не вмещает?


6.     Петя и Коля играют в следующую игру: на стол кладется 15 спичек. Ребята по очереди берут их со стола, причем, за один ход разрешается взять только 1, 2 или 3 спички. Выигрывает тот, кто возьмет последнюю спичку. Первым ходит Петя. Как он должен играть, чтобы выиграть?
Примечание от меня: спички детям... сами знаете!


7.     Есть двое песочных часов: на 3 минуты и на 8 минут. Для приготовления элексира бессмертия его надо варить ровно 7 минут. Как это сделать?


8.     Автоматическое устройство имеет 2 кнопки и экран. При включении на экране загорается число 0. При нажатии на одну кнопку число на экране удваивается (вместо х появляется 2х). При нажатии на другую кнопку число увеличивается на 1 (вместо х появляется х+1). Как нужно нажимать на кнопки, чтобы на экране появилось: а) число 5; б) число 99; в) число 99, если разрешается нажимать на кнопки не больше 10 раз?


9.     Придумайте способ нахождения самой легкой и самой тяжелой из 100 монет различной массы, если можно сделать не более 150 взвешиваний на чашечных весах без гирь.


10.     Имеется а) 3, б) 4, в) 5, г) 6 монет, среди которых одна фальшивая (легче других). Придумайте способ нахождения фальшивой монеты за минимальное количество взвешиваний на чашечных весах без гирь.


11.     Имеется 1000 монет, из которых одна фальшивая (легче других). Придумайте способ нахождения фальшивой монеты за 7 взвешиваний на чашечных весах без гирь. Докажите, что нельзя придумать способ, который гарантирует нахождение фальшивой монеты за 6 взвешиваний.


12.     Среди 2n+1 различных по массе монет нужно найти среднюю (т.е. такую, которая тяжелее n монет и легче других n монет). Придумайте, как это сделать не более, чем за 100n взвешиваний на чашечных весах без гирь.

А.Г. Кушниренко, Г.В. Лебедев, Р.А. Сворень "Основы информатики и вычислительной техники". Пробный учебник для средних учебных заведений; М. "П." 1990.