Ильин А.А., Евсюков В.В., Ильин Р.А. Информатика

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

–

211

–

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

заданным числом повторений и с неизвестным числом повторений. Примером

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

шаге значение z для данного x достигнет заданной величины.

Ввод

x, ε

Конец

sin := x,

z := x, n := 3

Начало

Z := -z

/((n-1)

n),

sin := sin+z, n=n+2

Вывод

sin

⏐z⏐≤ε

Нет

Да

Рис. 4.6. Пример схемы алгоритма простой циклической структуры

Другой способ классификации – на циклические процессы, в которых:

1. При переходе от цикла к циклу меняется значение простой переменной

по определенному закону (как в нашем примере значения n и z);

2. При переходе от цикла к циклу изменение управляющей переменной не

подчиняются какому-либо закону

. Пример – случай табличного задания

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

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

–

212

–

Алгоритмы структуры вложенных повторений

Более сложный случай – когда одновременно изменяются несколько

переменных. Если они взаимосвязаны (как n и z в предыдущем примере), это

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

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

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

носит характер циклического вычислительного

процесса по другой

переменной. Вторая вычислительная структура является вложенной в первую.

Цикл, охватывающий другие, называется внешним. Остальные – внутренними.

Параметры таких циклов изменяются не одновременно.

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

, X

..., X

. Будем сортировать по возрастанию. Схема этого алгоритма,

реализующего два цикла, вложенных один в другой, при этом телом

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

4.7.

Словесное описание алгоритма

Сравниваем X

и X

. Если X

≤ X

, то на нужном нам месте X

стоит меньшее из

двух чисел. Иначе – X

и X

надо переставить местами. После этого сравниваем

с X

, затем с X

, X

, и так далее. После того, как будет проведено сравнение с

последним элементом массива – X

, на первом месте X

будет находиться самое

маленькое значение из всех элементов массива. Заметим, что X

мы сравнивали

с X

, ... , X

–

213

–

Нет

Да

Нет

Да

Нет

Да

Начало

Ввод

n, X

, …, X

i := 1

j := i + 1

< X

Y := X

; X

:= X

;

:= Y;

j := j + 1

j ≤ n

i := i + 1

≤

n - 1

Вывод

отсортирован-

ного массива X

Конец

Рис. 4.7. Пример схемы алгоритма вложенных повторений

На втором шаге мы будем сравнивать значение X

последовательно со

значениями X

, ... , X

. После выполнения этих действий там будет расположен

минимальный из оставшихся элементов массива. Теперь сравним значение X

последовательно со значениями X

, ..., X

. И так далее. Последним шагом будет

сравнение X

n-1

и X

. Массив полностью отсортирован по возрастанию значений.

4.8. РЕАЛИЗАЦИЯ ОСНОВНЫХ АЛГОРИТМИЧЕСКИХ СТРУКТУР НА

ЯЗЫКАХ ПРОГРАММИРОВАНИЯ

Рассмотрим способы записи приведенных на рис. 4.4 – 4.7 примеров на

алгоритмических языках Basic и Pascal. Для того, чтобы приведенные

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

–

214

–

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

(заменим операции ввода вывода комментариями). Комментарии в языке Basic

начинаются с символа апостроф (‘ Комментарий), а в языке Pascal заключаются

в фигурные скобки ({Комментарий }). Обозначения основных операций,

операторов и функций в языках Basic и Pascal приведены в табл. 4.1.

Таблица 4.1.

Обозначения основных операций, операторов и функций в

языках Basic и Pascal

Basic Pascal Комментарии

= := Оператор присваивания

+ + Операция сложения

- - Операция вычитания

* * Операция умножения

/ / Операция деления

sin(x), cos(x) sin(x), cos(x)

Функции возвращают значения sin,

cos от аргумента x

exp(x) exp(x)

Функция возвращает значение

экспоненты от аргумента x

(

)

e .

sqr(x) sqrt(x)

Функция возвращает значение

квадратного корня от аргумента x

x^23 sqr(x) Возведение в квадрат аргумента x

if выражение then

оператор 1

…

оператор n

End If

if выражение then

begin

оператор 1;

…

оператор n;

end;

Если выражение принимает значение

true, то выполняется блок операторов

оператор 1, …, оператор n. В

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

операторов оператор 1, …, оператор

n пропускается. Если вместо блока

операторов используется один

оператор, то в Basic можно опустить

служебное слово End If, а в Pascal –

скобки

begin … end;

While выражение

оператор 1

…

оператор n

Wend

While выражение

do begin

оператор 1;

…

оператор n;

end;

Оператор цикла while. Блок

операторов оператор 1, …, оператор

n выполняется до тех пор, пока

выражение принимает значение true.

For i = N0 to Nk

оператор 1

…

оператор n

For i := N0 to Nk do

begin

оператор 1;

…

Оператор цикла for. Блок операторов

оператор 1, …, оператор n

выполняется до тех пор, пока

переменная цикла i примет значения

–

215

–

Basic Pascal Комментарии

next i оператор n;

end;

от N0 до Nk (N0 <= Nk. N0, Nk –

константы или выражения целого

типа) с шагом 1. Если N0 > Nk, то

блок операторов не выполнится ни

разу.

Запись приведенных на рис. 4.4 – 4.7 схем алгоритмов на

алгоритмических языках Basic и Pascal приведены в табл. 4.2 – 4.5.

Таблица 4.2.

Пример программирования алгоритма линейной структуры (см. рис. 4.4)

Basic Pascal

…

… Var a, b, x, Y, Z, C: double;

Begin

‘ Ввод a, b, x { Ввод a, b, x}

Y = a*cos(x) Y := a*cos(x);

Z = b*exp(x) Z := b*exp(x);

C = cos(x)^2 - x^2 C := cos(x)* cos(x) - x*x;

C = sqr(C) C := sqrt(C);

D = (Y - Z)/C D := (Y - Z)/C;

‘Вывод D {Вывод D}

END End.

Таблица 4.3.

Пример программирования алгоритма разветвленной структуры (см. рис. 4.5)

Basic Pascal

…

… Var a, b, c, D, x1, x2: double;

Begin

‘ Ввод a, b, c { Ввод a, b, c}

D = b^2 - 4*a*c D := b*b - 4*a*c;

If D <= 0 then If D <= 0 then begin

x1 = (-b – sqr(D)/(2*a) x1 = (-b - sqrt(D)/(2*a);

x2 = (-b + sqr(D)/(2*a) x2 = (-b + sqrt(D)/(2*a);

End If End;

‘Вывод x1, x2 {Вывод x1, x2}

END End.

–

216

–

Таблица 4.4.

Пример программирования алгоритма простой циклической

структуры (см. рис. 4.6)

Basic Pascal

…

Var n: integer;

… X, e, Z, _sin: double;

Begin

‘ Ввод x, e { Ввод x, e}

_sin = x _sin := x;

Z = x Z := x;

N = 3 n := 3;

While abs(z) <= e While abs(Z) <= e do begin

Z = -Z*x^2/((n - 1)*n) Z := -Z*Sqr(x)/((n - 1)*n);

_sin = _sin + Z _sin := _sin + Z;

n = n + 2 n := n + 2;

Wend End;

‘Вывод x, _sin {Вывод x, _sin}

END End.

Таблица 4.5.

Пример программирования алгоритма вложенных повторений (см. рис. 4.7)

Basic Pascal

…

Var i, j: integer;

… Y: double;

X: Array[1…100] of double;

Begin

‘ Ввод n { Ввод n (n <= 100)}

… …

Dim X(n)

‘ Ввод элементов массива X { Ввод элементов массива X}

For i = 1 to n – 1 For i = 1 to n - 1 do

For j = i + 1 to n For j = i + 1 to n do

If X(j) < X(i) then If X(j) < X[i] then begin

Y = X(j) Y = X[j];

X(j) = X(i) X(j) = X[i];

X(i) = Y X(i) = Y;

End If End;

Next j {Вывод элементов массива X}

Next i End.

‘Вывод элементов массива X

–

217

–

Basic Pascal

END

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

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Перечислите этапы подготовки задачи к решению на ЭВМ.

2. Что понимают под алгоритмом?

3. В чем сущность алгоритмизации вычислительного процесса?

4. Какие способы записи алгоритма Вам известны?

5. Приведите основные символы, используемые для построения схем

алгоритмов.

6. Каким образом можно проверить правильность построения

алгоритма?

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

на

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

обеспечения.

8. Укажите функциональные отличия встроенных отладчиков в

интегрированных средах разработки программного обеспечения QBasic

(операционная система MS DOS) и Visual Basic (операционная система MS

Windows) Micrsoft Corporation.

9. Что понимают под алгоритмами линейной структуры?

10. В чем суть алгоритмов разветвленной структуры?

11. В каких случаях используют алгоритмы циклической структуры?

12.

Дайте определение технологии алгоритмизации.

13. В чем суть нисходящего проектирования программного обеспечения?

14. Перечислите основные принципы нисходящего проектирования

программного обеспечения.

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

перехода (GOTO) при нисходящем проектировании программного обеспечения.

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

17. Как реализовать на каком-либо языке программирования высокого

уровня алгоритм

линейной структуры? Приведите конкретный пример.

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

алгоритм разветвленной структуры? Приведите конкретный пример.

19. Как реализовать на каком-либо языке программирования высокого

уровня алгоритм циклической структуры? Приведите конкретный пример.

20. Разработайте на каком-либо языке программирования высокого

алгоритм вложенных повторений? Приведите конкретный пример.

–

218

–

5. ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО

УРОВНЯ. БАЗЫ ДАННЫХ

5.1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

При использовании компьютера для решения любой задачи необходимо

выполнить три этапа действий:

• ясно и точно установить, что конкретно должно быть сделано;

• разработать алгоритм решения задачи, обеспечивающий получение

желаемого результата;

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

на компьютере.

При обработке экономической информации первые два этапа

относятся к

системному анализу, третий этап называют программированием.

Язык программирования – это средство связи между программистом и

компьютером. Язык программирования – нечто большее, чем просто средство

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

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

может выразить свои соображения

по поводу решения задачи.

Языки программирования – это не просто инструментальное средство;

это тот “материал”, из которого создается программное обеспечение, то, что мы

видим на экранах дисплеев при работе с компьютером. Язык

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

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

Язык программирования – набор правил, определяющих, какие

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

данных описывает программа.

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

целесообразно сгруппировать по трем уровням абстракции. Первому уровню

абстракции можно поставить в соответствие языки Fortran, C, Pascal и др. (язык

ассемблер условно не включен). Представителями второго, более высокого

уровня абстракции, являются языки C

, Ada и др. На самом высоком уровне

абстракции находятся языки функционального и логического

программирования: Lisp, Prolog и др.

С момента своего появления в начале 50-х годов до настоящего времени

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

рисунке 5.1 представлена обобщенная классификация языков

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

широко известных языков.

–

219

–

В процессе развития в языках программирования сменилось несколько

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

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

времени.

Операторные

Fort

Процедурные

Функциональные

Prolog

Машинно-независимые

(высокого уровня)

Машинно-зависимые

(низкого уровня)

Процедурно-ориентированные

(универсальные)

Объектно-

ориентированные

GPSS

LISP

Basic

Pascal

Fortran

Cobol

Ada

Visual Basic

C++

ObjectPascal

Perl

Java

Ada 93/95

Языки

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

Непроцедурные

Проблемно-

ориентированны

Рис.5.1. Обобщенная классификация языков

Первые программы писались непосредственно в виде последовательности

машинных команд конкретного процессора. Значительное облегчение при

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

Ассемблер, в котором реализовано

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

макроассемблер

MASM, ускоривший процесс создания программ,

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

–

220

–

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

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

FASM.

Начальная концепция предполагала прямое решение задачи, когда всё

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

этом не учитывалась возможность последующего использования созданного

программного кода для решения схожих задач, его последующей модификации.

Подобный подход позволял написать работоспособную программу,

содержащую до нескольких сотен строк. Увеличение количества строк (при

решении более

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

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

затрудняло процесс её отладки. Такой подход, в частности, был характерен для

ранних версий языка Basic.

Новая концепция базировалась на

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

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

внутреннюю организацию (реализацию) функций не накладывалось никаких

ограничений. В принципе каждую из функций можно рассматривать как

отдельный оператор. Данный подход позволяет абстрагироваться от реальной

сложности любой из функций. Он был реализован в 60-х годах при создании

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

Fortran и

Cobol.

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

связана со

структурным программированием (функционально-модульным

программированием). Оно вводит в практику программирования ряд новых

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

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

от других подсистем. Структурное программирование – это стиль

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

операторов, которые обеспечивают хорошо структурированные программы,

легкие для чтения и понимания.

Концепция структурного программирования явилась ответом на

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

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

информационные системы для сферы экономики. В основе структурного

подхода используется принцип функциональной декомпозиции (разделения),

при которой структура системы описывается в терминах иерархии ее функций

и передачи данных между отдельными функциональными

элементами. В

процессе декомпозиции система разбивается на функциональные подсистемы,

которые, в свою очередь, делятся на подфункции, те - на задачи и так далее до

конкретных процедур. При этом обеспечивается целостное представление

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

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