Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ТЕМА 4.1. ОСНОВЫ АЛГОРИТМИЗАЦИИ.
Термин алгоритм возник задолго до появления компьютеров, в IX веке. Первые правила
(алгоритмы) описывали сложение, вычитание, умножение, деление многозначных чисел. Этими правилами мы пользуемся и сегодня.
Алгоритм – это законченная последовательность команд, которые необходимо выполнить над исходными данными, чтобы получить результат.
В вычислительных процессах алгоритм есть последовательность команд (директив), которые обозначают действия, которые необходимо выполнить для достижения поставленной цели: решения конкретной задачи.
Эффективным методом построения алгоритмов есть метод пошаговой детализации, при котором задача разбивается на несколько простых подзадач (модулей), и для каждого модуля создается свой алгоритм. Чаще всего алгоритм складывается из главного модуля и нескольких других, созданных ранее. Такой метод называется структурным проектированием алгоритма.
является достаточно сложным и трудоемким. Он включает несколько последовательных этапов:
1) формулировка задачи;
2) математическая постановка задачи;
3) выбор метода решения и численный анализ;
4) разработка алгоритма;
5) выбор структуры данных;
6) программирование;
7) тестирование и отладка программы.
На первом этапе чётко излагается условие задачи, выделяются исходные данные для её решения, даются точные указания, какие результаты и в каком виде должны быть получены.
На втором этапе задача представляется в виде уравнений, соотношений, ограничений, необходимых для её решения.
На третьем этапе выбирается метод, наиболее приемлемый для решения данной задачи. Подбираются формулы, по которым выполняются вычисления. Для простых задач численные методы не нужны. Численный анализ проводится с целью выявления возможности возникновения некорректных арифметических операций (деление на 0 и т.п.).
На четвертом этапе непосредственно разрабатывают алгоритм решения задачи. Под разработкой алгоритма понимают сведение задачи к последовательности этапов, выполняемых друг за другом так, что результаты предыдущих этапов используются при выполнении последующих. Это согласуется с возможностями ЭВМ - выполнять действия последовательно одно за другим.
На пятом этапе определяются типы данных для используемых в программе переменных (целый, вещественный, логический, символьный или строковый и т.д.) и выбираются структуры данных (массивы, множества, файлы, записи).
На шестом этапе разрабатывается программа – запись алгоритма на языке, понятном ЭВМ.
На седьмом этапе проверяется правильность работы программы на конкретном примере, исправляются обнаруженные ошибки, т.е. производится отладка программы.
Полученный алгоритм должен обладать следующими свойствами:
Разработанный алгоритм можно описать несколькими способами:
При словесно-формульном описании алгоритм вычислений задается формульными инструкциями о выполнении конкретных действий в сочетании со словесными пояснениями.
При операторном способе алгоритм записывается с помощью абстрактных инструкций – операторов, в каждом языке программирования существуют соответствующие им реальные операторы, процедуры и функции.
Наиболее часто алгоритмы вычислительных процессов описываются в виде блок-схем, где каждый шаг алгоритма представляется специальным блоком, который условно показывает действие, которое необходимо выполнить. Использование графического способа позволяет отобразить алгоритм решения задачи в наглядной форме. Основные графические конфигурации блоков и их функции приведены в табл.1. (ГОСТ 19.701-90).
В соответствии с правилами построения, каждая схема должна иметь начало и окончание, обозначаемые в виде овалов. Блоки в схеме располагаются в последовательности сверху вниз, слева направо и соединяются линиями потока. Нормальным направлением линий потока, т.е. следования этапов процесса переработки данных считается направление сверху вниз и слева направо и стрелками не обозначается. Во всех других случаях обозначение направления стрелками обязательно. Линии, связывающие элементы схемы, должны проводиться только по вертикали или горизонтали и подводиться к середине символа. Расстояние между отдельными символами схемы не должно быть менее 10 мм. Внутри блоков указывается информация, характеризующая выполняемые ими функции, которые записываются словесно или с помощью формул и обозначений. Записи внутри символа должны быть представлены так, чтобы их можно было читать слева направо и сверху вниз, независимо от направления потока. Содержание записей должно быть кратким и точным. Для удобства нахождения символа на схеме задают их координаты в виде цифр, которые проставляются сверху слева в разрыве его контура. Между удаленными друг от друга символами линию потока можно обрывать. В этом случае в конце и начале отрыва должен быть помещен символ "соединитель", поименованный буквой или цифрой. Наименованием соединителя является номер приемника управления.
Табл.1.
ОБОЗНАЧЕНИЕ |
НАИМЕНОВАНИЕ |
НАЗНАЧЕНИЕ |
Пуск, останов |
Начало, конец алгоритма |
|
|
Процесс |
Отображает функцию обработки данных любого вида. Внутри записывается содержание операции (элементарные действия, из которых состоит алгоритм; при решении математических задач это могут быть арифметические действия, например, |
|
|
Предопределённый процесс |
Отображает предопределённый процесс, состоящий из одной или нескольких операций . |
|
|
Данные |
Ввод исходных данных или вывод результатов. Внутри пишется слово “Ввод” или “Вывод” и перечисляются переменные, подлежащие вводу или выводу. |
|
|
Условие |
Отображает решение или функцию переключательного типа, имеющую один вход и несколько альтернативных выходов, лишь один из них может быть активизирован после вычисления условий, определённых внутри этого символа. Если внутри этого блока записывается условие в виде вопроса, то ответом на этот вопрос может быть только ДА и НЕТ. После выполнения этого действия возможны два пути дальнейшего решения задачи: если условие выполняется, то идем по ветке ДА, если не выполняется, то по ветке НЕТ. |
|
|
Подготовка |
Отображает модификацию команды или группы команд. Применяется для реализации цикла “Для” (For). Внутри пишутся параметры цикла: начальное и конечное значения переменной цикла, шаг изменения. |
|
|
Соединитель |
Указывает связь прерываемых линий потока. Внутри указывается наименование соединителя (номер символа, к которому следует перейти). |
|
|
Граница цикла |
Символ, состоящий из двух частей, отображает начало и конец цикла. Внутри пишутся условия для инициализации, приращения, завершения цикла. Они располагаются вначале или в конце в зависимости от расположения операции, проверяющей условие. Также указывается имя цикла. |
|
|
Коментарий |
Применяется для пояснения связи, содержания программы, для написания длинной формулы, которая не помещается внутри символа ”процесс”. |
Основные структуры алгоритмов - ограниченный набор стандартных способов соединения блоков алгоритма для выполнения типичных последовательностей действий. Структурный подход к разработке алгоритмов предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов. К основным структурам относятся:
|
следование |
ветвление |
|
обход |
цикл «ДО» |
|
цикл «ПОКА» |
цикл «ДЛЯ» |
Рис.1. Типовые структуры вычислительных процессов.
"СЛЕДОВАНИЕ" - последовательное размещение блоков и групп блоков
"ВЕТВЛЕНИЕ" применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие.
"ОБХОД" - частный случай "ВЕТВЛЕНИЯ", когда одна ветвь не содержит никаких действий.
Цикл "ДО" применяется при необходимости осуществлять какие-либо вычисления несколько раз до тех пор, пока выполняется некоторое условие. Особенность этого цикла состоит в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.
Цикл "ПОКА" отличается от "ДО" тем, что здесь проверка условия проводится до выполнения цикла. Если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.
Цикл «ДЛЯ» применяется, когда переменная цикла изменяется с известным шагом или цикл повторяется заданное количество раз.
Программа – запись алгоритма на языке, понятном ЭВМ. Такие языки называются языками программирования.
Языки программирования принято делить на 5 поколений:
На базе систем программирования для создания дополнительных удобств пользователей были созданы среды программирования.
Среда программирования – это программа, которая имеет способы автоматизации процессов подготовки и выполнения программ пользователя, а именно:
Благодаря этим возможностям среды программирования часто называют интегрированными или дружественными средами.
Примеры интегрированных сред:
Turbo Basic, Turbo Pascal 7.0, Borland Pascal for Windows, Delphi, Visual Basic и много других.
Контрольные вопросы:
PAGE 3
действие 1
действие 2
Да
Нет
Условие
действие 1
действие 2
ачальные присвоения
Тело цикла
Условие
Да
Нет
действие 1
Да
Нет
Условие
Начальные присвоения
Тело цикла
Условие
Да
Нет
Параметры цикла
Тело цикла