Автор: Колесниченко Елена Владимировна

Должность: Учитель информатики

Категория: Высшая квалификационная категория

Учреждение: Муниципальное автономное общеобразовательное учреждение «Гимназия № 56»

Удмуртская Республика, город Ижевск

e-mail: helena@labore.ru

Тема: Основы алгоритмизации

Предмет: Информатика

Класс 10

Ключевые слова: алгоритм, свойства, блок-схема, идентификаторы, базовые структуры

Оборудование: графический редактор Visio (можно использовать on-line редактор блок схем), текстовый редактор MS Word.

Аннотация. Методическая разработка предназначена для изучения темы «Основы алгоритмизации» в классах физико-математического и информационно-технологического профилей. Содержит подробное изложение материала по данной теме и разработку практической  работы. Разработка может быть использована учителями информатики, а также обучающимся 10 классов при самостоятельном  изучении материала.

Муниципальное автономное общеобразовательное учреждение
«Гимназия № 56»

Методическая разработка темы 

«Основы алгоритмизации»

Колесниченко Елена Владимировна, учитель информатики

Ижевск 2014

Цель: изучение методов алгоритмизации и использование полученных знаний для построения математических моделей инженерных задач.

Задачи:

Формирование базовых знаний по алгоритмизации, рациональные методах разработки алгоритмов;

Изучение базовых алгоритмических структур;

Изучение объектов алгоритмов;

Знакомство с этапами построения математических моделей;

АЛГОРИТМЫ

Этапы решения задач на ЭВМ

Рассмотрим, из чего складывается процесс решения задачи на ЭВМ, и какие необходимо пройти для этого этапы.

ü I этап – постановка задачи. На этом этапе должна быть определена предметная область задачи, определены цели задачи, необходимый объем исходной информации, проведено описание каждого исходного данного. Предложен общий подход к решению.

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

Под математической моделью будем понимать описание объекта или процесса математическими формулами, связывающими их количественные параметры. При описании математических моделей используются различные системы обозначений.

ü III этап – алгоритмизация задачи. Главная особенность всех вычислений машины состоит в том, что в основе ее работы лежит программный принцип управления. Это означает, что для решения, как самой простой, так и самой сложной задачи пользователю необходимо использовать перечень инструкций или команд, следуя которым шаг за шагом ЭВМ выдаст необходимый результат.

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

На основе математической модели (имеющихся расчетных формул) разрабатывается алгоритм решения. Чаще всего алгоритм разрабатывается на основе блок – схемы с четко определенной последовательностью действий.

ü IV этап – программирование. Программа – это представление алгоритма с помощью специальных символов, воспринимаемых компьютером. Каждому блоку алгоритма соответствует определенная последовательность операторов. Программа обеспечивает возможность реализации алгоритма и поставленной задачи. При составлении программы возможно уточнение и изменение алгоритма.

ü V этап – ввод программы в ЭВМ. На этом этапе программу необходимо набрать в интегрированной среде программирования и сохранить на диске.

ü VI этап – разработка контрольного примера. Для того, чтобы убедиться в правильности составленной программы, необходимо разработать тестовую задачу, проверяющую все ветви алгоритма. Это совокупность таких исходных данных, на основании которых заранее определяются выходные данные.

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

ü VIII этап – получение и анализ результатов. После устранения всех ошибок, выявленных тестовой задачей, можно перейти к получению результатов поставленной задачи. Полученные в результате решения результаты необходимо проанализировать.

þ Алгоритмы

Слово «алгоритм» знакомо многим читателям. Его применяют широко и не только в области вычислительной техники и программирования. В повседневной жизни приходится решать различные задачи. Задачи могут быть бытовые (прибрать комнату, приготовить обед, перейти улицу и т.п.), учебные (решить систему уравнений, построить график) или профессиональные (изготовить деталь на станке, рассчитать заработную плату). Все задачи можно разделить по различным признакам: математические, научные, инженерные, экономические. Одни задачи решаются легко, другие нет. Решить задачу означает получить результат, отвечающий целям данной задачи. Для каждой задачи должно быть известно, что считать результатом. В процессе решения задачи выполняются определенные действия над исходными данными. Совокупность этих действий может быть задана настолько подробно, что ее исполнение становиться чисто механическим процессом. Полученная инструкция может использоваться для решения однотипных задач. Такую инструкцию называют алгоритмом.

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

Содержание понятия алгоритма можно определить следующим образом:

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

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

üАлгоритмический процесс – процесс последовательного преобразования объектов дискретными шагами.

Каждый алгоритм характеризуют независимые параметры:

·        совокупность возможных исходных данных (исходные данные могут изменяться в определенных пределах);

·        совокупность возможных промежуточных результатов (на каждом шаге должно быть известно, что считать результатом);

·        совокупность результатов;

·        правило начала;

·        правило непосредственной переработки;

·        правило окончания;

·        правило извлечения результата.

þ Свойства алгоритма

üПонятность. Каждый алгоритм создается для конкретного исполнителя. Чтобы исполнитель мог решить поставленную перед ним задачу, используя алгоритм, он должен уметь выполнить каждое его указание, понимать суть управления. Под «понятностью» алгоритмов понимают указания, понятные исполнителю.

üДетерминированность (однозначность). Будучи понятным, алгоритм не должен все же содержать предписаний, смысл которых может восприниматься неоднозначно.

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

Под однозначностью алгоритмов понимается единственность толкования правил выполнения действий и порядка их выполнения.

üДискретность. Под дискретностью понимают возможность разбиения алгоритма на отдельные элементарные действия, выполнение которых человеком или машиной не вызывает сомнения.

üМассовость. Очень важно, чтобы составленный алгоритм обеспечивал решение не одной частной задачи, а мог выполнять решение широкого класса задач данного типа.

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

üКонечность. Выполнение действий, заданных алгоритмом, состоит из конечного числа шагов.

üРезультативность. Выполнение алгоритма должно завершаться получением определенных результатов. Должно быть известно какой результат должен быть получен через конечное число шагов.

þ Способы представления алгоритмов

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

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

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

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

Таблица 1

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

þ Объекты алгоритмов

У каждой конкретной задачи есть свои реальные объекты (данные, которые подлежат обработке). Каждый объект имеет свои характеристики, свойства или атрибуты. В процессе решения могут возникнуть и вспомогательные объекты. К объектам относятся константы, переменные, файлы, массивы. Каждый объект имеет свой тип (например, число может быть целого типа или вещественного).

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

Под переменной будем понимать объект, который имеет определенный фиксированный тип, но значение переменной может меняться на протяжении вычислительного процесса.

Под массивом будем понимать упорядоченную совокупность данных одного типа.

Доступ к каждому элементу массива осуществляется по его порядковому номеру (индексу).

Каждый объект в алгоритме должен иметь свое имя – идентификатор.

Для обработки объектов алгоритма используют операторы, которые представляют закодированную форму инструкции. Различают простые и составные операторы. К простым относятся операторы присваивания, ввода-вывода, перехода. Группу составных (сложных) операторов представляют операторы условия, циклические, присоединения. Для пояснения алгоритмов используют комментарии.

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

К базовым конструкциям алгоритмов относятся три основные структуры:

·    линейная;

·    разветвляющаяся;

·    циклическая.

Алгоритм любой сложности состоит из комбинации этих базовых структур.

üЛинейные алгоритмы

Алгоритм называется линейным, если все действия в нем выполняются последовательно одно за другим.

Типовая блок схема линейного алгоритма представлена на рис. 1. Линейный алгоритм может содержать блоки ввода и вывода данных, блоки вычислений – действий.

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

üРазветвляющиеся алгоритмы

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

üЦиклические алгоритмы

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

·          параметр цикла;

·          тело цикла (повторяющиеся действия);

·          приращение параметра цикла (изменением его на определенный шаг);

·          условие выхода из цикла.

Если заранее известно число повторений в цикле, то такой цикл называют арифметическим и его реализуют при помощи типовой схемы «цикл с параметром» рис. 3.

Если число повторений в цикле неизвестно, то цикл называют итерационным.

Итерационные циклы можно организовывать двумя структурами:

1. с постусловием (рис. 5);

2. c предусловием (рис. 6).

Цикл с постусловием выполняется пока условие «ложно». Этот цикл выполнится всегда хотя бы один раз, так как первая проверка выхода из цикла происходит после выполнения «тела цикла». Цикл с предусловием выполняется пока условие «истинно» и может не выполниться ни одного раза, если при первой проверке условие выхода выполняется.

Внутри цикла может содержаться функциональный узел на проверку условия (рис. 4).

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

þ Этапы разработки алгоритма

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

На рис. 7 представлена общая схема этапов разработки алгоритма.

Рис. 7. Этапы разработки алгоритма.

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

Пошаговая детализация задачи позволяет свести трудную задачу к последовательности более простых задач.

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

Таблица идентификаторов может быть представлена в произвольной форме, но она должна содержать все объекты задачи с указанием имен и типов. Примерная таблица приведена в табл. 2.

Таблица идентификаторов

Таблица 2.

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

Пример 1. Рассмотрим задачу вычисления площади треугольника по трем заданным сторонам.

Постановка задачи. Даны стороны треугольника. Вычислить его площадь.

üМатематическая модель.

Входные данные: стороны треугольника.

Выходные данные: площадь треугольника.

Дополнительные параметры: полупериметр.

Расчетные формулы:

Заполним таблицу идентификаторов табл. 3:

Таблица 3.

Теперь можно перейти к составлению алгоритма (рис. 8).

Данный алгоритм повторяет линейную структуру. Но всегда ли такой алгоритм будет работать? Нет, так как при вычислении площади мы имеем дело с вычислением квадратного корня, подкоренное выражение которого может оказаться отрицательным. Это говорит о том, что не из любых трех отрезков можно построить треугольник. На уточняющем этапе разработки алгоритма необходимо учесть случай существования треугольника и в алгоритме поставить проверку на существование треугольника. Треугольник будет существовать, если сумма двух сторон больше третьей стороны. При такой постановке задачи алгоритм уже будет реализовывать разветвляющуюся структуру (рис. 9). Для исключения варианта некорректного ввода данных, в случае невыполнения условия, сделаем переход на блок ввода данных (рис. 10).

Пример 2. Определить, принадлежит ли точка с координатами (x,y) окружности с центром в начале координат и радиусом r.

üМатематическая модель.

Входные данные: радиус окружности;

координаты точки.

Выходные данные: сообщение о принадлежности точки окружности.

Дополнительные параметры: расстояние от точки до центра окружности.

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

Точка будет принадлежать окружности при условии, что расстояние от нее до центра окружности будет меньше или равно радиусу окружности.

Расчетные формулы:

Расстояние от точки до центра окружности

Составим таблицу идентификаторов табл. 4:

Таблица 4.

Алгоритм задачи представлен на рис. 11. Структура алгоритма повторяет типовую разветвляющуюся структуру.

Пример 3. Теперь усложним задачу. Пусть задано n точек. Определить количество точек, принадлежащих окружности. Для решения этой задачи требуется ввести новые объекты. Занесем их в таблицу идентификаторов, продолжив табл. 4:

Составим алгоритмы двумя способами: в первом случае используем цикл с параметром, а во втором цикл с постусловием, рис.13, 14. Циклический блок объединяет следующие действия:

·        задание начального значения параметра цикла (переменной i присваивается начальное значение равное1);

·        приращение переменной на 1 (i=i+1);

·        проверка условия выхода из цикла (как только i достигает значения n, цикл завершается.)

Во втором алгоритме (рис. 14) все эти действия показаны в отдельных блоках.

В цикле осуществляется ввод координат точек и подсчет количества точек, принадлежащих окружности.

Рис. 13

Рис. 14

ПРАКТИЧЕСКАЯ РАБОТА

Цель работы. Получить навыки составления математических моделей и алгоритмов.

üЗадание. Составить математическую модель, таблицу идентификаторов и алгоритм для следующих задач:

1.     а) Определить в каком квадрате находится точка с координатами x,y.
b) Задано n точек. Определить, сколько из них находится в первом квадрате.

2.     а) Определить принадлежит ли точка с координатами x,y заданному прямоугольнику;
b) Задано n точек. Определить, сколько из них находится внутри прямоугольника.

3.     Рассчитать прибыль по вкладу за заданный промежуток времени. Годовой процент начислений известен. Проценты могут начисляться через 1, 2 ,3 месяца. С полученных начислений идет новый процент.

4.     Из квадратного листа картона вырезается коробка. Определить, какова должна быть сторона вырезаемого квадрата, чтобы коробка имела наибольшую вместимость.

5.     Определить количество рулонов обоев, необходимых для оклейки 1, 2, 3 и т.д. комнат.

6.     Рассчитать количество краски, необходимое для покраски окон, если известен расход краски на 1 кв. м.

7.     В прямоугольном треугольнике задана длина гипотенузы. Определить размеры катетов, при которых треугольник будет иметь наибольшую площадь.

8.     Рассчитать стоимость покупки товаров в магазине.

9.     Вычислить стороны прямоугольного треугольника, если известны его плошадь и периметр.

10. Составить алгоритм пересчета суммы денег в рублях в доллары и евро.

11. Рассчитать стоимость шитья пальто.

12. Рассчитать прибыль, полученную от реализации товаров.

sКонтрольные вопросы

1.     Из чего складывается процесс решения задачи на ЭВМ?

2.     Что понимают под математической моделью задачи?

3.     Как влияет выбор метода решения на дальнейший ход решения задачи?

4.     Как можно реализовать алгоритм на ЭВМ?

5.     С какой целью разрабатываются контрольные примеры?

6.     Что означает «отладить» программу?

7.     Какими параметрами характеризуется алгоритм?

8.     Какими свойствами характеризуется алгоритм?

9.     Какие существуют способы представления алгоритмов?

10. Какие существуют объекты алгоритмов?

11. Перечислите базовые алгоритмические конструкции.

12.    Какими параметрами характеризуется циклический процесс?

Литература

1.     В.В. Фаронов. «Основы Турбо Паскаля». М: учебный инженерный центр «МВТУ – ФЕСТО ДИДАКТИК», 1992, 304 с.

2.     Р. Хершель. «Turbo Pascal». Вологда: МП «МИК», 1991, 342 с.

3.     И. Бабушкина и др. «Практикум по Турбо Паскалю» учебное пособие по курсам «Информатика и вычислительная техника», «Основы программирования». М, АБФ, 1998, 384 с.

4.     Колесниченко Е.В. «Turbo Pascal», лабораторный практикум. Ижевск, Издательский дом «Удмуртский университет». 2002, 244 с.

Данный материал был скачан с сайта www.metod-kopilka.ru

============================================================

!!!!!!!!Орфография и форматирование автора материала!!!!!!!!!!

========================================

Образовательно-информационный ресурс для учителей информатики,

учащихся и всех-всех, кто интересуется ИТ:

http://www.metod-kopilka.ru Методическая копилка учителя информатики

Организационные, методические и нормативные документы,

лабораторно-практические работы (комплекс занятий по MS Word, MS Excel,

MS Access, MS PowerPaint, Paint, Move Maker и др. прикладным программам),

лекции,конспекты, дидактический материал, занимательная информатика,

экзамен, проектная деятельность, презентации.

Все в свободном доступе! Без регистрации!