2 классические школьные задачи - оказывается, их ещё решают...

Волк, коза и капуста; устройство с двумя кнопками (2x и x+1)

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

Задача очень проста, если учесть, что перевозить объекты можно не только "туда", но и "обратно". Второе соображение - существует единственное "безопасное" сочетание двух объектов из трех - волк и капуста.

Поэтому решение таково:

 1)перевезти козу туда;
 2)вернуться обратно;
 3)перевезти капусту туда;
 4)перевезти козу обратно;
 5)перевезти волка туда;
 6)вернуться обратно;
 7)перевезти козу туда;

Шаги 3) и 5) можно поменять местами.

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

а)-б) Простейший порядок действий таков:
Если а - искомое число, х - текущее число на экране, (1),(2) - кнопки умножения на 2 и инкремента соответственно, то

   нажать (2)
   пока х*2<=a, нажимать (1)
   пока х<a, нажимать (2)

в) Попробуем найти более оптимальный алгоритм. Обозначения те же. N - число нажатий кнопок.

   N:=0
   Пока a>1, {начало цикла}
    Если a нечетное, то a:=(а-1)/2; n:=n+2;
    Иначе a=а/2; n:=n+1;
   {конец цикла}
   N:=N+1; {Переход от 1 к 0}

Для числа 99 алгоритм работает так:

   A  99 49 24 12 6 3 1 0
   N  0  2  4  5  6 7 9 10

То есть, требуется ровно 10 нажатий, а именно

   Кнопка     (2) (1) (2) (1) (1) (1) (1) (2) (1) (2)
   Результат  1   2   3   6   12  24  48  49  98  99

 Перенесено в раздел алгоритмов

20.04.2009, 19:46 [12968 просмотров]