Базовые алгоритмические структуры

Предмет: Основы информатики.

Группа: 29-30 учащихся.

Характеристика группы: в группе 30 человек. 11 человек – с высоким уровнем знаний, 9 – человек со среднем, с низким уровнем знаний – 10 человек.

Цель урока: составление программ с помощью алгоритмических структур.

Задачи урока:

• научится правильно составлять структуры;
• развитие логического мышления и аккуратности у учащихся;
• обучение работе с компьютерными тестами.

Тип урока: изучение нового материала.

Методы урока:

• словесный;
• практический;
• самостоятельной работы.

Форма урока: групповая, индивидуальная.

Средства ведения урока: компьютеры, электронный учебник, схемы, тесты.

Ход занятия

1. Организационный момент.

Приветствие учащихся. Отметка явки на занятие. Сообщение темы и цели занятия.

2. Знакомство с новым материалом.

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

План:

• Последовательная алгоритмическая конструкция;
• Ветвящаяся алгоритмическая конструкция;
• Циклическая алгоритмическая конструкция.

Элементарные шаги алгоритма при укреплении объединяются в алгоритмические конструкции: последовательные, ветвящаяся, циклические, рекурсивные. В 1969 году Эдсгер В. Дийкстра в статье «Структуры данных и алгоритмы доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических.

Последовательная алгоритмическая конструкция

Алгоритм Р реализирован последовательную алгоритмическую конструкцию, если каждые шаги алгоритма Р выполняются один раз, причем после каждого i-го шага выполняются (i +1)-й шаг, если i-й шаг – не конец алгоритма.

Ветвящаяся алгоритмическая конструкция

Алгоритм Р реализован через ветвящуюся алгоритмическую конструкцию, если от входных данных зависит, какие шагибудут выполнятся (последовательность выполнения шагов алгоритма зависит от входных данных). При каждом конкретном наборе входных данных ветвящаяся алгоритмическая конструкция сводится к последовательной алгоритмической конструкции.

Циклическая алгоритмическая конструкция

Алгоритм Р реализован с использованием циклической алгоритмической конструкции, если некая, подряд идущая группа шагов алгоритма может выполнять несколько раз в зависимости от входных данных. Любая циклическая алгоритмическая конструкция содержит в себе элементы ветвящейся алгоритмической конструкции.

Количество повторений тела цикла может быть известно или нет. Если неизвестно количество повторений тела цикла, завершение его работы происходит по достижению определенного условия. Таким образом, циклы делятся на циклы с параметром и условием.

В цикле с параметром задается переменная, выполняется роль параметра цикла , её начальное и конечное значения, приращение (шаг изменения значения параметра цикла).

Блок-схема алгоритма цикла с параметром представлена на рисунке:

Рис. Блок-схема алгоритма цикла с параметром.

Условные циклы предназначены для организации итерационных вычислительных процессов. Они подразделяются на циклы с предусловием и циклы с постусловием. В цикле с предусловием перед выполнением тела цикла осуществляется проверка значения логического выражения или переменной логического типа, если значение этих величин удовлетворяют условию работы цикла, то выполняется тело цикла, в противном случае, выполняется следующий за циклом оператор. Таким образом, операторы тела цикла с постусловием могут быть не выполнены ни одного раза. На рис. Представлена блок-схема алгоритма цикла с постусловием.

Цикл с постусловием предназначен для организации циклических алгоритмов, в которых проверка условия работы цикла выполняется после исполнения операторов тела цикла. По этой причине, операторы тела цикла всегда будут выполнены хотя бы один раз. На рисунке представлена блок-схема алгоритма цикла с постусловием.

Рис. Блок-схема алгоритма цикла с предусловием.

Рис. Блок-схема алгоритма цикла с постусловием.

3. Закрепление материала.

Работа на компьютере с электронными учебниками.

4. Самостоятельная работа.

Вопросы и задания.

• Приведите примеры алгоритмов, использующих последовательные алгоритмические конструкции.
• Приведите примеры алгоритмов, использующие ветвящиеся алгоритмические конструкции.
• Приведите примеры алгоритмов, использующие циклические алгоритмические конструкции.
• Составить алгоритм нахождения суммы конечного ряда в виде блок-схемы.
• Составить алгоритм нахождения факториала числа N в виде блок-схемы.
• Составить алгоритм нахождения N-ой степени числа x в виде блок-схемы.
• При каких начальных значениях переменных алгоритм закончит работу.

1. А= -2; С=-3;
2. А=-3; С=-2;
3. А=-3; С=-3;
4. А=-2; С=-1;
5. А=-4, С=-3.

• Определите выходные значения переменных А и С после выполнения алгоритма

1. 1, 7
2. 0, -4
3. 1, 3
4. 0, -5
5. Зацикливание

• Укажите, какие из приведенных схем алгоритмов могут быть отнесены к основным (типовым) схемам:

 

• Найдите значение переменной F входных данных 1, 1, 3, вычисленное по блок-схеме

• Найдите значение переменной F для входных данных 3, 3, 1 вычисленное по блок-схеме

5. Продолжение изучения нового материала.

АЛГОРИТМ И ЕГО СВОЙСТВО. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ БЛОК-СХЕМ.

План:

• Алгоритм и его свойстваж
• Описание алгоритма с помощью блок-схем.

Алгоритм и его свойства

Алгоритм – это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа ходов) искомого результата.

Приведенное выше определение не является формальным, это довольно подробное описание понятия алгоритма, раскрывающее его сущность.

Любой алгоритм не существует сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которым исполнитель может совершать действия образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.

Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ. Однако любой алгоритм в отличие от рецепта или способа, обязательно обладает следующими свойствами.

1. Выполнение алгоритма разбивается на последовательность законченных действий – шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Это свойство алгоритма называется дискретностью. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
2. Детерминированность – на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученной на предыдущих шагах алгоритма. Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат.

Замечание. Свойство детерминированности объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.

Точность – запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнять следующей.

Понятность (для данного исполнителя)- алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнителя должно давать один и тот же результат. То есть запись алгоритма должна быть насколько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя.

Рассмотрим известный пример «бытового» алгоритма- алгоритма перехода улицы: «посмотрим налево. Если машины нет – дойти до середины улицы. Если есть – подожди, пока они проедут». И т.д. представьте себе ситуацию, машина слева есть, но она не едет – у нее меняют колесо. Если вы думаете, что надо ждать, то вы поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!)обстоятельств, то вы не усвоили понятие алгоритма.

3. Результативность – каждый шаг (и алгоритм в целом) после своего завершения дает среду, в котором все объекты однозначно определены. Если по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. При точном исполнении команд алгоритма процесс должен прекратиться за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного возможных ответов может быть и установление того факта, что задача решений не имеет.
4. Конечность – завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамки теории алгоритмов.
5. Массовость – алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма, т.е. алгоритм пригоден для решения любой задачи из которого класса задач. Это свойство не следует понимать как возможность решить много задач.

Дадим уточненное понятие алгоритма, которое более формально описывает понятие алгоритма, раскрывающее его сущность.

Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности, конечности и массовости.

Описание алгоритм с помощью блок-схем

При блок-схемном описании алгоритма изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями тока) со стрелками. В блоках записывается последовательность действий.

Данный способ по сравнению с другими способами записи алгоритма имеет ряд преимуществ. Он наиболее нагляден: каждая операция вычислительного процесса изображается отдельной геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвление путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.

Условные обозначения блоков схем алгоритмов

Наименование	Обозначения	Функции
Процесс		Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Решение		Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.
Предопределенный процесс		Использование ранее созданных и отдельно написанных программ (подпрограмм).
Документ		Вывод данных на бумажный носитель.
Пуск-останов		Начало, конец, прерывание процесса обработки данных.

Линии, соединяющие блоки и указывающей последовательность связей между ними, должны проводится параллельно линиям рамки. Стрелка в конце линии может не ставится, если линия направлена слева направо или сверху вниз. В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков. Из блока (кроме логического) может выходить из двух блоков, и из него выходят две линии. Если на схеме имеет место слияние линий, то место пересечения выделяются точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.

Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.

Блок-схема должна содержать все разветвления, циклы и обращения к подпрограммам, содержащиеся в программе.

6. Домашнее задание.

Выучить конспект и подготовиться к тесту.