Основы программирования (Иванова Г.С. Основы программирования), страница 3

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

ПроектированиеПринято различать логическое и физическое проектирование. Логичес­кое проектирование не учитывает особенностей среды, в которой будет вы­полняться программа (технические и программные средства компьютера).При выполнении физического проектирования все эти параметры должныбыть учтены.Логическое проектирование. Логическое проектирование при проце­дурном подходе предполагает детальную проработку последовательностидействий будущей программы. Его начинают с определения структуры буду­щего программного продукта: отдельная программа или программная систе­ма, состоящая из нескольких взаимосвязанных программ. Затем переходят кразработке алгоритмов программ.14/. Этапы создания программного обеспеченияАлгоритмом называют формально описанную последовательность дей­ствий, которые необходимо выполнить для получения требуемого результа­та.Различают последовательности действий (вычислений) линейной, раз­ветвленной и циклической структуры.Линейная структура процесса вычислений предполагает, что для получе­ния результата необходимо выполнить некоторые операции в определеннойпоследовательности.

Например, для определения площади треугольника поформуле Герона необходимо сначала определить полупериметр треугольни­ка, а затем по формуле его площадь.Разветвленная структура процесса вычислений предполагает, что кон­кретная последовательность операций зависит от значений одного или не­скольких параметров. Например, если дискриминант квадратного уравненияне отрицателен, то уравнение имеет два корня, а если отрицателен, то дейст­вительных корней нет.Циклическая структура процесса вычислений предполагает, что для по­лучения результата некоторые действия необходимо выполнить несколькораз. Например, для того, чтобы получить таблицу значений функции на за­данном интервале изменения аргумента с заданным шагом, необходимо со­ответствующее количество раз определить следующее значение аргумента ипосчитать для него значение функции.Процессы вычислений циклической структуры в свою очередь можноразделить на три группы:• циклические процессы, для которых количество повторений извест­но ~ счетные циклы или циклы с заданным количеством повторений',• циклические процессы, завершающиеся по достижении или наруше­нии некоторых условий - итерационные циклы;• циклические процессы, из которых возможны два варианта выхода:выход по завершении процесса и досрочный выход по какому-либо дополни­тельному условию - поисковые циклы.Формальное описание алгоритмов осуществляют с использованиемсхем алгоритмов и псевдокодов.На изображение схем алгоритмов существует ГОСТ 19.701-90, согласнокоторому каждой группе действий ставится в соответствие блок особой фор­мы.

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

При переходе на другой лист или получении управления с друго15Часть L Основы алгоритмизации и процедурноепрограммированиеТаблицаНазвание блокаОбозначение1.1Назначение блока1I( Действие JНачало, завершение программыили подпрограммыДействиеОбработка данных (вычисления,пересылки и т. п.)I Терминаторij' Процесс/ДанныеРешениеДанные/Операции ввода-выводаВетвления, выбор, итерационныеи поисковые циклыУсловие^/действияЧПодготовкаiСчетные циклыНачалоГраница циклаЛюбые циклыКонецк-Предопределенныйпроцесс1 \ИмяВызов процедурСоединительМаркировка разрывов линийI{ Комментарийi::;{Комментарий•Пояснения к операциямго листа в комментарии указывается номер листа, например «с листа 3» «налист 1».В теории программирования доказано, что для записи любого скольугодно сложного алгоритма достаточно трех базовых структур:• следование - обозначает последовательное выполнение действий(рис. 1.2, а);• ветвление - соответствует выбору одного из двух вариантов действий(рис.

1.2,6);• цикЛ'Пока - определяет повторение действий, пока не будет нарушеноусловие, выполнение которого проверяется в начале цикла (рис. 1.2, в).16/. Эт<ты создант программного обеспеченияДействие 1IДействие 2«^-Л'словиГ--^Действие 1нетДействие 2"ЕРис. 1.2. Базовые алгоритмические структуры:следование (а), ветвление (б) и цикл-пока (в)Помимо базовых структур используют три дополнительные структуры,производные от базовых:• выбор - выбор одного варианта из нескольких в зависимости отзначения некоторой величины (рис. 1.3, а);• цикл'до ~ повторение некоторых действий до выполнения заданногоусловия, проверка которого осуществляется после выполнения действий вцикле (рис. 1.3, в);• цикл с заданным числом повторений {счетный цикл) - повторениенекоторых действий указанное число раз (рис.

1.3, д).На рис. 1.3, б, г и е показано, как каждая из дополнительных структурможет быть реализована через базовые структуры.Перечисленные структуры были положены в основу структурного про­граммирования - технологии, которая представляет собой набор рекоменда­ций по уменьшению количества ошибок в программах [4, 8]. В том случае,если в схеме алгоритма отсутствуют другие варианты передачи управления,алгоритм называют структурным^ подчеркивая, что он построен с учетомрекомендаций структурного программирования.Схема алгоритма детально отображает особенности разработанного ал­горитма. Иногда такой высокий уровень детализации не позволяет выделитьсуть алгоритма. В этих случаях для описания алгоритма используют псевдо­код.Псевдокод - описание алгоритма, которое базируется на тех же основ­ных структурах, что и структурные схемы алгоритма.

Описать на псевдоко­де неструктурный алгоритм нельзя.Для каждой структуры используют свою форму описания. В литературебыли предложены несколько вариантов форм псевдокодов. Один из вариан­тов приведен в табл. 1.2.Пример L2, Разработать алгоритм определения наибольшего общегоделителя двух натуральных чисел.17Часть I. Основы алгоритмизации и процедурное программированиенетДействие 1Действие 2Действие 3П"ДействиеДействиенет _ Условиеда>словие^ "^даДействие1=п1i=nl,n2,hТнетДействиеИЗРис.1.3. Дополнительные структуры и их реализация через базовые структуры:выбор (а-б), цикл-до (в-г) и цикл с заданным числом повторений (д--€)Существует несколько способов определения наибольшего общего де­лителя двух натуральных чисел. Самым простым из них является так назы­ваемый алгоритм Евклида.

Суть этого метода заключается в последователь-18/. Этапы создания программногообеспеченияТаблицаСтруктураСледованиеПсевдокод<действие 1><действие 2>...Структура.ВыборЕсли <условие>то<действие 1>иначе <действие2>Все-еслиЦикл'пока <условие><действие>Все-циклВетвлениеЦикл-покаj Цикл с! заданнымколичеством[^повторений' Цикл-до|11.2ПсевдокодВыбор <код><код1>: <действие 1><код2>: <действие 2>Все-выборДля <индекс> =<n>,<k>,<h><действие>Все-циклВыполнять<действие>_Др.?УСлр1ие>ной замене большего из чисел на разность большего и меньшего. Вычисле­ния заканчиваются, когда числа становятся равны.