Алгоритм и его формальное исполнение.

Алгоритм и его формальное исполнение МОБУ Вышневолоцкого района «Академическая СОШ» Белова Т. А.

Алгоритм  определенная  действий при решении задачи. –  строго  последовательность  это

Исполнитель – это объект, способный  выполнять определенный набор команд.  Исполнителем может быть человек,  робот, животное, компьютер. Система команд исполнителя (СКИ)  – это набор команды, которые может  выполнять конкретный исполнитель.

Дискретность Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги АЛГОРИТМ Конечность Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения Свойства алгоритма Результативность – получение результата за конечное количество шагов Результативность Массовость – использование алгоритма для решения Массовость однотипных задач Детерминированность (определенность, точность) – Детерминированность каждое действие должно быть строго и недвусмысленно определено

Классификация алгоритмов по структуре: • Линейный (следование) • Разветвленный (ветвление) • Циклический (повтор) • Комбинированный

Классификация алгоритмов по форме представления: • Словесные • Табличные • Графические (блок-схемы) • Программа

Задача 1 Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: «Вперед N» (Кузнечик прыгает вперед на N единиц); «Назад М» (Кузнечик прыгает назад на М единиц). Переменные М и N могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 40 команд, в которой команд «Назад 2» на 10 больше, чем команд «Вперед 3». Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

Решение: Если всего команд 40, то команд «Назад 2» было 25, а «Вперед 3» 15. Кузнечик прыгнул вперед на 15*3=45 шагов, а назад на 25*2=50 шагов. Тем самым, он оказался на 5 шагов назад от первоначальной точки. Ответ: Назад 5.

Задача 2 Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды: Вперед n, где n – целое число, вызывающее передвижение Черепашки на n шагов в направлении движения. Направо m, где m - целое число, вызывающее изменение направления движения на m градусов по часовой стрелке. Запись Повтори 4 [Команда 1 Команда 2] означает, что последовательность команд в скобках повторится 4 раза.   Черепашке был дан для исполнения следующий алгоритм: Повтори 4 [Вперед 10 Направо 120] Какая фигура появится на экране? 1)      Незамкнутая ломаная линия 2)      Правильный треугольник 3)      Квадрат 4)      Правильный пятиугольник

Решение: 120о А В 120о 120о Черепашка прочертит на экране 4 линии, но последний отрезок полностью совпадет с первым, так что на экране появится правильный треугольник.

Таблица основных условных Условное обозначение Назначение блока обозначений в блок-схемах Начало/Коне ц Ввод/ вывод Команда Услови е Счетчик Начало или конец алгоритма Ввод или вывод данных Процесс (блок действий) Проверка условия Количество повторов цикла

Основные типы алгоритмических структур:

Основные типы алгоритмических структур:

Основные типы алгоритмических структур:

№ 1 Используя блок-схему алгоритма , вычислите значение функции Y при X=2, начало начало ввод: X ввод: X Z = 8 * X Z = 8 * X • РЕШЕНИЕ: начало 1. X = 2 2. Z = 8 * 2 = 16 3. Z = √16 = 4 4. Z = 4 – 1 = 3 5. Y = 3 * 2 = 6 6. Y = 6 / 3 = 2 конец Z = ZZ Z = Z = Z - 1 Z = Z - 1 Y = 3 * X Y = 3 * X Y = Y / Z Y = Y / Z вывод: Y вывод: Y конец конец

№ 2 Используя блок-схему алгоритма , вычислите значение функции Y при х =7, х = 0   • РЕШЕНИЕ: 1) Ввод: X = 7 Проверка условия x>0 (Да) y=2*7=14 Вывод: y=14 2) Ввод:  х=0 Проверка условия x>0 (Нет) y=-2*0=0 Вывод: y=0 начало ввод х да x >0 нет y = 2x y = -2x вывод y конец

Задача 3. (ЕГЭ) Записано 6 строк, каждая имеет свой номер – от 0 до 5. В нулевой строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i-той строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): (0)               0 (1)               001 (2)               0010012 (3)               001001200100123 Какая цифра стоит в последней строке на 62-м месте (считая слева направо)?

Решение: Найдем длину последней строки. Получается, что длина строк составит: (0)               1 элемент в строке; (1)               1*2+1=3 элемента в строке; (2)               3*2+1=7; (3)               7*2+1=15 элементов в строке; (4)               15*2+1=31; (5)               31*2+1=63 элемента в строке. Требуется найти 62-й элемент в строке длиной в 63 символов. Это означает, что нам нужен второй элемент с конца, предпоследний в строке. Последний символ в последней строке, это ее номер – 5. Предпоследний элемент строки – это последняя цифра в предыдущей строке (по правилу формирования строк). А окончание предыдущей строки – это ее номер, т.е. цифра 4.

Спасибо за внимание!!!