Технология разработки алгоритмов. Этапы решения задачи на ЭВМ. Структурное программирование. Пошаговая разработка программ презентация

способы его описания
Структурное программирование
Пошаговая разработка программ
Отладка и тестирование программ

Математическое описание задачи

3. Выбор численного метода решения задачи

4. Составление алгоритма решения

5. Программирование

6. Отладка программы

7. Решение задачи

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

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

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

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

на одном из входных языков машины - это может быть язык низкого уровня, близкий к машинному языку, (например, ассемблер) или один из алгоритмических языков, близких к формульному описанию алгоритмов (Basic, Pascal, Fortran, C, C++).
В зависимости от уровня входного языка выполняется более или менее детальное разбиение алгоритма решения на элементарные шаги и запись каждого из них в виде эквивалентной конструкции языка (в виде команд или операторов).
Программа, реализующая заданный алгоритм, представляет собой совокупность команд или операторов входного языка ЭВМ и исходных данных. На машинный язык программа переводится с помощью специальной программы, называемой компилятором (или транслятором).

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

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

программирование
Пошаговая разработка программ
Отладка и тестирование программ

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

Алгоритм обладает следующими свойствами:

♦ Определенность – алгоритм должен быть однозначно понятым любым исполнителем. Благодаря этому свойству процесс выполнения носит механический характер.

♦ Результативность – искомый результат должен получаться за конечное число шагов.

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

называется алгоритмизацией. Цепочка выполняемых действий называется алгоритмическим процессом, каждое элементарное действие – его шагом.
Для того чтобы реализовать алгоритм на ЭВМ, необходимо записать его на одном из языков программирования. В большинстве случаев особенно при решении сложных задач этапу непосредственного программирования предшествует этап неформальной записи алгоритма.
Неформальная запись алгоритма преследует следующие цели:
♦ сделать запись алгоритма наглядной, понятной для человека, не обладающего специальными знаниями в области программирования;
♦ выявить пути экономии в количестве выполняемых операций и используемых величин, что связано, соответственно, со временем выполнения алгоритма и объемом используемой памяти ЭВМ;
♦ произвести предварительную оценку алгоритма и выбрать те или иные конструкции алгоритмического языка с точки зрения эффективности и компактности программы

неформальной записи алгоритмов вычислительных процессов:

♦ словесное описание алгоритма;

♦ описание с помощью блок-схем.

Независимо от принятого способа записи алгоритма, прежде всего, необходимо определить структуру данных, используемых в алгоритме.
Данные могут быть трех видов:
1. исходные данные, значения которых известны до выполнения алгоритма;
2. промежуточные данные, являющиеся вспомогательными в процессе выполнения алгоритма;
3. результирующие данные, получаемые в итоге выполнения алгоритма.

с более тщательным отбором используемых слов по сравнению с обычной речью.
Алгоритм описывается в виде последовательности шагов, определяется состав выполняемых действий и направление дальнейших вычислений на каждом шаге. При этом, если на текущем шаге не указывается номер следующего шага, то осуществляется естественный переход к следующему шагу.
Действия на каждом шаге необходимо описывать кратко и однозначно по смыслу.
ЗАДАЧА 1. Записать алгоритм вычисления корней квадратного уравнения Ax2+Bx+C=0 при A≠0.
Известно, что корни квадратного уравнения вычисляются по формуле: x1,2=-B/(2A)±(√D)/(2A), D=B2-4AC.
Обозначим R=-B/(2A), Q= (√D)/(2A) .
Если D≥0, то корни действительные: x1=R+Q, x2=R-Q .
Если D<0, то корни комплексно–сопряженные x1=R+iQ, x2=R-iQ. В этом случае достаточно напечатать действительную R и мнимую Q части корней.

Словесное описание алгоритма

R=-B/(2×A), D=B2-4 × A × C;

Шаг 2. Если D<0, то перейти на шаг 4;

Шаг 3. Вычислить Q= (√D)/(2 × A) , Rez1=R+Q, Rez2=R-Q, S=‘К.Д’, перейти на шаг 5;

Шаг 4. Вычислить Q= (√-D)/(2 × A) , Rez1=R, Rez2=Q, S=‘К.K’;

Шаг 5. Печать S, Rez1, Rez2;

Шаг 6. Конец.

Здесь переменная S имеет значения текстовых констант:
‘К.Д’– в случае действительных корней,
‘К.K’;– в случае комплексных корней.

Словесное описание алгоритма продолжение

изображение его в виде блок–схемы.
В этом случае шаги выполнения алгоритма записываются в виде блоков различной формы, а связь между ними обозначается стрелками, выходящими из блока.
Правила начертания графических схем алгоритмов изложены в ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения".

Описание алгоритма в виде блок-схем

1.1.2. Запоминаемые данные
Символ отображает хранимые данные в виде, пригодном для обработки, носитель данных не определен.

1.2. Специфические символы данных

1.2.1. Оперативное запоминающее устройство
Символ отображает данные, хранящиеся в оперативном запоминающем устройстве.

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

1. Символы данных

запоминающем устройстве с прямым доступом (магнитный диск, магнитный барабан, гибкий магнитный диск).

1.2.4. Документ
Символ отображает данные, представленные на носителе в удобочитаемой форме (машинограмма, документ для оптического или магнитного считывания, микрофильм, рулон ленты с итоговыми данными, бланки ввода данных).

1.2.5. Ручной ввод
Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штриховым кодом).

1. Символы данных продолжение

магнитные карты, карты со считываемыми метками, карты с отрывным ярлыком, карты со сканируемыми метками).

1.2.7. Бумажная лента
Символ отображает данные, представленные на носителе в виде бумажной ленты.

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

1. Символы данных продолжение

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

2.2. Специфические символы процесса

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

2.2.2. Ручная операция
Символ отображает любой процесс, выполняемый человеком.

2. Символы процесса

на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы).

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

2.2.5. Параллельные действия
Символ отображает синхронизацию двух или более параллельных операций.

2. Символы процесса продолжение

цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т. д. помещаются внутри символа

2. Символы процесса продолжение

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

3.2. Специфические символы линий

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

3.2.2. Канал связи
Символ отображает передачу данных по каналу связи.

3.2.3. Пунктирная линия
Символ отображает альтернативную связь между двумя или более символами.

3. Символы линий

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

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

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

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

4. Специальные символы

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

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

3. Две или более входящие линии могут объединяться в одну
исходящую линию. Если две или более линии объединяются
в одну линию, место объединения должно быть смещено.

4. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

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

Правила применения символов

линиями от данного символа к другим символам;

♦ одной линией от данного символа, которая затем разветвляется в соответствующее число линий.

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

Правила применения символов продолжение

Разветвления

Комментарии

Ax2+Bx+C=0 для любых действительных переменных A, B, C.

Блок–схема алгоритма выглядит следующим образом:

Пример блок-схемы алгоритма

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

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

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

♦ Принципиальная схема наиболее детально раскрывает этапы решения задачи. Элементом схемы обязательно является формализованный оператор.

Виды графических схем алгоритмов

программирование
Пошаговая разработка программ
Отладка и тестирование программ

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

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

Используется 3 вида управляющих структур:

а) структура следования (линейный вычислительный процесс)

Блок–схема алгоритма состоит из цепочки вычислительных
блоков. Здесь S1, S2, S3 – блоки, определяющие одно или
несколько действий.




б) структура ветвления

P – логическое выражение. В зависимости от Р
Вычислительный процесс может быть направлен
на выполнение блока S1 (истина) или блока S2 (ложь).
При этом один из блоков (S1 или S2) в данной
структуре может отсутствовать.

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

Цикл с предусловием Цикл с постусловием

Величины, меняющиеся в цикле, называются параметрами цикла.

и понимания.

Принцип 3. Законченная часть программы должна быть размещена в пределах экрана.

Принцип 4. Не рекомендуется использовать оператор GOTO.

Оператор GOTO – оператор безусловного перехода. Наличие в программе многочисленных безусловных переходов делает ее трудно читаемой. После нескольких переходов из одной точки программы в другую читатель может потерять логику вычислительного процесса.
Профессор Э. Дейкстра в 1965 г. высказал предположение, что оператор GOTO может быть исключен из языков программирования. Считается, что именно с этого времени и началось структурное программирование. В языке «С» оператор GOTO присутствует, но его использование считается дурным тоном.

программирование
Пошаговая разработка программ
Отладка и тестирование программ

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

3. Устанавливаются связи между ними по обрабатываемым данным.

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

5. Убедившись в правильности работы в целом, можно переходить к детализации каждой отдельной части.

целых чисел найти сумму элементов, расположенных между максимальным и минимальным элементами.

1. Общая структура программы

элементов")

между lmax и lmin ")

7. Завершение алгоритма – часть 3 "Вывод на печать суммы S"

программирование
Пошаговая разработка программ
Отладка и тестирование программ

программа может содержать ошибки. Ошибки делятся на две категории:

1. Синтаксические – ошибки записи операторов языка. Эти ошибки выявляются на этапе компиляции программы.
2. Семантические – ошибки в логической структуре программы.

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

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

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

более сложным.

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

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

4. Использовать для проверки специальные значения, например, 0, 1 или пустая строка.

а) граничные значения (на границе области допустимых величин):
♦ очень больших;
♦ очень малых;
♦ данные отсутствуют;

б) граничные объемы информации:
♦ 0 или 1 элемент массива;
♦ 1 строка или 1 столбец матрицы.

6. Для циклов обеспечить тройную проверку:
♦ обход тела цикла;
♦ однократное выполнение;
♦ максимальное число выполнений.