Закрепление знаний по теме "Алгоритм и его свойства"

Решение задач, для закрепления материала.

Задача №1. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного “пассажира”. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту. Найди 2 варианта решения.

Решение:
Решение удобно записать в виде таблицы, указывая текущее положение объектов при переправе: кто на каком берегу остался, кто переправляется.

Исходное состояние
Старик, Волк, Коза, Капуста 

1 шаг
Волк, Капуста - левый берег
> Старик, Коза  - способ действия  

2 шаг
Волк, Капуста  - левый берег
< Старик  - способ действия  
Коза  - правый берег

3 шаг
Капуста - левый берег
> Старик, Волк  - способ действия  
Коза - правый берег

4 шаг
Капуста - левый берег
< Старик, Коза  - способ действия  
Волк - правый берег

5 шаг
Коза - левый берег
> Старик, Капуста  - способ действия  
Волк - правый берег

6 шаг
Коза - левый берег
< Старик  - способ действия  
Волк, Капуста - правый берег

7 шаг
> Старик, Коза  - способ действия  
Волк, Капуста - правый берег

Результат
Старик, Волк, Коза, Капуста - правый берег

Если возникли трудности при решение, целесообразно ответить на вопросы:

• Может ли перевозчик поплыть на лодке один, оставив на берегу всех троих – волка, козу и капусту?

• Может ли перевозчик поплыть на другой берег с одним из «пассажиров», а вернуться с другим?

Задача №2.Выполните предложенные действия.

1. Задумайте целое число от 1 до 20.
2. Результат умножьте на 2.
3. К полученному произведению прибавьте 3.
4. От суммы отнимите задуманное число.
5. К разности прибавьте 5.
6. От суммы отнимите задуманное число.
7. Сообщите ответ.
   
   
   Что у вас получилось? Объясните, в роли какого исполнителя – формального или неформального – вы выступали. Попробуйте поменять местами две любые команды. Получится ли у вас тот же результат?
   Решение: Очень хочется надеяться, что вы были внимательны, и у вас получилось число 12. Если получилось другое число, то выми допущена ошибка в вычислениях, так как последовательность действий была такова:
   Х
   Х+2
   (х+2)*2=2х+4
   2х+4+3=2х+7
   (2х+7)-х=х+7
   (х+7)+5=х+12
   (х+12)-х=12
   12
   
   
   Ответ: В данном случае вы выступали в качестве формального исполнителя, т.к. выполняли команды. Если поменять команды местами, то ответ будет уже другим. Если выполнять эти команды друг за другом, без вычислительных ошибок, то для разных чисел результат будет один и тот же.

главная страница

Задачи более высокого уровня

Задача №3. Задача про исполнителя команд.

Имеется Исполнитель алгоритма, который может передвигаться по числовой оси. Система команд Исполнителя алгоритма:
«Вперед N»
«Назад M»

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было.
Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?

Решение: Найдем сколько было команд «Вперед», а сколько было «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение х+(х+12)=50, где х- количество команд «Вперед». Тогда общее количество команд»Вперед» - х=19, а количество команд «Назад»: 19+12=31.
Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед3», Исполнитель алгоритма оказался на отметке числовой оси 57 (19*3=57). После выполнения 31 раз команды «Назад2» (31*2=62) он оказался бы на отметке -5. (57-62=-5).
Все эти команды можно заменить на одну команду «Назад 5»

Задача №4. Числа Фибоначчи.

Леонардо Пизанский, известный, как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который назван его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака»(1202 год).
Он выглядит так: 1,1,2,3,5,8,13,21,34,55,89,144…
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих.
Составьте словесный алгоритм проверки принадлежности введенного числа n ряду Фибоначчи.

Решение:
1. Ввести число N.
2. Установить значение первых трех чисел Фибоначчи: 1,1,2.
3. Пока введенное число N больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
3. Если число Фибоначчи равно введенному N или было введено число N=1, значит, что было введено число Фибоначчи, в противном случае – введенное число не является числом Фибоначчи.
Приведенный словесный алгоритм сожержит начальные установки, в пункте 3 цикл с условием, а пункт 4 – это вывод результата работы алгоритма.

главная страница