РАЗДЕЛ 2. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ВЫСОКОГО УРОВНЯ

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

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

Структуированные типы данных и их обработка. Строковые типы. Процедуры и функции обработки строковых данных.

Подпрограммы. Формальные и фактические параметры. Процедуры. Функции. Программирование рекурсивных алгоритмов.

Модуль языка Турбо Паскаль. Структура модуля. Стандартные модули.

Файлы. Типы файлов. Процедуры и функции для работы с файлами.

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

Принципы объектно-ориентированного программирования. Статистические и виртуальные методы. Динамические объекты.

Жизненный цикл программного обеспечения. Интегрированная среда обработки Delphi. Разработка приложения в Delphi. Структура проекта в Delphi. Управление проектами.

Язык Object Pascal. Классы. Типы данных. Базовые классы VCL. Программы, управляемые событиями. Форма. Управления компонентами форм. Шаблоны форм.

Библиотека визуальных компонентов. Списки и коллекции. Графический интерфейс.

Этапы решения задач на ЭВМ.

1. Этапы решения задачи на ЭВМ

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

1. Постановка задачи:

• сбор информации о задаче;

• формулировка условия задачи;

• определение конечных целей решения задачи;

• определение формы выдачи результатов;

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

2. Анализ и исследование задачи, модели:

• анализ существующих аналогов;

• анализ технических и программных средств;

• разработка математической модели;

• разработка структур данных.

3. Разработка алгоритма:

• выбор метода проектирования алгоритма;

• выбор формы записи алгоритма (блок-схемы, псевдокод и др.);

• выбор тестов и метода тестирования;

• проектирование алгоритма.

4. Программирование:

• выбор языка программирования;

• уточнение способов организации данных;

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

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

5. Тестирование и отладка:

• синтаксическая отладка;

• отладка семантики и логической структуры;

• тестовые расчеты и анализ результатов тестирования;

• совершенствование программы.

6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5.

7. Сопровождение программы:

• доработка программы для решения конкретных задач;

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

Алгоритм.
Алгори́тм, от имени учёного аль-Хорезми (перс. خوارزمی‎ [al-Khwārazmī]) — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкции, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).

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

Свойства алгоритмов.
Формальные свойства алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
Массовость — универсальность. Алгоритм должен быть применим к разным наборам исходных данных.
Результативность — завершение алгоритма определёнными результатами.
Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

Основные структуры алгоритмов.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
1. Базовая структура следование. Образуется из последовательности действий, следующих одно за другим:

2. Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Структура ветвление существует в четырех основных вариантах:
если-то;
если-то-иначе;
выбор;
выбор-иначе.
1) если-то
если условие
то действия
конец если

2) если-то-иначе
если условие
то действия 1
иначе действия 2
конец если

3) выбор
выбор
при условие 1: действия 1
при условие 2: действия 2
. . . . . . . . . . . .
при условие N: действия N
конец выбора

4) выбор-иначе
выбор
при условие 1: действия 1
при условие 2: действия 2
. . . . . . . . . . . .
при условие N: действия N
иначе действия N+1
конец выбора

Пример. Составить блок-схему алгоритма вычисления функции

Базовая структура цикл. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Структура цикл существует в трех основных вариантах:
Цикл типа для.
Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
Цикл типа пока.
Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
Цикл типа делать - пока.
Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. Условие проверяется после выполнения тела цикла.
Заметим, что циклы для и пока называют также циклами с предпроверкой условия а циклы делать - пока - циклами с постпроверкой условия. Иными словами, тела циклов для и пока могут не выполниться ни разу, если условие окончания цикла изначально не верно. Тело цикла делать - пока выполнится как минимум один раз, даже если условие окончания цикла изначально не верно.
цикл для i от i1 до i2 шаг i3
тело цикла (последовательность действий)
конец цикла

цикл пока условие
тело цикла (последовательность действий)
конец цикла

цикл делать
тело цикла (последовательность действий)
пока условие
конец цикла

Пример. Составить блок-схему алгоритма вычисления функции
yk = sin (kx) + cos (k/x), k = 1, 2, ..., 50
Пример. Составить блок-схему вычисления функции
y = a3 / (a2 + x2)
при x, изменяющимся от x = 0 до x = 3 с шагом Dx = 0,1
Итерационные циклы. Особенностью итерационного цикла является то, что число повторений операторов тела цикла заранее неизвестно. Для его организации используется цикл типа пока. Выход из итерационного цикла осуществляется в случае выполнения заданного условия.
На каждом шаге вычислений происходит последовательное приближение и проверка условия достижения искомого результата.

Пример. Составить алгоритм вычисления суммы ряда

с заданной точностью (для данного знакочередующегося степенного ряда требуемая точность будет достигнута, когда очередное слагаемое станет по абсолютной величине меньше).
Вычисление сумм - типичная циклическая задача. Особенностью же нашей конкретной задачи является то, что число слагаемых (а, следовательно, и число повторений тела цикла) заранее неизвестно. Поэтому выполнение цикла должно завершиться в момент достижения требуемой точности.
При составлении алгоритма нужно учесть, что знаки слагаемых чередуются и степень числа х в числителях слагаемых возрастает.
Решая эту задачу "в лоб" путем вычисления на каждом i-ом шаге частичной суммы
S:=S+(-1)**(i-1)*x**i/i ,
мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой р, то у следующего слагаемого числитель будет равен -р*х (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое m

будет равно p/i, где i - номер слагаемого.
Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма - результативность.
Вложенные циклы.
Возможны случаи, когда внутри тела цикла необходимо повторять некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая структура получила название цикла в цикле или вложенных циклов. Глубина вложения циклов (то есть количество вложенных друг в друга циклов) может быть различной.
При использовании такой структуры для экономии машинного времени необходимо выносить из внутреннего цикла во внешний все операторы, которые не зависят от параметра внутреннего цикла.
Пример вложенных циклов для. Вычислить сумму элементов заданной матрицы А(5,3).

Пример вложенных циклов пока. Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.

Структурный подход к разработке ал-горитмов.
Указанный структурный подход к разработке алгоритмов позволяет осуществить перевод записи алгоритма с языка блок-схем на язык процедурного программирова-ния без внесения изменений в конструкцию алгоритмических предписаний.
В ходе поиска решения задачи учащиеся не всегда получают блок-схему в структурном ви-де. Поэтому учителю необходимо овладеть приемами приведения алгоритмического предписания к структурной записи. Такими специальными приемами являются инвертирование условия со-ставной команды, дублирование блока, соединение условий составных команд и введение допол-нительной переменной – признака [3, стр.113-122].
Рассмотрим несколько примеров иллюстрирующих указанный подход.
Пример 1. Две блок-схемы одного и того же фрагмента алгоритма приведены на рис. 2. В схеме слева довольно трудно выделить базовые структуры алгоритма, найти точки входа и выхода в составных командах, определить имеется ли вложенность одной базовой конструкции в другую или же соединение идет последовательно. Инвертировав условие команды повторения, соединив стрелки до выхода из команды ветвления и представив запись в соответствии с шаблонами ко-манд, получаем структурную запись алгоритма.

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

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

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

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

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

Для каждого понятия языка должна существовать единственная метаформула, в левой части которой указывается определяемое понятие, т.е. метапеременная языка БНФ, а правая часть формулы тем или иным способом задает все множество значений этой метапеременной, т.е. все допустимые конструкции, которые объединяются в это понятие. Все метапеременные заключаются в специальные угловые скобки < и >, которые не принадлежат алфавиту определяемого языка, т.е. являются метасимволами, например, <выражение>, <число> и т.д. Основные же символы языка указываются непосредственно. Левая и правая части метаформулы разделяются специальным знаком : : =, смысл которого можно интерпретировать как «по определению есть». Обычно в качестве значений метапеременной может приниматься любая из нескольких допустимых конструкций. Все допустимые конструкции указываются в правой части формулы и разделяются метасимволом "|", смысл которого можно передать словом «или» («либо»). Кроме перечисления всех возможных значений метапеременной в правой части метаформулы может быть указано правило построения значений.

Структура программы на языке Турбо Пас-каль.
Написанная по правилам стандарта языка Паскаль программа будет иметь в своем полном варианте структуру показанную ниже:

PROGRAM Имя_Программы;
USES
Список используемых библиотек (модулей);
LABEL
Список меток в основном блоке программы;
CONST
Определение констант;
TYPE
Описание типов;
VAR
Определение глобальных переменных программы;

ОПИСАНИЕ ПРОЦЕДУР;

ОПИСАНИЕ ФУНКЦИЙ;

BEGIN
Основной блок программы (операторы)
END.

Таким образом, программа содержит два раздела: (I) раздел описаний (блоки USES, LABEL, CONST, TYPE, VAR, а также описание процедур и функций) и (II) исполняемую часть (основной блок). Раздел описаний, в принципе, не является обязательным и может вовсе отсутствовать. Заголовок программы, начинающийся с ключевого слова PROGRAM, выполняет исключительно декоративную функцию, и поэтому также может отсутствовать.

Классификация типов данных.
I. Простые типы: порядковые, вещественные, дата-время.

Порядковый тип в свою очередь делится на:

1. целые типы;

2. логический тип или булевский тип;

3. символьный тип;

4. перечисляемые типы;

5. ограниченные типы или тип-диапазон.

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

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

II. Составные типы: структурированные типы, указатели, строки, процедурные, объекты, классы, варианты.

Структурированные типы в свою очередь делятся на:

1. регулярные типы (массивы);

2. комбинированные типы (записи);

3. множественные типы;

4. файловые типы;

Простые типы данных.

1. Целые типы

Эта группа типов обозначает множество целых чисел в различных диапазонах. Имеется пять целых типов, различающихся допустимым диапазоном значений и размером занимаемой памяти. Целые типы обозначаются идентификаторами Integer, Byte, ShortInt, Word, LongInt; их характеристики приведены в таблице 1.

Таблица 1

Тип
Диапазон значений
Размер памяти

ShortInt
-128..127
1 байт

Integer
-32768..32767
2 байта

LongInt
-2147483648..2147483647
4 байта

Byte
0..255
1 байт

Word
0..65535
2 байта

Значения целых типов могут изображаться в программе двумя способами: в десятичном виде и в шестнадцатеричном коде. В последнем случае в начале такого кода ставится символ `$'.

Примеры:

123

-1

$F1 (десятичное представление 241)

0$B80

2. Булевский (логический) тип

К логическим относятся типы Boolean, ByteBool, Bool, wordBool и LongBool. В стандартном Паскале определен только тип Boolean, остальные логические типы введены в Object Pascal для совместимости с Windows: типы Boolean и ByteBool занимают по одному байту каждый, Bool и WordBool - по 2 байта, LongBool - 4 байта.

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

true (истина)

false (ложь).

3. Символьный тип

Значениями символьного типа являются символы из множества ASCII (American Standard Code for Information Interchange - американский стандартный код для обмена информацией). Это множество состоит из 256 различных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и различных других символов, включая специальные управляющие символы. Допускаются некоторые отклонения от стандарта ASCII, в частности, при наличии соответствующей системной поддержки это множество может содержать буквы русского алфавита.

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

`*' `a' `X' `:' `'''

Для представления самого апострофа его изображение удваивается.

Если символ, который нужно изобразить, не имеет графического представления, то можно воспользоваться следующей эквивалентной формой записи, состоящей из символа `#' (решетка, диез) и целочисленного кода символа (от 0 до 255):

#10 #$A

4. Перечислимые типы

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

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

Например: Пусть необходимо разработать программу управления уличным светофором. Ясно, что программа будет моделировать светофор с помощью указания его текущего состояния, т.е. включенного в данный момент света. Таким образом, переменная программы, представляющая светофор, может принимать одно из трех значений, соответствующих красному, желтому и зеленому цветам. Можно было бы ввести для этого переменную целого типа и установить, что, например, значения 1, 2, 3 соответствуют указанным цветам. Однако очевидно, что числа, кодирующие цвета, не имеют прямого отношения к решаемой задаче и, следовательно, усложняют программу и затемняют ее смысл. Поэтому наиболее естественным решением в данном случае будет введение перечислимого типа из трех значений, обозначаемых именами Red, Yellow, Green, и переменной этого типа.

Синтаксис определения перечислимого типа:

(идентификатор 1, идентификатор 2,...,идентификатор N)

Примеры перечислимых типов:

(Red, Yellow, Green)

(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday)

(On, Off)

(Left, Up, Right, Down)

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

Monday..Friday

Left..Up

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

5. Ограниченные типы (тип-диапазон)

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

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