АЛГОРИТМЫ, ВИДЫ АЛГОРИТМОВ, ОПИСАНИЕ АЛГОРИТМОВ. ФОРМАЛЬНОЕ ИСПОЛНЕНИЕ АЛГОРИТМА ( ЗАДАЧИ ЕГЭ ). АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ. - презентация

1 АЛГОРИТМЫ, ВИДЫ АЛГОРИТМОВ, ОПИСАНИЕ АЛГОРИТМОВ. ФОРМАЛЬНОЕ ИСПОЛНЕНИЕ АЛГОРИТМА ( ЗАДАЧИ ЕГЭ ). АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ

2 Исполнители алгоритмов

3 КАЛЬКУЛЯТОР 1 У исполнителя Калькулятор две команды, которым присвоены номера: 1) вычти 1; 2) умножь на 3. Первая из них уменьшает число на экране на 1, вторая – увеличивает его в 3 раза. Запишите порядок команд в программе получения из 4 числа 17, содержащей не более 5 команд, указывая лишь номера команд. Например, – это программа: вычти 1; 2 -1=1 умножь на 3;1*3=3 умножь на 3;3*3=9 вычти 1;9-1=8 вычти 1;8-1= 7 Которая преобразует число 2 в 7. Если таких программ более одной, то запишите любую из них. РЕШЕНИЕ: При выполнении задания поиск программы удобнее вести от ответа, приближаясь к исходному числу. Ближайшее делящееся на 3 число, из котрого вычитанием единиц можно получить 17, будет 18. Последняя команда в программе будет 1)вычти 118 – 1 = 17 Число 18 можно получить, умножая 6 на 3, а число 6 умножая 2 на 3. Значит, три последние команды в программе – 221. Ну, а 2 получается, если дважды вычесть 1 из исходного числа 4. Две первые команды – 11. Итак, программа будет выглядеть так: Программа содержит 5 команд, значит условие задачи выполнено. 14-1=3 13-1=2 22*3=6 26*3= =17

4 2 У исполнителя Калькулятор две команды, которым присвоены номера: 1) вычти 2; 2) умножь на 3. Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 5 числа 19, содержащей не более 5 команд, указывая лишь номера команд. Например, – это программа: умножь на 3;3*3=9 вычти 2;9-2=7 умножь на 3;7*3=21 вычти 2;21-2=19 вычти 2;19-2= 17 Которая преобразует число 3 в 17. Если таких программ более одной, то запишите любую из них.

5 У исполнителя Калькулятор две команды, которым присвоены номера: 1) возведи в квадрат; 2) вычти 1. Первая из них возводит число на экране в квадрат, вторая – уменьшает его на 1. Запишите порядок команд в программе получения из 5 числа 8, содержащей не более 4 команд, указывая лишь номера команд. Например, – это программа: возведи в квадрат;2 2 =4 вычти 1;4-1=3 возведи в квадрат;3 2 =9 вычти 1;9-1=8 вычти 1;8-1= 7 Которая преобразует число 2 в 7. 3

6 У исполнителя Калькулятор две команды, которым присвоены номера: 1) прибавь 3; 2) умножь на 2. Первая из них прибавляет к числу на экране 3, вторая – увеличивает его в 2 раза. Запишите порядок команд в программе получения из 2 числа 31, содержащей не более 6 команд, указывая лишь номера команд. Например, – это программа: прибавь 3; 0 +3=3 умножь на 2;3*2=6 умножь на 2;6*2=12 прибавь 3;12+3=15 прибавь 3;15+3=18 Которая преобразует число 0 в 18. 4

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

8 2 ЧЕРЕПАШКА Повтори 9[Вперед 40 Направо n] Какое число надо написать вместо n, чтобы на экране появился правильный n- угольник? : Последняя линия должна полностью совпасть с первой. Т. о., за 8 поворотов – 360 градусов должна пройти. Ответ: Последняя линия должна полностью совпасть с первой. Т. о., за 8 поворотов – 360 градусов должна пройти. N=360/8=45

9 3 ЧЕРЕПАШКА Повтори 7[Вперед 20 Направо 60] Какая фигура появится на экране? Правильный шестиугольник Ответ: Правильный шестиугольник

10 Черепашка Повтори 5[Вперед 30 Налево 72] Какая фигура появится на экране? Где она будет находиться по отношению к черепашке? 4 ПравильныйпятиугольникСлева Ответ: Правильный пятиугольник. Слева.

11 Робот Робот (A 18) вверхвнизвлевовправо При выполнении этих команд РОБОТ перемещается на одну клетку соответственно. Четыре команды проверяют истинность условия отсутствия стены у той клетки, где находится РОБОТ: Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: Сверху свободноСнизу свободноСлева свободноСправа свободно Цикл ПОКА КОМАНДА выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток лабиринта соответствует требованию, что выполнив предложенную программу, РОБОТ остановится в той же клетке, с которой начал движение? НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ 1) 1 2) 2 3) 3 4) 4 2) 2 А В C D E F

12 ABCDEFGH 13.(Вовк Е.Т., с.70) НАЧАЛО ПОКА справа свободно ДЕЛАТЬ вправо ПОКА снизу свободно ДЕЛАТЬ вниз ПОКА слева свободно ДЕЛАТЬ влево ПОКА сверху свободно ДЕЛАТЬ вверх КОНЕЦ 1 А8 2. Сколько клеток данного лабиринта соответствует требованию, что, выполнив предложенную программу, Робот остановится в той же клетке, с которой начал движение? В ответе запишите число – количество таких клеток, а далее через запятую их адреса (сначала идёт латинская буква столбца, а затем цифра строки). Например, нижний левый угол имеет адрес А1

13 Робот ABCDEFGH 14. (Вовк Е.Т., с.71) НАЧАЛО ПОКА справа свободно ДЕЛАТЬ вправо ПОКА сверху свободно ДЕЛАТЬ вверх ПОКА слева свободно ДЕЛАТЬ влево ПОКА снизу свободно ДЕЛАТЬ вниз КОНЕЦ 4 A1, D4, B2, G6

14 Робот ABCDEFGH 15. (Вовк Е.Т., с.72) НАЧАЛО ПОКА снизу свободно ДЕЛАТЬ вниз ПОКА справа свободно ДЕЛАТЬ вправо ПОКА сверху свободно ДЕЛАТЬ вверх ПОКА слева свободно ДЕЛАТЬ влево КОНЕЦ 3 А2, А7, С6