СТРАТЕГИЯ СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ сверху-вниз
Пример абстракции и уточнения.
Систему хранения идентификаторов пользователей Интернет-магазина можно представить как множество целых чисел, забыв о том, что эти числа — идентификаторы пользователей, и о том, что все это как-то связано с Интернет-магазином.
2) принцип формализации. Этот принцип предполагает строгий методический подход и дает основания для доказательства правильности программ.
3) принцип "разделяй и властвуй" предполагает разделение проблемы на множество мелких независимых задач, которые легче понимать и решать. Т.е. означает разделение программы на отдельные фрагменты (модули), которые просты по управлению и допускают независимую отладку и тестирование.
Модульность — принцип организации больших систем в виде наборов подсистем, модулей или компонентов. Этот принцип предписывает организовывать сложную систему в виде набора более простых систем — модулей, взаимодействующих друг с другом через четко определенные интерфейсы. При этом каждая задача, решаемая всей системой, разбивается на более простые, решаемые отдельными модулями подзадачи, решение которых, будучи скомбинировано определенным образом, дает в итоге решение исходной задачи. После этого можно отдельно рассматривать каждую подзадачу и модуль, ответственный за ее решение, и отдельно — вопросы интеграции полученного набора модулей в целостную систему, способную решать исходные задачи.
4) принцип иерархического упорядочения, т.е. не просто "разделяй и
властвуй", а так разделять, чтобы сохранялась сруктурированная взаимосвязь между модулями комплекса.
Таким образом, структурный подход к разработке ПО заключается в его декомпозиции (разбиении) на автоматизируемые функции (подпрограммы, процедуры, модули). Система разбивается на функциональные подсистемы, которые в свою очередь делятся на подфункции, подразделяемые на задачи и подзадачи.
Это были основные цели и принципы технологии структурного программирования
Фундаментом любой технологии программирования является стратегия
программирования.
Разлачают различные стратегии программирования
"сверху-вниз"- нисходящая;
"снизу-вверх"- восходящая;
"изнутри-наружу";
"снаружи-внутрь".
--------------------------------------------------------¬
¦ Структурное программирование - модульное нисходящее ¦
¦ пошаговое проектирование алгоритма и структур данных ¦
L--------------------------------------------------------
Стратегия "сверху-вниз" включает три составляющие:
1) нисходящая разработка;
2) структурное кодирование (программирование);
3) сквозной контроль.
Нисходящая разработка - это подход к разработке программного обеспечения, при котором оно разбивается на программные модули (подпрограммы, процедуры, функции), образующие многоуровневую структуру.
Каждый модуль представляет собой достаточно короткую программу, решающую отдельную задачу (подзадачу). В процессе разработки модули нижележащих уровней заменяются "заглушками". Таким образом, в любой момент разработки программного комплекса имеется его действующий вариант. Тестирование и отладка отдельных модулей и программного комплекса в целом ведется по ходу его проектирования.
Сначала проектируется модуль основной программы, далее подпрограммы, вызываемые основным модулем, затем подпрограммы, вызываемые этими уже спроектированными подпрограммами, и т.д. двигаясь в направлении от блоков высшего уровня к более низшего.
Основной принцип: разработка алгоритма начинается сверху с самых общих сведений о задаче и производится по уровням (шагам) вниз до окончательной записи алгоритма или программы.
Вначале принимаются общие решения, более мелкие оставляются.
Каждый шаг детализации не должен быть слишком большим - не нужно стремиться к охвату сразу всех деталей.
На верхнем уровне алгоритм представляется в виде некоторой иерархической схемы, элементы которой описываются на естественном для данной проблемы языке.
При этом на каждом шаге указывается что надо делать, но не раскрывается то, как это должно быть сделано.
Если полученные шаги можно рассматривать как единое целое и последовательное их выполнение приведет к успешному решению проблемы, то можно перейти с следующей стадии разработки алгоритма.
Далее каждый шаг разбивается на более мелкие. При этом на каждом шаге нужно принимать решения не только о программе, но и о данных.
Этот процесс детализации повторяется необходимое число раз.
Детализировать можно сразу все блоки предыдущей детализации или по частям. Причем, может отменяться уже принятое решение, если на очередном шаге детализации приводит к усложнению программы или структур данных.
Участки алгоритма, требующие детализации, обозначаются блоками "детализируемая программа".
Полностью заимствованные части алгоритма обозначаются блоками "предопределенный процесс"
Конечным уровнем детализации алгоритма является такой, при котором нет действий более крупных, чем операции, реализуемые в используемом языке напрямую: вычисление арифметического выражения и присваивание значений переменной, обращение к библиотечному (вспомогательному алгоритму), сравнение арифметических выражений(или переменных), ввод(вывод) данных и т.д.
Вторая составляющая структурного программирования – структурное кодирование.
Структурное кодирование- это метод кодирования (программирования), предусматривающий создание понятных, простых и удобочитаемых программных модулей на требуемом языке программирования.
Свойства программных модулей:
1) должен иметь один вход и один выход;
2) должен решать самостоятельно задачу по принципу "один программный модуль - одна функция".
3) работа программного модуля не должна зависеть:
а) от входных данных;
б) от того, какому программному модулю предназначены его выходные данные;
в) от предыстории вызовов программного модуля.
4) программный модуль может вызывать другой модуль;
5) программный модуль должен возвращать управление модулю, который его вызвал;
6) размер программного модуля желательно ограничивать одной-двумя
страницами исходного текста, т.е. не более 100 операторов
7) каждый модуль должен начинаться с комментария, объясняющего
его назначение, назначение переменных, передаваемых в модуль и из
него, модулей, которые его вызывают, и модулей, которые вызываются
из него
8) Идентификаторы всех переменных должны быть смысловыми
9) Родственные группы идентификаторов должны начинаться с одинакового префикса
10) Нужно использовать только стандартные конструкции (выбор, цикл, выход, блок)
11) В одной строке нужно записывать не более одного оператора
12) не допускать вложенности операторов if более 3-х уровней
Третья составляющая. Сквозной контроль- это проверка программного комплекса, выполняемая на основе изучения его группой специалистов. На протяжении всего времени существования программного комплекса может осуществляться несколько проверок, охватывающих все этапы его разработки.
Существенные преимущества стратегии:
1. Возможность начала программирования почти одновременно и параллельно с разработкой соответствующего алгоритма.
2. Легко модифицировать программу по уровням.
3. Упрощается отладка т.к. она ведется также по уровням.
4. Выполнять разработку алгоритма можно несколькими программистами.
Недостатки:
1. Т.к. могут работать одновременно несколько программистов, то может оказаться необходимость в проведении одинаковых вычислений. Разные программисты могут отдельно их программировать.
2. Сложно использовать готовые модули, разработанные ранее.
Примерынисходящей разработки программы для решения вычислительной задачи.
Пример 1.
Задание
Разработать программу для решения следующей задачи:
имеется три действительных числа, представляющих собой длины трех
отрезков.
Определить, можно ли построить из них треугольник и будет ли он
прямоугольным.
Составим СПЕЦИФИКАЦИЮ программы:
1. Название задачи
Треугольник.
Название программы - Tr.
Система программирования - Турбо Паскаль.
Компьютер - IBM PC AT/486 и выше.
2. Описание задачи
Даны три действительных положительных числа a, b и c. Определить:
1. Можно ли построить треугольник из отрезков, длина которых соответственно равна a, b и c
2. Является ли этот треугольник прямоугольным?
3. Математическая модель задачи.
Известно, что условием существования треугольника является выполнение всех неравенств:
b + c > a
c + a > b (1)
a + b > c.
Если все неравенства (1) выполняются, то треугольник будет прямоугольным при выполнении хотя бы одного из равенств
a * a = b * b + c * c
b * b = c * c + a * a (2)
c * c = a * a + b * b.
Так как в (2) имеется нелинейность (возведение в квадрат вещественных чисел), то необходимо ввести следующее допущение: вычисление будем выполнять с некоторой погрешностью. Поэтому (2) преобразуем в следующие неравенства
|a * a - (b * b + c * c)|/(a * a) < e
|b * b - (c * c + a * a)|/(b * b) < e (3)
|c * c - (a * a + b * b)|/(c * c) < e
Здесь e - малая величина, определяющая относительную погрешность вычислений. Гипотенузе прямоугольного треугольника будет соответствовать переменная, стоящая первой в левой части того неравенства, которое выполняется (переменная a, b или c).
4. Управление режимами работы
В общем случае для управления режимами работы программы нужно использовать меню, в котором выбор режима осуществляется вводом номера выбранного режима. Работа с программой завершается через меню (мы опустим).
5. Входные данные
Положительные числа a, b, с и относительная погрешность e. Они должны иметь вещественный тип.
6. Выходные данные
а) На дисплей должна выдаваться справочная информация о назначении программы
б) После обработки входных данных, введенных пользователем, на дисплее должно выводиться одно из следующих сообщений
- "Это не треугольник"
- "Это прямоугольный треугольник с гипотенузой (далее указывается численное значение гипотенузы"
- "Это не прямоугольный треугольник"
7. Ошибки
При вводе чисел a, b, c и относительной погрешности e надо предусмотреть контроль:
- соответствия их типу real
- знака вводимых чисел a, b и c
- диапазона изменения значения относительной погрешности e
(0 < e < 1).
При диагностировании этих ошибок программа должна выдавать соответствующие сообщения, которые могут сопровождаться звуковым сигналом, и предлагать повторить ввод. (Это мы опустим)
Проектируем алгоритм.
НИСХОДЯЩАЯ РАЗРАБОТКА
Подумаем, какие должны быть основные уровни:
- ввод ошибки (Epsilon)
- ввод чисел (Input)
- определение типа треугольника
- вывод результатов (Result)
Структурная диаграмма программного комплекса, соответствующая сокращенному варианту программы, приведена на рис.
рис.
Как следует из структурной диаграммы, управляющий программный модуль (Треугольник) вызывает четыре подчиненных программных модуля.
Теперь подумаем о последовательности выполнения.
(2) Последовательность обработки входных данных этими программными модулями представлена в виде схемы потоков данных
рис.
Описание алгоритма в виде блок-схем.
Блок-схема управляющего программного модуля показана на следующем
Рисунке (3)
рис
Блок-схема управляющего программного модуля соответствует сложному алгоритму, в который входят унифицированные структуры СЛЕДОВАНИЕ, ВЕТВЛЕНИЕ ПОЛНОЕ и ЦИКЛ ДО.
Блок-схемы программных модулей первого уровня показаны на следующих рисунках.
(4) Программный модуль Epsilon соответствует линейному алгоритму и
состоит из унифицированных структур СЛЕДОВАНИЕ
рис
Программный модуль Input соответствует разветвляющемуся алгоритму.
В него входят унифицированные структуры СЛЕДОВАНИЕ и ВЕТВЛЕНИЕ НЕПОЛНОЕ.
рис
Программный модуль Process соответствует разветвляющемуся алгоритму.
В него входят унифицированные структуры СЛЕДОВАНИЕ и ВЕТВЛЕНИЕ НЕПОЛНОЕ
рис.
Программный модуль Result соответсвует разветвляющемуся алгоритму.
Он состоит из унифицированных структур СЛЕДОВАНИЕ и ВЕТВЛЕНИЕ ПОЛНОЕ.
рис.
Теперь можно программировать. Структурное кодирование.
программа
PROGRAM Tr;
USES Crt;
VAR
a, b, c : REAL; {значения отрезков}
Flag : REAL; {вспом. переменная}
Hyp : REAL; {гипотенуза}
e : REAL; {погрешность}
{------------------------
Ввод относительной ошибки
-------------------------}
PROCEDURE Epsilon;
BEGIN
CLRSCR;
WRITE('Введите погрешность...');
READLN (e);
END;
{-------------------------
Ввод отрезков и их проверка
--------------------------}
PROCEDURE Input;
BEGIN
WRITELN;
WRITELN('Введите значения сторон');
WRITELN;
WRITE ('a = ');
READLN (a);
WRITE ('b = ');
READLN (b);
WRITE ('c = ');
READLN (c);
Flag :=1; {это треугольник}
IF NOT ((b+c)>a) then Flag:=0;{это не треугольник}
IF NOT ((c+a)>b) then Flag:=0;{это не треугольник}
IF NOT ((b+a)>c) then Flag:=0;{это не треугольник}
END;
{-----------------------------
Процедура проверки является ли
треугольник прямоугольным
------------------------------}
PROCEDURE Process;
BEGIN
Hyp:=0; {Если Hyp=0, то это не
прямоугольный треугольник.
Иначе - прямоугольный}
IF (ABS(a * a - (b * b + c * c))) / (a * a) < e
THEN Hyp:=a;
IF (ABS(b * b - (a * a + c * c))) / (b * b) < e
THEN Hyp:=b;
IF (ABS(c * c - (b * b + a * a))) / (c * c) < e
THEN Hyp:=c;
END;
{---------------------
Вывод сообщений
----------------------}
PROCEDURE Result;
BEGIN
WRITELN;
IF Hyp <> 0
THEN WRITE('Это прямоугольный треугольник с '+
'гипотенузой ', Hyp:5:2)
ELSE WRITE ('Это не прямоугольный треугольник');
END;
{-----------------------
Управляющая программа
------------------------}
BEGIN
Epsilon;
Input;
IF Flag = 1 THEN
BEGIN
Process;
Result;
END
ELSE WRITE('Это не треугольник');
GOTOXY(1, 20);
WRITE('Для завершения - пробел');
REPEAT UNTIL KeyPressed;}
END.
16.1.3. Стратегия программирования "снизу-вверх"
«Снизу – вверх» означает, что вначале разрабатываются процедуры низшего уровня, затем они постепенно собираются в единое целое. За основу берутся уже готовые программные модули, из которых строятся другие, более сложные или недостающие в исходном наборе.
Преимущества - стандартизируются работы по программированию, упрощается накопление библиотек программ, облегчается обмен между исполнителями в процессе разработки программ и т.д.
Недостатки - сложность объединения отдельных модулей в единую систему, сложность исправления ошибок.
При разработке системы “снизу-вверх”, от отдельных задач ко всей системе, целостность теряется, возникают проблемы информационной стыковки отдельных компонентов.
В практике программирования обычно используются оба эти метода. причем при разработке новых программ предпочтение отдается методу "сверху - вниз", а при модернизации уже готовых программ – методу "снизу - вверх".
Стратегия "изнутри - наружу".
Заключается в разработке сначала наиболее сложных блоков, затем более простых.
Основные требования - время и память.
Идея: при разбиении программы на модули в первую очередь выявляются однородные части программы, которые затем оформляются определенным образом.
Примеры: 1) в трансляторах значительную долю общего объема составляют однородные модули, реализующие отдельные конструкции входного языка.
2) в текстовых редакторах - процедуры, выполняемые при нажатии функциональных клавиш
3) при моделировании некоторой установки или явления - модули, учитывающие различные физические эффекта.
После выявления однородных модулей, переходят непосредственно к программированию. Оно разбивается на этапы.
стр. 185 Горбунов
Объектно-ориентированное проектирование
Объектно-ориентированный подход состоит из объектно-ориентированного анализа (OOA), объектно-ориентированного проектирования (OOP)и объектно-ориентированного программирования(OOP).
Объектно-ориентированный анализ состоит в объектной декомпозиции предметной области, т.е. ИС представляется не набором функций, а совокупностью объектов, взаимодействующих друг с другом. Объекты обладают поведением, состоянием, свойствами, которые реализуются в виде подпрограмм (функций). Т.о., ООП включает в себя возможности структурного подхода, но объектно-ориентированное проектирование в большей степени реализует модель реального мира и соответствует естественной логике человеческого мышления. Объектно-ориентированное программирование состоит в записи уже созданной объектно-ориентированной модели на алгоритмическом языке.
Моделирование объекта в программе осуществляется с помощь объектных типов (классов). Конкретный объект (переменная) является экземпляром класса. Описание класса включает данные и функции (члены класса), характеризующие свойства, состояние и поведение объектов, и обеспечивает инкапсуляцию (скрытие) информации.
Основные принципы ООП:
- наследование
- полиморфизм
- инкапсуляция
Наследование состоит в процессе создания новых классов (классов-потомков) на основе уже имеющихся классов (предков) с передачей их свойств и методов по наследству. Этот принцип был введен для избежания ненужной работы по написанию одинакового кода.
Полиморфизм заключается в возможности вызова для данного объекта при необходимости одноименных методов классов-предков.
(См. ниже в описании синтаксиса оператор указания диапазона).
Инкапсуляция является важным приемом ООП, организующим защиту информации от ненужных и случайных модификаций, что обеспечивает целостность данных и упрощает отладку программного кода после изменений.
Вручную обычно приходится писать лишь небольшие фрагменты кода, в основном для ускорения и упрощения разработки используются визуальные методы. Однако знание синтаксиса ООП необходимо для правильного обращения к объектам и понимания логики их взаимодействия.
CASE - технологии
Под CASE- технологией понимается совокупность средств автоматизации
разработки информационной системы, включающей в себя методолгию
анализа предметной области, программирования и эксплуатации ИС.
Инструментальные средства CASE- технологий применяются на всех
этапах жизненного цикла системы (от анализа и проектирования до
внедрения и сопроволдения), значительно упрощая решение возникающих
задач.
CАSE- технология позволяет отделить проектирование информацион-
ной системы от собственно программирования и отладки:разработчик
системы занимается проектированием на более высоком уровне, не
отвлекаясь на детали. Это позволяет не допустить ошибок уже на
стадии проектирования и получить более совершенные программные
продукты. Эта технология изменяет все стадии разработки ИС, более
всего отражаясь на этапах анализа и проектирования.
Нередко применение CASE- технологии выходит за рамки проектирования
и разработки ИС. Технология дает возможность оптимизировать модели
организационных и управленческих структур компаний и позволяет
им лучше решать такие задачи, как планирование, финансирование,
обучение. Таким образом, CASE- технология позволяет произвести ради-
кальное преобразование деятельности компании, направленное на оптима-
льную реализацию того или иного проекта или повышение общей эффектив-
ности бизнеса.
Коллективная работа над проектом предполагает обмен информацией,
контроль выполнения задач, отслеживание изменений и версий, плани-
рование, взаимодействие и управление. Фундаментом реализации подоб-
ных функций чаще всего служит общая база данных проекта, которую
обычно называют репозитарием. По существу, репозитарий - это
информационный архив, где хранятся сведения о процессах, данных
и связях объектов в разрабатываемом приложении.
В различных CASE-технологиях репозитарий реализуется по-разному и
может содержать описания и модели данных, а также правила их обра-
ьотки. Репозитарий является важнейшим компонентом набора инструмен-
тальных средств CASE и служит источником информации, необходимой
для автоматизации построения проектируемых систем и генераций при-
ложений. Кроме того, CASE-продукты на базе репозитария позволяют
разработчикам использовать в работе над проектом и другие инстру-
ментальные средства, например, пакеты быстрой разработки программ.
В настоящее время CASE-технологии - одна из наиболее динамично
развивающихся отраслей информатики, объединяющая сотни компаний.
Из имеющихся на рынке CASE-технологий можно выделить:Application
Development Workbench (ADW) фирмы Knowledge Ware, BPwin и ERwin,
CDEZ Tods (Oracle), Clear Case (Alria Software), Composer (Texas
Instrument), Discover Development Information System (Software
Emancipation Technology).
Современные CASE-технологии успешно применяются для создания
автоматизированных ИС различного класса:банки, финансовые корпо-
рации, крупные фирмы. Они обычно имеют достаточно высокую стои-
мость и требуют длительного обучения и кардинальной реорганизации
всего процесса создания АИС. Тем не менее экономический эффект
применения CASE-технологий весьма значителен, и большинство сов-
ременных серьезных программных проектов осуществляется именно с
их помощью.
СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ
В процессе разработки алгоритма могут использоваться различные
способы его описания. Они различаются наглядностью, компактностью,
степенью формализации, ориентацией на машинную реализацию и исполь-
зование другими пользователями.
В практике программирования наибольшее применение получили
следующие формы записи алгоритмов:
- словесная и формульно - словесная;
- блок - схемы, структурограммы и Р-схемы ;
- псевдокоды и решающие таблицы;
- язык операторных схем;
- языки программирования.
Все формы кроме последней являются вспомогательными.
Любая из форм представления алгоритмов должна содержать следую-
щие элементы:
- начало и конец вычислительной схемы;
- объекты(данные), над которыми выполняются действия, и резуль-
таты выполнения алгоритма;
- этапы(шаги) преобразования данных с формализованной записью
их содержания;
- указания о последовательности выполнения этапов и отдельных
шагов алгоритмического процесса.
СЛОВЕСНАЯ ФОРМА используется для алгоритмов, ориентированных на
исполнителя - человека. Здесь содержание последовательных этапов вы-
числений задается в произвольной форме на естественном языке. Команды
алгоритма нумеруют, чтобы иметь возможность на них ссылаться. Испол-
нение алгоритма происходит в порядке возрастания номеров шагов, начиная
с первого.
ФОРМУЛЬНО-СЛОВЕСНЫЙ способ использует помимо словесного описания
еще математические символы и выражения.
Предполагается, что отдельные шаги выполняются в последовательности
их записи, если нет указаний обхода определенных шагов.
Пример классического алгоритма Евклида для нахождения наибольшего
ОД двух положительных (не равных нулю) чисел А и В.
ПРИМЕР. ШАГ 1. Начало вычислительного процесса.
ШАГ 2. Ввод значений А и В.
ШАГ 3. Если А = В, то перейти к ш. 5, иначе к ш. 4.
ШАГ 4. Если А > В, то А = А-В, иначе В=В-А. Перейти к ш.3.
ШАГ 5. Вывод результата: "НОД значений А, В "равно" А.
ШАГ 6. Конец вычислительного процесса.
Недостатком словесного способа записи алгоритма является отсутст-
вие более или менее строгой формализации и наглядности вычислитель-
ного процесса.
ПРЕИМУЩЕСТВО - можно описывать алгоритм с произвольной степенью
детализации.
Формульно-словесный также обеспечивает любую степень детализации,
но он более компактен и нагляден.
БЛОК - СХЕМЫ и СТРУКТУРОГРАММЫ
Блок-схемы представляют алгоритм в наглядной графической форме.
Команды алгоритма помещаются внутрь стандартных блоков, соеди-
ненных стрелками, показывающими очередность выполнения команд алгоритма.
Блок - схемы вы отчасти знаете, мы на них останавливаться
не будем. Только запишем ГОСТ 19.707-90 На экзамене будет вопрос.
Рис
Ссылка на методичку 1936. Стр. 17 - 24 изучить самостоятельно.
Р - схемы описываются в ГОСТе 19.005-85
Структурограммы
Для изображения алгоритмов используются как и в блок-схемах
специальные блоки. Каждый блок имеет форму прямоугольника и может
быть вписан в любой внутренний прямоугольник любого другог блока.
Блоки дополняются элементами словесной записи с помощью предложений
на естественном языке или с использованием математических обозна-
чений. Очень важно то, что исключается операция безусловного пере-
хода goto
1. Блок обработки(вычислений). Каждый символ структурограммы
является блоком обработки и обозначается прямоугольником. Каждый
прямоугольник внутри любого символа представляет собой также блок
обработки.
2. Блок следования. Этот символ объединяет ряд следующих друг за
другом процессов обработки.
3. Блок решения. Применяется для обозначения структуры типа раз-
ветвления. Условие располагается в верхнем треугольнике, варианты
решения - по сторонам треугольника, а процессы обработки обозна-
чаются прямоугольниками слева и справа.
Если в блоке решения отсутствует одна из ветвей, то применяется
сокращенный блок решения.
4. Блок варианта. Этот символ представляет расширение блока решения.
Те варианты выхода из этого блока, которые можно сформулировать точно,
размещаются слева. Остальные объединяются в один, называемый выходом
по несоблюдению условий и расположенный справа. Если нужно перечислить
все возможные случаи, правую часть можно оставить незаполненной или
совсем опустить.
5.Блок цикла с предусловием. Этот символ обозначает циклическую
конструкцию с проверкой условия в начале цикла. Условие окончания
цикла размещается в верхней полосе, сливающейся с левой полосой,
указывающей границу цикла. Данная структура может быть использована
также для обозначения цикла с параметром. При этом вверху указывают
закон изменения параметра цикла.
6. Блок цикла с постусловием. Этот символ аналогичен блоку цикла с
предусловием, но условие располагается внизу.
Сравнить блок-схему и структурограмму алгоритма Евклида
Р- схемы описываются ГОСТом 19.005-85.
ПСЕВДОКОД это частично формализованная запись для наглядного
представления схем алгоритмлв и программ, разрабатываемых в соот-
ветствии с общими принципами структурного программированияю. стр. 18
методички 1936.
Он ориентирован на человека и занимает промежуточное место между
естественным и формальным языками. В псевдокоде не приняты строгие
синтаксические правила для записи команд. Вместе с тем имеются некоторые
конструкци, присущие формальным языкам. Для этого вводятся служебные слова.
Рис.
Решающие таблицы в основном используются для разработки прорграмм
логического типа, в которых требуется проверка многочисленных логи-
ческих условий.
ОПЕРАТОРНАЯ СХЕМА - это аналитическая форма представления алгоритма
с помощью операторов, описывающих содержание некоторых автономных
этапов или детальных шагов вычислительного процесса.
Предполагается, что каждый такой этап реализуется посредством
арифмитического оператора А, выполняющего вычисления, и логического
оператора Р(условие), проверяющего соблюдение определенных условий.
Дополняют еще специальными операторами V - ввод, W - вывод, С - конец
и т.д. В П О
Такая схема является логической схемой программы.
Минимальные правила формализации:
- каждый оператор имеет порядковый номер в виде индекса;
- операторы выполняются в естественном порядке - слева напрво;
- если нет передачи управления оператору справа, то между
ними указывается ;
- при выполнении логического оператора очередным становится
оператор, записанный справа от него, иначе подлежащий выполнению
оператор указывается стрелкой.
Рис.
где V1 - ввод значений А и В. Р3 - проверка условия; А5 и А6 - вычисление
значений А-В и В-А. W - вывод результатов.
Программа на Паскале.
БАЗОВЫЕ (СТАНДАРТНЫЕ) ТИПЫ ДАННЫХ
Данные различаются между собой
1) способом кодирования;
2) набором допустимых компьютерных операций над ними.
Например, над закодированными целыми числами можно выполнять ариф-
метические операции, а с символами это лишено смысла.
При программировании основой для классификации данных служит
набор допустимых операций над данными, а не способ их представ-
ления в памяти.
Все данные, для которых допустим определенный набор компь-
ютерных операций, объединим в один класс и дадим этому классу имя
(название). Такой поименованный класс назовем базовым типом дан-
ных.
Для описания базового типа нужно
1) составить функциональное описание базового типа.Охарактери-
зовать каждую допустимую операцию, т.е. сформулировать правило опре-
деления значения результатат для всех возможных значений участвующих
в ней данных.
2) каждый базовый тип имеет определенную физическую реализа-
цию в компьютере, т.е. способы кодирования и доступы к значениям
данных.
Перечень всех возможных значений данных и характеристики
допустимых для них операций представляют собой функциональное
описание базового типа.
Кроме того каждый базовый тип имеет определенную физическую
реализацию в компьютере , т.е. способы кодирования и доступы к зна-
чениям данных.
Обычно пользователь имеет возможность оперировать с несколькими
базовымим типами данных. С какими именно, определяется не столько
моделью компьютера, сколько применяемыми средствами программиро-
вания.
Какие же типы данных обычно бывают базовыми ? Базовыми данными
являются как правило, переменные, перечисление, интенрвал. А базо-
выми типами: целый,вещественный, булевый, символьный.
Абстрактные типы данных (структуры)
На практике исходные данные, промежуточные и окончательные ре-
зультаты удобнее представлять не в виде базовых типов данных, а с
помощью более сложных структурных единиц.
Под абстрактным типом данных (структурой) понимается поименованная
совокупность данных, которые имеют один и тот же набор допустимых
операций.
Перечень и характеристики всех операций представляют собой функ-
циональное описание структуры.
Описание отдельных составляющих элементов исходной структуры,
представляющих более простые структуры и даже базовые типы, а также
операций с данными исходной структуры через операции над составляющими
простыми элементами называется логическим описанием исходной структу-
ры.
Последний уровень описания структуры данных - физическое представ-
ление, которое дает способы хранения структур в памяти, доступа к ним,
а также выполнения операций.
К абстрактным структурам данных относятся массивы, строки, запись,
файл, структура, смесь(объединение). стр.62
Массивы представляют собой переменные с индексами и служат для
описания структур, состоящих из множества элементов, упорядоченных
в соответствии со значениями индексов. Причем массивы в зависимости
от числа индексов различают одномерные (один индекс), двумерные и т.д.
Массив можно представить как папку с пронумероваванными докумен-
тами (информацией), каждый из которых может быть прочитан или заменен
на другой.
С функциональной точки зрения простейший массив Т - это совокупность
N элементов одинаковой структуры, каждому из которых поставлен в соот-
ветствие порядковый номер 1, 2, ...., N, называемый индексом. Для мас-
сива Т определены следующие операции:
- создание массива Т, имеющего N элементов, значения которых иногда
бывают еще не определены;
- чтение элемента с заданным индексом i = 1, 2,..., N,
результатом котрых является элемент Т(i), имеющий этот индекс, а также
исходный массив Т;
- замена элемента массива с данным индесом i на данный элемент G, в
результате которой получается новый массив, отличающийся от исходного
наличием элемента G на i-м месте (T(i)=G).
Логическое описание массива представлено на рис. 1, а физическое
представление - на рис.2.
Рис. 3.13 и 3.14 стр.67 в Ларионове.
Строка - это последовательность символов. Операции со строками вы-
ражаются через операции с символамит: операция присоединения двух
строк, сравнения, вырезания слева, справа и из строки подстроки и т.д.
Динамические структуры данных
К динамическим структурам данных относятся стек, дек, очередь,
список.
Испытания. Контрольные примеры. Сквозной контроль.
(из файла treugol.doc)
Пример 2. Требуется написать программу, которая по времени начала отсчета и числу прошедших секунд выдаст время остановки секундомера согласно 24-часовому исчислению времени. Например, если секундомер был пущен в 1 час дня (13 часов) и число прошедших секунд равно 3662, то результат будет 14 часов 1 мин. и 2 сек.
Вначале надо понять задачу.
Задача понятна!!! Приступаем.
Разбиваем задачу на крупные шаги:
1. Прочитать время пуска секундомера и число прошедших секунд.
2. Вычислить время остановки секундомера.
3. Изобразить это время на экране.
Теперь надо эти три шага рассмотреть вместе и убедиться, что
они выполняют требуемую обработку. Затем надо рассмотреть каждый шаг по
очереди и по мере необходимости детализировать его.
Первый шаг элементарен и заключается в реализации операций вывода
на экране приглашения и ввода времени пуска и числа прошедших секунд.
Значит этот шаг детализировать не нужно.
А вот, чтобы перевести 2-й шаг на язык программирования нужны дополнительные рассуждения. Этот шаг можно рассматривать отдельно и дополнить деталями его выполнения.
Если поделить нацело число прошедших секунд на 60, то в результате получится число прошедших минут. В остатке окажется число секунд, которое надо добавить ко времени пуска секундомера. Если при сложении число секунд превысит 59, то надо уменьшить его на 60, а число прошедших минут увеличить на единицу. В результате деления нацело числа прошедших минут на 60 получится число прошедших часов. Полученный при этом делении остаток даст число минут, которое надо добавить ко времени
пуска. Если при сложении число минут превысит 59, то надо уменьшить его на 60 и увеличить число прошедших часов на единицу. Наконец, число прошедших часов надо добавить ко времени пуска и скорректировать результат в том случае, если произойдет переход на следующие сутки.
Деление нацело можно проделать с помощью операции DIV, а отыскание остатка - с помощью операции MOD. Обсудив способ реализации указанный на шаге 2 обработки можно написать следующий план этого шага:
1) Вычислить число прошедших минут и секунд. Добавить число прошедших секунд ко времени пуска, корректируя в случае необходимости число прошедших минут и счетчик минут времени остановки секундомера.
2) Вычислить число прошедших часов и минут. Добавить число прошедших минут ко времени пуска, корректируя в случае необходимости число прошедших часов и счетчик минут времени остановки секундомера.
(Отметить в программе)
3) Добавить число прошедших часов ко времени пуска с тем, чтобы получить час остановки секундомера, корректируя его в случае перехода на следующие сутки.
Теперь надо просмотреть эти шаги и убедиться, что если они будут один за другим выполнены, то получится как раз то, что указано на шаге 2.
Требуемые для реализации этих шагов приемы рассмотрены нами настолько подробно, что можно писать программу, не детализируя более процесс разработки. Для составления программы теперь достаточно написать операторы, реализующие шаг 1, за ними - операторы, реализующие шаг 23, за ними - операторы, реализующие шаг 3.
sekunda;
(* Эта программа читает время пуска секундомера и число прошедших
секунд и изображает на экране время остановки секундомера *)
var
Максимальный диапазон секундомера от 0 до 32767
p_t:0..maxint; прошедшее время в секундах
sek,s,min,m:0..118; (59*2)
has,h:0..48;
begin
writeln('Введите время пуска секундомера');
write('Часы = ');
readln(has);
write('Минуты = ');
readln(min);
write('Секунды = ');
program readln(sek);
writeln('Введите прошедшее время в секундах');
readln(p_t);
s:=p_t mod 60; число прошедших минут
m:=p_t div 60;
sek:=sek+s;
m:=m+sek div 60; сложение минут с новым значением
sek:=sek mod 60; получение оставшихся секунд
p_t:=m;
m:=p_t mod 60;
h:=p_t div 60;
min:=min+m;
has:=has+min div 60;
min:=min mod 60;
has:=(has+h) mod 24;
writeln('Время остановки = ','часы',has:3,' мин',min:3,' сек',sek:3)
end.
Мы рассмотрели пример решения вычислительной задачи.
Пример решения задачи не вычислительного характера Карасев В.