Методическая разработка урока "Алгоритм и его формальное исполнение".

• 1 слайд

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

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

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

• 9 слайд

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

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

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

• 15 слайд

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

• 16 слайд

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

• 17 слайд

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

• 18 слайд

  Решение: Найдем длину последней строки. Получается, что длина строк составит: (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.

• 19 слайд

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

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

Учитель: Белова Т. А.

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

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-е место (считая слева направо).

• 1 слайд

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

• 2 слайд

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

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

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

• 9 слайд

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

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

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

• 15 слайд

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

• 16 слайд

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

• 17 слайд

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

• 18 слайд

  Решение: Найдем длину последней строки. Получается, что длина строк составит: (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.

• 19 слайд

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

Краткое описание документа:

Методическая разработка включает конспект урока и презентацию. Целью данного урока является повторение теоретического материала по теме «Алгоритм, исполнитель, свойства алгоритма, виды алгоритмов, формальное исполнение». Закрепление представлений учащихся о понятии алгоритма, способах записи алгоритма, уметь применять полученные знания при решении задач