Силаенков А.Н. Лекции по технологии программирования

Подождите немного. Документ загружается.

государства и власти; экономическая модель развития общества; структурное

построение языка и т. д.

Естественные языки служат для создания описательных

информационных моделей. В истории науки известны многочисленные

описательные информационные модели. Например, гелиоцентрическая

модель мира, которую предложил Коперник, формулировалась следующим

образом:

9999-99 Земля вращается вокруг своей оси и вокруг Солнца;

9999-99 орбиты всех планет проходят вокруг Солнца.

999999С помощью формальных языков строятся формальные информационные

модели (математические, логические и др.). Процесс построения

информационных моделей с помощью формальных языков называется

формализацией.

999999Одним из наиболее широко распространенных формальных языков

является математический. Модели, сформированные с использованием

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

Язык математики представляет собой совокупность формальных языков :

алгебраический, геометрический.999999Язык алгебры позволяет формализовать

функциональные зависимости между величинами.

999999Язык алгебры логики (алгебры высказываний) дает возможность

строить формальные логические модели. С помощью алгебры высказываний

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

сложные высказывания, выраженные на естественном языке. Путем

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

логические модели устройств компьютера (сумматора, триггера) и т. д.

999999В процессе познания окружающего мира человечество постоянно

прибегает к моделированию и формализации.

99Статистические и динамические модели.9Описание состояния

объекта и описание изменения состояния объекта производится с помощью

статических и динамических информационных моделей.

999999Система состоит из объектов, которые называются элементами системы.

Между элементами системы существуют различные связи и отношения.

Например, компьютер является системой, состоящей из различных

устройств, при этом устройства связаны между собой и аппаратно

(физически подключены друг к другу) и функционально (между

устройствами происходит обмен информацией).

999999Важным признаком системы является ее целостное функционирование.

Компьютер нормально работает до тех пор, пока в его состав входят и

являются исправными основные устройства (процессор, память, системная

плата и т. д.). Если удалить одно из них, например процессор, компьютер

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

999999Любая система находится в пространстве и времени. Состояние системы

в каждый момент времени характеризуется ее структурой, т. е. составом,

свойствами элементов, их отношениями и связями между собой. Так,

структура Солнечной системы характеризуется составом входящих в нее

объектов (Солнце, планеты и пр.), их свойствами (скажем, размерами) и

взаимодействием (силами тяготения).

999999Модели, описывающие состояние системы в определенный момент

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

999999Состояние систем изменяется во времени, т. е. происходят процессы

изменения и развития систем.999999Модели, описывающие процессы изменения

и развития систем, называются динамическими информационными

моделями.

999999В физике динамические информационные модели описывают движение

тел, в биологии - развитие организмов или популяций животных, в химии -

процессы прохождения химических реакций и т. д.

2. Алгоритмы.

Слово "алгоритм" является производным от имени среднеазиатского

ученого ал-Хорезми, уроженца Хивы, жившего в IX в. н. э. На основании его

трудов в средние века были сформулированы основные правила арифметики.

В латинском переводе все правила начинались со слов "ал-Хорезми сказал",

что потом транспонировалось в "алгоритм гласит".

Алгоритм - заранее определенное, точное предписание, которое задает

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

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

должен обладать следующими свойствами:

o дискретность - каждый алгоритм должен быть разбит на конечное

число законченных действий;

o детерминированность (определенность) - каждое действие должно

быть понятно исполнителю (для каждого алгоритма предполагается

конкретный исполнитель) и содержать действия над известными

данными;

o результативность - каждый алгоритм направлен на решение

конкретной задачи, а следовательно, на получение определенного

результата;

o массовость - алгоритм необходимо составить так, чтобы с его помощью

можно было решать подобные задачи.

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

o линейный алгоритм - последовательность действий (команд);

Последовательной называется такая структура алгоритма, при которой его

отдельные части (операторы) выполняются поочередно одна за другой. В

качестве примера рассмотрим алгоритм заварки чая.

Начало

Вскипятить воду.

Ополоснуть чайник кипятком.

Положить туда чай.

Залить чайник кипятком.

Конец

Блок-схема базовой структуры следования:

Рис. 3. Блок – схема линейного алгоритма

999В Delphi последовательный алгоритм реализован в виде составного

оператора

Begin оператор; оператор; … оператор End

o разветвляющийся алгоритм

алгоритм ветвления - выбор действия в зависимости от выполнения

условия;

)

Рис.4.Блок- схемы алгоритмов ветвления

o циклический алгоритм - некоторые действия повторяются

определенное количество раз или пока не выполнится условие;

Рис.5. Блок- схема циклического алгоритма

999999 Цикл, для которого нельзя указать числа повторений, и проверка

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

итерационным.

Цикл - пока

(может не выполняться ни разу)

Цикл - до

(выполняется хотя бы

раз)

Рис.6. Блок- схемы циклических алгоритмов

Пусть необходимо из двух чисел, A и B, выбрать большее и поместить его

значение в переменную M. Алгоритм такого выбора можно записать так:

999если A > B, то M = A , иначе M = B.

999При выполнении алгоритма сначала вычисляется условие. Если условие

истинно, выполняется оператор после слова "то", если условие ложно -

оператор после слова "иначе".

999Большинство языков программирования имеют специальную конструкцию

для реализации алгоритма выбора - условный оператор. Например, в Delphi

выбор числа будет выглядеть так:

999if A > B then M := A

else M := B;

o Рекусивный алгоритм обращается к самому себе, пока не

выполнится определенное условие

Примечание*. Рекурсивные функции – такие функции, значения

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

предшествующих аргументов.

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

телефонного автомата; правила пользования банкоматом; решение систем

уравнений методом Гаусса.

Структурное программирование.

При программировании следует иметь в виду, что программа должна

быть понятной не только компьютеру, но и человеку.

В связи с этим Дейкстра и предложил строить программу как

композицию из вышерассмотренных типов управляющих конструкций

(структур). Программирование с использованием только таких конструкций

назвали структурным.

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

Следова

ние

Не

Повторение

Рис. 7. Основные управляющие конструкции структурного

программирования.

Основными конструкциями структурного программирования являются:

следование, разветвление и повторение (Рис. 7). Компонентами этих

конструкций являются обобщенные операторы S, S1, S2 и условие

(предикат) P. В качестве обобщенного оператора может быть либо простой

оператор используемого языка программирования (операторы присваивания,

ввода, вывода, обращения к процедуре), либо фрагмент программы,

являющийся композицией основных управляющих конструкций

структурного программирования. Существенно, что каждая из этих

конструкций имеет по управлению только один вход и один выход. Тем

самым, и обобщенный оператор имеет только один вход и один выход.

Весьма важно также, что эти конструкции являются уже

математическими объектами (что, по существу, и объясняет причину успеха

структурного программирования). Доказано, что для каждой

неструктурированной программы можно построить функционально

эквивалентную (т.е. решающую ту же задачу) структурированную

программу. Для структурированных программ можно математически

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

некоторые ошибки.

Структурное программирование иногда называют еще

"программированием без GO TO". Однако дело здесь не в операторе GO TO,

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

избегать употребления оператора перехода всюду, где это возможно, но не

ценой ясности программы. К полезным случаям использования оператора

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

условию, "досрочно" прекращающего работу данного цикла или данной

процедуры.

Вопросы для самопроверки

1. Два класса моделей.

2. Классификация информационных моделей.

3. Алгоритм и его свойства.

4. Приведите примеры алгоритмов

5. Что такое линейный алгоритм и его структура?

6. Что такое алгоритм с ветвлением?

7. Что такое циклический алгоритм?

8. Что такое структурное программирование?

9. Укажите основные управляющие конструкции структурного

программирования.

Лекция№3. Пошаговая детализация - основной метод построения

текста программного модуля

1. Способы записи алгоритмов

Структурное программирование дает рекомендации о том, каким

должен быть текст программы. Возникает вопрос, как должен действовать

программист, чтобы построить такой текст. Часто программирование модуля

начинают с построения его блок-схемы, описывающей в общих чертах

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

логику работы модуля, при их ручном кодировании на языке

программирования возникают ошибки: отображение двумерных структур,

какими являются блок-схемы, на линейный текст, представляющий

программу, может привести к искажению логики работы модуля

В качестве основного метода построения текста модуля современная

технология программирования рекомендует пошаговую детализацию.

Сущность этого метода заключается в разбиении процесса разработки текста

программы на ряд шагов.

На первом шаге описывается общая схема работы программы в

обозримой линейной текстовой форме, причем это описание не является

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

На каждом следующем шаге производится уточнение и детализация

одного из понятий (будем называть его уточняемым), в каком либо

описании, разработанном на одном из предыдущих шагов.

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

языке программирования путем замены вхождений конструкций

структурного программирования средствами языка программирования.

Пошаговая детализация связана с использованием частично

формализованного языка для представления указанных описаний, который

получил название псевдокода. Этот язык позволяет использовать все

конструкции структурного программирования, которые оформляются

формализовано.

Для каждого неформального обобщенного оператора должно быть

создано отдельное описание, выражающее логику его работы

(детализирующее его содержание) с помощью композиции основных

конструкций структурного программирования и других обобщенных

операторов. В качестве заголовка такого описания должно быть

неформальное обозначение детализируемого обобщенного оператора.

Основные конструкции структурного программирования могут быть

представлены в следующем виде (рис. 8).

Рис.8.Запись на псевдокоде базовых конструкций структурного

программирования

Следование:

обобщенный_оператор

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

ЕСЛИ условие ТО

обобщенный_оператор

ИНАЧЕ

обобщенный_оператор

ВСЕ ЕСЛИ

Повторение:

ПОКА условие ДЕЛАТЬ

обобщенный_оператор

ВСЕ ПОКА

Здесь условие может быть либо явно задано на базовом языке

программирования в качестве булевского выражения, либо неформально

представлено на естественном языке некоторым фрагментом, раскрывающим

в общих чертах смысл этого условия. В последнем случае должно быть

создано отдельное описание, детализирующее это условие, с указанием в

качестве заголовка обозначения этого условия (фрагмента на естественном

языке).

Рис. 9. Частные случаи оператора перехода в качестве обобщенного

оператора.

В качестве обобщенного оператора на псевдокоде можно использовать

указанные выше частные случаи оператора перехода (см. рис.9).

Последовательность обработчиков исключительных ситуаций (исключений)

задается в конце модуля или описания процедуры (функции). Каждый такой

обработчик имеет вид:

ИСКЛЮЧЕНИЕ имя_исключения

обобщенный_оператор

ВСЕ ИСКЛЮЧЕНИЕ

Выход из повторения (цикла):

ВЫЙТИ

Выход из процедуры

(функции):

ВЕРНУТЬСЯ

Переход на обработку

исключительной ситуации:

ВОЗБУДИТЬ

имя_исключения

Отличие обработчика исключительной ситуации от процедуры без

параметров заключается в следующем: после выполнения процедуры

управление возвращается к оператору, следующему за обращением к ней, а

после выполнения исключения управление возвращается к оператору,

следующему за обращением к модулю или процедуре (функции), в конце

которого (которой) помещено данное исключение.

Рекомендуется на каждом шаге детализации создавать достаточно

содержательное описание, но легко обозримое (наглядное), так чтобы оно

размещалось на одной странице текста. Как правило, это означает, что такое

описание должно быть композицией пяти-шести конструкций структурного

программирования. Рекомендуется также вложенные конструкции

располагать со смещением вправо на несколько позиций (см. рис.9). В

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

конкурентное с блок-схемами, но обладающее существенным

преимуществом  сохраняется линейность описания.

Пример1. З а д а ч а. Ввести X и подсчитать значение функции Sin X по

формуле:

999Р ешение. Покажем пример записи алгоритма на псевдокоде.

Начало

Ввести X;

Подсчитать сумму SinX;

Вывести сумму SinX на экран.

Конец

Пример2. Покажем пример записи на псевдокоде алгоритма,

который вводит числа с клавиатуры и складывает их, пока не будет введено

число 0. Накопленная сумма выводится на экран.

Начало

Занести в переменную сумму S число 0;

Ввести с клавиатуры число X;

Пока Х не равно 0 повторять

Начало

Добавить к сумме S значение Х;

Ввести с клавиатуры число X;

Конец;

Сумму S вывести на экран дисплея;

Конец.