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

Алгоритм и его формальное исполнение. 10 класс Цель: повторение теоретического материала по теме «Алгоритм, исполнитель, свойства  алгоритма, виды алгоритмов, формальное исполнение».  Задачи: Образовательная – закрепить представление  учащихся о понятии алгоритма, способах  записи алгоритма, уметь применять полученные знания при решении задач; Воспитательная – воспитание информационной культуры учащихся, внимательность,  аккуратность, дисциплинированность, усидчивости; Развивающая – развитие алгоритмического мышления, познавательного интереса. Ход урока: 1. Повторение теоретического материала по теме "Алгоритмы, виды алгоритмов,  описания алгоритмов. Формальное исполнение алгоритма".   Вопросы для повторения: 1. Сформулируйте понятие алгоритма. Слайд 2 2. Кто или что является Исполнителем алгоритмов? Слайд 3 Флэш­ролик 3. Что вы понимаете под Системой Команд Исполнителя? Слайд 3 4. Определите свойства алгоритмов. Слайд 4 5. Охарактеризуйте виды алгоритмов.  Слайд 5 6. Какими способами можно записать алгоритм? Слайд 13 2. Решение задач.   Задача 1. Слайды 7­8 Имеется   исполнитель   Кузнечик,   который   живет   на   числовой   оси.   Система   команд Кузнечика: «Вперед N» (Кузнечик прыгает вперед на N единиц); «Назад М» (Кузнечик прыгает   назад   на   М   единиц).   Переменные   М   и   N   могут   принимать   любые   целые положительные значения. Известно, что Кузнечик выполнил программу из 40 команд, в которой   команд   «Назад   2»   на   10   больше,   чем   команд   «Вперед   3».   Других   команд   в программе   не   было.   На   какую   одну   команду   можно   заменить   эту   программу,   чтобы Кузнечик оказался в той же точке, что и после выполнения программы? Какая алгоритмическая структура будет использована при решении задачи?   Решение.  Если всего команд 40, то команд «Назад 2» было 25, а «Вперед 3» всего 15. кузнечик прыгнул вперед на 15*3=45 шагов, а назад на 25*2=50 шагов. Тем самым, он оказался   на   5   шагов   назад   от   первоначальной   точки.   Последовательность   команд   в алгоритме в данном случае не имеет значения.   Ответ: Назад 5.   Задача 2.  Слайды 9­10 Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В   каждый   конкретный   момент   известно   положение   исполнителя   и   направление   его движения. У исполнителя существуют две команды: Вперед   n,   где   n   –   целое   число,   вызывающая   передвижение   Черепашки   на   n   шагов   в направлении движения. Направо m, где m ­ целое число, вызывающая изменение направления движения на m градусов по часовой стрелке. Запись  Повтори 4 [Команда 1 Команда 2]  означает, что последовательность команд в скобках повторится 4 раза.   Черепашке был дан для исполнения следующий алгоритм: Повтори 4 [Вперед 10 Направо 120] Какая фигура появится на экране? 1)      Незамкнутая ломаная линия 2)      Правильный треугольник 3)      Квадрат 4)      Правильный пятиугольник  Какая алгоритмическая структура будет использована при решении задачи? Решение: Черепашка   прочертит  на  экране  4  линии,  но  последний   отрезок  полностью  совпадет  с первым, так как после третьего выполнения цикла Черепашка полностью обернется вокруг своей   оси   и  окажется   в  той   же   точке,   что   и   изначально.  Так   что  на   экране   появится правильный треугольник.   Ответ: 3.    Вопросы для повторения: 1. Какие блоки используются при составлении блок­схем? Слайд 11 2. Блок схемы основных типов алгоритмических структур. Слайды 12­14 Решение задач с использованием блок­схем.  Используя блок­схему алгоритма, вычислите значение функции. Слайды 15­16 Задача. (ЕГЭ) Записано 6 строк, каждая имеет свой номер – от 0 до 5. В нулевой строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i­той строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): (0)               0 (1)               001 (2)               0010012 (3)               001001200100123 Какая цифра стоит в последней строке на 62­м месте (считая слева направо)?   Решение: Найдем   длину   последней   строки.   По   условию,   длина   каждой   последующей   строки увеличивается  в 2 раза, по сравнению с предыдущей, плюс еще один символ – цифра, обозначающая порядковый номер самой строки. Получается, что длина строк составит: (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.   Ответ: 4.    Д/з:   повторить   понятия   «Алгоритм,   исполнитель,   свойства   алгоритма,  виды   алгоритмов, формальное исполнение».    Задача:   Строки   (цепочки   символов   латинских   букв)   создаются   по   следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих   цепочек   создается   такими   действиями:   в   очередную   строку   сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i­ м   шаге   пишется   «i»­я   буква   алфавита),   к   ней   справа   дважды   подряд   приписывается предыдущая строка.             Вот первые 4 строки, созданные по этому правилу:             (1) A             (2) BAA             (3) CBAABAA             (4) DCBAABAACBAABAA             Латинский алфавит (для справки):              ABCDEFGHIJKLMNOPQRSTUVWXYZ              Запишите семь символов подряд, стоящие в восьмой строке со 126­го по 132­е место (считая слева направо). Задача 1.  Имеется   исполнитель   Кузнечик,   который   живет   на   числовой   оси.   Система   команд Кузнечика: «Вперед N» (Кузнечик прыгает вперед на N единиц); «Назад М» (Кузнечик прыгает   назад   на   М   единиц).   Переменные   М   и   N   могут   принимать   любые   целые положительные значения. Известно, что Кузнечик выполнил программу из 40 команд, в которой   команд   «Назад   2»   на   10   больше,   чем   команд   «Вперед   3».   Других   команд   в программе   не   было.   На   какую   одну   команду   можно   заменить   эту   программу,   чтобы Кузнечик оказался в той же точке, что и после выполнения программы?   Задача 2.   Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В   каждый   конкретный   момент   известно   положение   исполнителя   и   направление   его движения. У исполнителя существуют две команды: Вперед   n,   где   n   –   целое   число,   вызывающая   передвижение   Черепашки   на   n   шагов   в направлении движения. Направо m, где m ­ целое число, вызывающая изменение направления движения на m градусов по часовой стрелке. Запись  Повтори 4 [Команда 1 Команда 2]  означает, что последовательность команд в скобках повторится 4 раза.   Черепашке был дан для исполнения следующий алгоритм: Повтори 4 [Вперед 10 Направо 120] Какая фигура появится на экране? 1)      Незамкнутая ломаная линия 2)      Правильный треугольник 3)      Квадрат 4)      Правильный пятиугольник Задача. (ЕГЭ) Записано 6 строк, каждая имеет свой номер – от 0 до 5. В нулевой строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i­той строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): (0)               0 (1)               001 (2)               0010012 (3)               001001200100123 Какая цифра стоит в последней строке на 62­м месте (считая слева направо)? Д/з:  Строки   (цепочки   символов   латинских   букв)   создаются   по   следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих   цепочек   создается   такими   действиями:   в   очередную   строку   сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i­ м   шаге   пишется   «i»­я   буква   алфавита),   к   ней   справа   дважды   подряд   приписывается предыдущая строка.             Вот первые 4 строки, созданные по этому правилу:             (1) A             (2) BAA             (3) CBAABAA             (4) DCBAABAACBAABAA             Латинский алфавит (для справки):              ABCDEFGHIJKLMNOPQRSTUVWXYZ              Запишите семь символов подряд, стоящие в восьмой строке со 126­го по 132­е место (считая слева направо).