ТЕМА 1: Технология разработки алгоритмов

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

Методика разработки программы «сверху – вниз»

462.50K

Category:

programming

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

1. ТЕМА 1: Технология разработки алгоритмов

Содержание:
1.
2.
3.
4.
5.
Основные этапы решения задачи на ЭВМ
Алгоритм и способы его описания
Структурное программирование
Пошаговая разработка программ
Отладка и тестирование программ
1

2. Этапы решения задачи

1. Постановка задачи
2. Математическое описание задачи
3. Выбор численного метода решения задачи
4. Составление алгоритма решения
5. Программирование
6. Отладка программы
7. Решение задачи
2

3. 1. Постановка задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

10. 11. Понятие алгоритма

Алгоритмом называется совокупность правил, определяющих
последовательность действий для получения требуемого
результата. Другими словами это предписание, определяющее
процесс преобразования исходных данных в конечный результат.
Алгоритм обладает следующими свойствами:
♦ Определенность – алгоритм должен быть однозначно
понятым любым исполнителем. Благодаря этому свойству
процесс выполнения носит механический характер.
♦ Результативность – искомый результат должен получаться
за конечное число шагов.
♦ Массовость – алгоритм, разработанный для определенного
класса задач, должен быть пригоден для решения любой задачи
из этого класса.
11

12. Понятие алгоритма продолжение

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

13. Способы неформальной записи алгоритма

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

14.

Словесное описание алгоритма
При словесном описании алгоритма используется обычный язык,
но с более тщательным отбором используемых слов по
сравнению с обычной речью.
Алгоритм описывается в виде последовательности шагов,
определяется состав выполняемых действий и направление
дальнейших вычислений на каждом шаге. При этом, если на
текущем шаге не указывается номер следующего шага, то
осуществляется естественный переход к следующему шагу.
Действия на каждом шаге необходимо описывать кратко и
однозначно по смыслу.
ЗАДАЧА 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 части
корней.
14

15.

Словесное описание алгоритма
продолжение
Алгоритм может быть записан следующим образом:
Шаг 1. Вычислить 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’;– в случае комплексных корней.
15

16.

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

17.

1. Символы данных
1.1. Основные символы данных
1.1.1. Данные
Символ отображает данные, носитель данных не
определен.
1.1.2. Запоминаемые данные
Символ отображает хранимые данные в виде,
пригодном для обработки, носитель данных не
определен.
1.2. Специфические символы данных
1.2.1. Оперативное запоминающее устройство
Символ отображает данные, хранящиеся в
оперативном запоминающем устройстве.
1.2.2. Запоминающее устройство с
последовательным доступом
Символ отображает данные, хранящиеся в
запоминающем устройстве с последовательным
доступом (магнитная лента, кассета с магнитной
лентой, магнитофонная кассета).
17

18.

1. Символы данных продолжение
1.2.3. Запоминающее устройство с прямым
доступом
Символ отображает данные, хранящиеся в
запоминающем устройстве с прямым доступом
(магнитный диск, магнитный барабан, гибкий
магнитный диск).
1.2.4. Документ
Символ отображает данные, представленные на
носителе в удобочитаемой форме (машинограмма,
документ для оптического или магнитного
считывания, микрофильм, рулон ленты с итоговыми
данными, бланки ввода данных).
1.2.5. Ручной ввод
Символ отображает данные, вводимые вручную во
время обработки с устройств любого типа
(клавиатура, переключатели, кнопки, световое перо,
полоски со штриховым кодом).
18

19.

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

20.

2. Символы процесса
2.1. Основные символы, процесса
2.1.1. Процесс
Символ отображает функцию обработки данных любого
вида (выполнение определенной операции или
группы операций, приводящее к изменению
значения, формы или размещения информации или
к определению, по которому из нескольких
направлений потока следует двигаться).
2.2. Специфические символы процесса
2.2.1. Предопределенный процесс
Символ отображает предопределенный процесс,
состоящий из одной или нескольких операций или
шагов программы, которые определены в другом
месте (в подпрограмме, модуле).
2.2.2. Ручная операция
Символ отображает любой процесс, выполняемый
человеком.
20

21.

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

22.

2. Символы процесса продолжение
2.2.6. Граница цикла
Символ, состоящий из двух частей, отображает начало и конец цикла. Обе
части символа имеют один и тот же идентификатор. Условия для
инициализации, приращения, завершения и т. д. помещаются внутри
символа
Имя цикла,
условие
завершения
Имя цикла
Процесс
Процесс
Имя цикла
Условие
завершения, имя
цикла
22

23.

3. Символы линий
3.1. Основной символ линий
3.1.1. Линия
Символ отображает поток данных или управления.
При необходимости или для повышения удобочитаемости
могут быть добавлены стрелки-указатели.
3.2. Специфические символы линий
3.2.1. Передача управления
Символ отображает непосредственную передачу управления от одного процесса к другому, иногда с возможностью
прямого возвращения к инициирующему процессу после
того, как инициированный процесс завершит свои
функции.
Тип передачи управления должен быть назван внутри
символа (например, запрос, вызов, событие)
3.2.2. Канал связи
Символ отображает передачу данных по каналу связи.
3.2.3. Пунктирная линия
Символ отображает альтернативную связь между двумя или
более символами.
23

24.

4. Специальные символы
4.1. Соединитель
Символ отображает выход в часть схемы и вход из другой части этой
схемы и используется для обрыва линии и продолжения ее в
другом месте. Соответствующие символы-соединители должны
содержать одно и то же уникальное обозначение.
4.2. Терминатор
Символ отображает выход во внешнюю среду и вход из внешней
среды (начало или конец схемы программы, внешнее
использование и источник или пункт назначения данных).
4.3. Комментарий
Символ используют для добавления описательных комментариев
или пояснительных записей в целях объяснения или примечаний.
Пунктирные линии в символе комментария связаны с
соответствующим символом или могут обводить группу
символов. Текст комментариев или примечаний должен быть
помещен около ограничивающей фигуры.
4.4. Пропуск
Символ (три точки) используют в схемах для отображения пропуска
символа или группы символов, в которых не определены ни тип,
ни число символов. Символ используют только в символах линии
или между ними. Он применяется главным образом в схемах,
изображающих общие решения с неизвестным числом
повторений.
24

25.

Правила применения символов
1. Потоки данных или потоки управления в схемах показываются линиями.
Направление потока слева направо и сверху вниз считается стандартным. В
случаях, когда необходимо внести большую ясность в схему на линиях
используются стрелки. Если поток имеет направление, отличное от
стандартного, стрелки должны указывать это направление.
2. В схемах следует избегать пересечения линий. Пересекающиеся линии не имеют логической связи между собой, поэтому
изменения направления в точках пересечения не допускаются.
3. Две или более входящие линии могут объединяться в одну
исходящую линию. Если две или более линии объединяются
в одну линию, место объединения должно быть смещено.
4. Линии в схемах должны подходить к символу либо слева, либо сверху, а
исходить либо справа, либо снизу. Линии должны быть направлены к
центру символа.
5. При необходимости линии в схемах следует разрывать для
избегания излишних пересечений или слишком длинных линий,
а также, если схема состоит из нескольких страниц. Соединитель
в начале разрыва называется внешним соединителем, а
соединитель в конце разрыва - внутренним соединителем.
1
25
К ст

26.

Правила применения символов
продолжение
6. Несколько выходов из символа следует показывать:
♦ несколькими линиями от данного символа к другим символам;
♦ одной линией от данного символа, которая затем разветвляется в
соответствующее число линий.
7. Каждый выход из символа должен сопровождаться соответствующими
значениями условий, чтобы показать логический путь, который он
представляет, с тем, чтобы эти условия и соответствующие ссылки были
идентифицированы.
Данные А
A=B
Сравнить
А, В
A<B
A>B
комментарий 1
Значение
условия
Процесс 1
1
2
Данные B
комментарий 2
3
4
Процесс 2
5
Разветвления
Комментарии
26

27.

Пример блок-схемы алгоритма
Задача 2. Записать в виде блок–схемы алгоритм нахождения корней
квадратного уравнения Ax2+Bx+C=0 для любых действительных
переменных A, B, C.
Блок–схема алгоритма выглядит следующим образом:
Начало
D=B*B-4*A*C; R=-B/(2*A);
Q=sqrt(|D|)/(2*A);
Ввод
А, В, С
да
А=0
нет
да
REZ1=-(C/B); REZ2=0;
S=’A=0’;
REZ1=R+Q;
REZ2=R-Q;
S=’К.Д’;
D≥0
нет
REZ1=R;
REZ2=Q;
S=’К.К’;
Печать S,
REZ1, REZ2
Конец
27

28.

Виды графических схем алгоритмов
Способ неформального описания алгоритма в виде блок–схемы
обладает хорошей наглядностью и широко используется на
предварительном этапе составления алгоритма вычислительного
процесса непосредственно перед составлением программы для ЭВМ.
Рекомендуются три вида графических схем, отличающиеся уровнем
иерархии:
♦ Структурная схема. Отражает лишь крупные участки алгоритма без
раскрытия деталей. Блоки обработки и блоки проверки логических
условий обычно содержат словесные описания необходимых действий.
♦ Функциональная схема. Является наиболее распространенной. По
ней легко установить логику решения задачи и в тоже время от неё легко
перейти к написанию собственно программы. На функциональной схеме
должны быть показаны все основные циклы и разветвления, вызванные
проверкой логических условий. В блоках обработки можно писать как
словесные обозначения действий, так и формализованные операторы в
обобщенном виде.
♦ Принципиальная схема наиболее детально раскрывает этапы
решения задачи. Элементом схемы обязательно является
формализованный оператор.
28

29. 30. Понятие структурного программирования

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

31. Принципы структурного программирования

Принцип 1. Логика алгоритма и программы должна опираться на
минимальное число достаточно простых управляющих структур.
Используется 3 вида управляющих структур:
а) структура следования (линейный вычислительный процесс)
Блок–схема алгоритма состоит из цепочки вычислительных
блоков. Здесь S1, S2, S3 – блоки, определяющие одно или
несколько действий.
S1
S2
S3
б) структура ветвления
P – логическое выражение. В зависимости от Р
Вычислительный процесс может быть направлен
на выполнение блока S1 (истина) или блока S2 (ложь).
При этом один из блоков (S1 или S2) в данной
структуре может отсутствовать.
ложь
P
истина
S1
S2
31

32. Принципы структурного программирования

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

33. Принципы структурного программирования

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

34. 35. Методика разработки программы «сверху – вниз»

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

36. Этапы разработки программы

Пример. В массиве, состоящем из N целых чисел найти сумму
элементов, расположенных между максимальным и минимальным
элементами.
1. Общая структура программы
начало
1
Ввод элементов
массива
2
Вычисление
суммы S эл-тов от
max до min
3
Вывод
результатов
конец
36

37. Этапы разработки программы

2. Алгоритм первой части ("Ввод элементов массива")
1
i = 1;n
A[i]
37

38. Этапы разработки программы

3. Детализация второй части
2.1
Вычисление номеров
max и min элементов,
lmax и lmin
2.2 Определение границ
для суммирования
2.3
Вычисление суммы S
эл-тов, расположенных от lmax до lmin
38

39. Этапы разработки программы

4. Алгоритм части 2.1. ("Вычисление номеров max и min элементов")
max=A[1]; lmax=1
min=A[1];lmin=1
i = 2;n
A[i]>max
нет
да
max=A[i]
lmax=i
A[i]<min
нет
да
min=A[i]
lmin=i
39

40. Этапы разработки программы

5. Алгоритм части 2.2. ("Определение границ для суммирования")
нет
lmax<>lmin
нет
p:=lmin
q:=lmax
да
lmax<lmin
да
p:=lmax
q:=lmin
40

41. Этапы разработки программы

6. Алгоритм части 2.3. ("Вычисление суммы S элементов, расположенных
между lmax и lmin ")
S=0
i=p,q
S:=S+A[i]
7. Завершение алгоритма – часть 3 "Вывод на печать суммы S"
41

42. 43. Отладка и тестирование программы

Любая, даже очень аккуратно написанная программа может
содержать ошибки. Ошибки делятся на две категории:
1. Синтаксические – ошибки записи операторов языка. Эти
ошибки выявляются на этапе компиляции программы.
2. Семантические – ошибки в логической структуре
программы.
Семантические ошибки можно выявить на этапе отладки
программы с помощью специальных тестов.
Отладкой называется процесс поиска и устранения ошибок,
включающий многократную последовательность действий по
локализации и устранению ошибок.
Тестом называется набор входных данных, как правильных, так и
неправильных, используемых с целью нахождения максимально
возможного количества ошибок в программе.
43

44. Правила выбора тестов

1. Начинать следует с простых тестов, постепенно переходя к
более сложным.
2. Каждый оператор в процессе тестирования должен быть
выполнен хотя бы один раз. Для этого по блок–схеме алгоритма
проверяется, в каждом ли направлении выполняются условные
переходы.
3. Обеспечить проверку функционирования программы в
нормальных условиях, стараясь использовать простые данные и
ограничивая их объем.
4. Использовать для проверки специальные значения, например, 0,
1 или пустая строка.
44

45. Правила выбора тестов

5. Обеспечить проверку функционирования программы в
экстремальных условиях:
а) граничные значения (на границе области допустимых
величин):
♦ очень больших;
♦ очень малых;
♦ данные отсутствуют;
б) граничные объемы информации:
♦ 0 или 1 элемент массива;
♦ 1 строка или 1 столбец матрицы.
6. Для циклов обеспечить тройную проверку:
♦ обход тела цикла;
♦ однократное выполнение;
♦ максимальное число выполнений.
45

English Русский Rules