Основы технологии разработки программ. Этапы разработки программ

       2. ОСНОВЫ ТЕХНОЛОГИИ  РАЗРАБОТКИ ПРОГРАММ. ЭТАПЫ РАЗРАБОТКИ  ПРОГРАММ. ПОНЯТИЕ  АЛГОРИТМА, ЕГО  СВОЙСТВА, СПОСОБЫ  ОПИСАНИЯ. 

       Для подготовки информации к обработке  на ПЭВМ необходимо выполнить следующие  этапы:

1. Постановка задачи.
2. Формализация поставленной задачи.
3. Выбор численного метода и представление решения в виде структурной схемы(блок-схемы) (алгоритмизация).
4. Оформление задачи на входном языке ПЭВМ (программирование).
5. Ввод и отладка программы.
6. Выполнение программы и анализ полученных результатов.

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

       Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритма построены основные принципы программирования - составления программ для вычислительных машин.

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

       Алгоритм - это совокупность действий со строго определенными правилами выполнения.

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

       Приведем  свойства алгоритма:

1. Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).
2. Определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.
3. Результативность (или конечность) состоит в том, что за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
4. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

       Форма записи алгоритмов

       На  практике наиболее распространены следующие  формы представления алгоритмов:

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

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

       Пример 1

       если условие то действие1 иначе действие2

       Пример 2 Алгоритм нахождения наибольшего  общего делителя (НОД) двух натуральных  чисел (алгоритм Евклида).

1. задать два числа;
2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить большее из чисел;
4. заменить большее из чисел разностью большего и меньшего из чисел;
5. повторить алгоритм с шага 2.

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

       Словесный способ не имеет широкого распространения, так как такие описания:

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

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

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

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

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

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

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

       3. ЛИНЕЙНЫЕ И ВЕТВЯЩИЕСЯ  АЛГОРИТМЫ. ПРИМЕРЫ  ЗАПИСИ.

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

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

       Базовыми  элементами алгоритма являются:

• Следование.
• Ветвление.

       Следование 

       Базовая структура "следование" образуется последовательность действий, следующих  одно за другим (линейная последовательность): 

       Ветвление

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

             Структура ветвление  существует в четырех основных вариантах:

• если-то;
• если-то-иначе;
• выбор;
• выбор-иначе.

       Запись  ветвления выполняется в двух формах: полной и неполной.  

       Полная  форма:

       Неполная  форма:

       Пример: найти наименьшее из трех чисел.

       1 вариант решения: 

2. вариант решения:

       4. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ. ПРИМЕРЫ ЗАПИСИ.

       Цикл - управляющая структура, организующая многократное выполнение некоторой совокупности действий, которая называется телом цикла. 

       Виды  циклов

• С предусловием (пока)
• С постусловием (до)
• С параметром

       Цикл "пока" (цикл с предусловием):

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

        Цикл "до" (цикл с постусловием):

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

       Цикл  с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов.

       В блоке модификации указывается  закон изменения переменной параметра  цикла X.

       Xo - начальное значение параметра, h – шаг, Xn - последнее значение параметра. 

        Для создания циклов с параметром необходимо использовать правила:

1. Параметр цикла X, его начальное X₀ и конечное значения X_n и шаг h изменения параметра цикла должны быть одного типа
2. Запрещено изменять в теле цикла начальное и конечное значения, а также текущее значение параметра цикла.
3. Запрещено входить в цикл минуя его начала.
4. Если начальное значение больше конечного, то шаг - число отрицательное
5. Из цикла можно выйти принудительно не закончив его, тогда переменная параметра цикла сохраняет свое последнее значение.

       Рассмотрим  пример: Требуется вычислить значения функции , для a принимающим значения от 0 до 2π с шагом π/10, при любом допустимом значении (r= …). 
 
 
 
 
 
 

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

       5.МЕТОД НИСХОДЯЩЕГО ПРОЕКТИРОВАНИЯ АЛГОРИТМОВ. ПРИМЕРЫ.

1. Метод нисходящего проектирования

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

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

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

       Такая разработка алгоритмов получила название нисходящего проектирования.

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

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

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

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

       Рассмотрим пример:

       Дано:

1. значение   n=10.
2. вычислить по формуле элементы квадратной матрицы, размерность которой n*n.
3. по заданному правилу из матрицы получить компоненты вектора, состоящего из n компонентов.
4. выполнить сортировку составляющих матрицы или компонент вектора.
5. определить значение функции исходя из элементов матрицы или вектора.

       Модульная схема  алгоритма поставленной задачи имеет  вид:

6. АЛГОРИТМИЧЕСКИЙ ЯЗЫК ПАСКАЛЬ. АЛФАВИТ  ЯЗЫКА. ЭЛЕМЕНТЫ ЯЗЫКА: ДАННЫЕ. ПРИМЕРЫ.

       Язык  ПАСКАЛЬ удовлетворяет требованиям  всех категорий пользователей: язык предоставляет возможность работать в режиме диалога, что может быть весьма полезно при обучении студентов.

1. Алфавит языка Паскаль состоит из основных (базисных) символов, которые подразделяются на буквы, цифры и специальные символы:

       Буквы:

              от А до Z; от а до z и знак _ (подчеркивание)

       Цифры:

              0 1 2 3 4 5 6 7 8 9

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

              + - * / = ^ < > ( ) [ ] { } . , : ; ' # $

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

3. Данные — величины, обpабатываемые пpогpаммой. Имеется тpи основных вида данных: константы, пеpеменные и массивы.
1. Константы — это данные, которые зафиксированы в тексте программы и не изменяются в процессе ее выполнения.

       Пpимеpы  констант:

       числовые 7.5 , 12 ;

       логические Nrue (истина), False (ложь);

       символьные (содержат ровно один символ) "А" , "+" ;

       литеpные (содержат произвольное количество символов) "a0", "Мир", "" (пустая строка).

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

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

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

       7. ОСНОВНЫЕ ПОНЯТИЯ  ЯЗЫКА ПАСКАЛЬ:  АЛФАВИТ, КОНСТАНТЫ,  ПЕРЕМЕННЫЕ, СТАНДАРТНАЯ  ФУНКЦИЯ, ВЫРАЖЕНИЯ,  ПРАВИЛА ИХ ЗАПИСИ.

       Язык  ПАСКАЛЬ удовлетворяет требованиям  всех категорий пользователей: язык предоставляет возможность работать в режиме диалога, что может быть весьма полезно при обучении студентов.

       Основными понятиями любого алгоритмического языка в том числе и Паскаль  являются:

• Алфавит (символы).
• Имена (идентификаторы).
• Операции (арифметические, логические).
• Данные (константы, переменные и массивы).
• Выражения.
• Операторы (команды).

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

       Алфавит стандартного языка Паскаль содержит следующие  символы:

• - 26 букв латинского алфавита
• - арабские цифры
• - 32 буквы русского алфавита
• - специальные символы + – * / : , < > = . ‘ ; () [] {}

       Русскими  буквами поясняется текст в какой-либо конструкции языка Паскаль.

         К о н с т  а н т ы

          Тип констант  в  языке ПАСКАЛЬ  определяется по их виду:  константы  целого типа - это целые числа,  не содержащие десятичной точки,  константы действительного  типа - действительные числа,  логические  константы - логические значения TRUE и FALSE, символьные константы  – либо строки длиной в один  символ, либо конструкции вида #K или ^K.

          Язык ПАСКАЛЬ допускает использовать  синонимы для обозначения констант, в    этом  случае  текст   программы  содержит  раздел  описания

       констант, например: {}

       Пpимеpы  констант:

• числовые 7.5 , 12 ;
• логические True (истина), False (ложь);
• символьные (содержат ровно один символ) "А" , "+" ;
• литеpные (содержат произвольное количество символов) "a0", "Мир", "" (пустая строка).

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

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

        Выpажения — пpедназначаются для выполнения необходимых вычислений, состоят из констант, пеpеменных, указателей функций (напpимеp, exp(x)), объединенных знаками опеpаций.

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

       Различают выражения арифметические, логические и строковые.

       Арифметические  выражения служат для определения одного числового значения. Например, (1+sin(x))/2. Значение этого выражения при x=0 равно 0.5, а при x=p/2 — единице.

       Логические  выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Таким образом, логическое выражение может принимать только два значения — "истина" или "ложь" (да или нет). Рассмотрим в качестве примера логическое выражение x*x + y*y < r*r , определяющее принадлежность точки с координатами (x, y) внутренней области круга радиусом r c центром в начале координат. При x=1, y=1, r=2 значение этого выражения — "истина", а при x=2, y=2, r=1 — "ложь".

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