Вычисление индекса элемента массива. Удаление элемента из массива. Вставка элемента в массив.

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

"Найти максимальный элемент в массиве" и

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

 

Удаление элемента в массиве.

 

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

 

Алгоритм:

1) Определить местоположение удаляемого элемента

2) Начиная с элемента с номером I+1 осуществлять перезапись последующего элемента в предыдущий.

 

Вставка элемента в массив.

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

 

Алгоритм:

1) Расширить верхнюю границу массива

2) Выполнить перезапись последующих элементов на место предыдущих

3) Вставить требуемый элемент вместо элемента с указанным индексом.

 

Организация работы со строками. Строки как частный случай одномерного массива. Строковые типы в Pascal. Функции работы со строками.

 

Строка – тип данных, предназначенный для хранения и обработки цепочки символов, воспринимаемый программой как единое целое.

 

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

 

Этот тип является структурным и позволяет сохранять и обрабатывать символьную строку, содержащую не больше, чем 255 символов. Каждый символ занимает 1 байт, т.е. под элемент типа String выделяется 256 байт, 255 из которых используются под данные строки, а 0 – определяет фактическую длину строки. Каждый символ в строке имеет индекс, например, первый элемент в строке имеет индекс 1. Таким образом, тип string можно представить как array of Char.

 

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

 

ShortString (ANSI): 1 байт на символ, длина не может быть больше 255 символов.

AnsiString (ANSI): 1 байт на символ. Хранение такой строки осуществляется в динамической памяти. При объявлении переменной AnsiString в статической памяти выделяется 4 байта под хранение участка памяти, в котором расположена используемая строка. Структура: первые 4 байта отводятся под фактическую длину строки, далее следуют символы строки. Максимальное число доступных символов – 2³¹.

WideString (Unicode): 2 байта на символ, располагается в динамической памяти, при объявлении переменной в статической памяти выделяется 4 байта под адрес. Под длину строки отводится 4 байта.

PChar (ANSI): 1 байт на символ, размещается в динамической памяти. Признаком конца является символ с кодом 0 (#0). Для описания адреса выделяется 4 байта.

PWideChar (Unicode): То же, что и PChar, но выделяется 2 байта на символ.

 

Функции работы со строками.

 

Для работы со строками в Pascal используются функции, определенные в модулях System, SysUtils, Strings.

Все функции можно разбить на следующие категории:

- создание и удаление строк

- копирование и объединение строк

- определение длины и позиции в строке

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

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

 

System:

Length(S): длина строки в байтах.

UpCase(C): представление символа C из строчного представления в прописное.

Copy(S, I, Count): копирование указанного в Count числа символов строки S, начиная с номера I.

Pos(SubStr, S): возвращает номер начала подстроки SubStr в строке S.

Insert(S, SubStr, I): вставка в строку S1 подстроки S2, начиная с позиции I.

Delete(S, I, C): удаление из исходной строки фрагмента указанной в C длины, начиная с позиции I.

Concat(S1, S2, …): конкатенация строк (аналог оператора "+").

LowerCase(S): строка S в нижнем регистре.

Str(X, S): преобразование числа X в строку S.

Val(S, V, C): преобразование строки S в число V. При невозможности преобразования в C записывается индекс первого ошибочного символа.

StringOfChar(C, Count): создание строки, состоящей из Count символов

 

SysUtils:

IntToStr(V): превращение числа в строку

StrToInt(S): превращение строки в число

FloatToStrF(V, Format): превращение числа в строку с возможностью форматирования вывода.

 

Строка – частный случай одномерного массива.

S[1]:= 'a'; S[2]:= 'b';

 

Кроме модуля System, для работы со строками используется модуль Strings, позволяющий обрабатывать строки типов PChar и PWideChar.

 

StrNew(S): создание строки S и размещение ее в динамической памяти

StrDelete(S): удаление строки из динамической памяти

StrCopy(D, S): копирование в D строки S; также позволяет копировать в D строку S с ограничением максимальной длины до MaxLen

StrMove(D, S, Count): копирование в D строки S длиной Count символов

StrCat(D, S): присоединение к D строки S

StrLen(S): вычисление длины строки S

StrEnd(S): вычисление указателя на символ конца строки

StrScan(S, C): указатель на первое появление символа C в S

StrPas(S): преобразование строки PChar в тип String, при этом значение S не изменяется.

 

 

Динамическое программирование. Понятие задачи и подзадачи. Идея динамического программирования. Нисходящее и восходящее динамическое программирование.

 

Метод динамического программирования – метод оптимизации, приспособленный к операциям, в ходе которых процесс принятия решения может быть разбит на этапы (шаги):

1) Разбиение задачи на подзадачи меньшего размера;

2) Построение таблицы решений;

3) Решение задачи с помощью построенной таблицы.

 

Динамическое программирование – метод решения задач путем составления последовательности из подзадач таким образом, что:

1) Первый элемент последовательности (возможно, несколько элементов) имеет тривиальное решение;

2) Последний элемент последовательности – исходная задача;

3) Каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами.

 

Для T составляется {T1, T2, T3, …, Ti, …, Tn}, причем T = Tn и Ti = F(Ti-1).

 

Исходные данные называют параметрами задачи.

- Для решения квадратного уравнения ax^2+bx+c=0 определяются 3 параметра: a, b, c.

- Для нахождения среднего арифметического параметрами являются количество чисел и их значения.

 

Аргумент -> количество параметров и значения параметров.

 

Задача – проблемная ситуация с явно заданной целью, которую необходимо достичь.

Подзадача – это задача с меньшим числом параметров, либо с тем же числом параметров, но хотя бы один имеет меньшее значение.

 

Идея ДП: При помощи метода динамического программирования задача может быть решена с использованием решения подзадач с меньшими номерами (оптимизация решения).

 

Рекуррентное соотношение – соотношение, связывающее одни и те же функции, но с различными аргументами.

 

Существуют два подхода ДП.

1) Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Решение подзадач запоминается, а затем комбинируется для решения исходной задачи.

2) Восходящее ДП: подзадачи, которые впоследствии понадобятся для решения исходной задачи, просчитываются заранее и затем используются для построения решения исходной задачи. Решается сначала самая мелкая задача, а потом на ее основе строится решение исходной задачи.

 

Подпрограммы. Понятие процедуры и функции. Определение области действия идентификаторов. Предварительные и внешние описания подпрограмм.

 

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

 

Подпрограмма – именованная, логически законченная группа операторов языка, определяющая некоторую задачу, причём эту группу операторов можно вызвать на выполнение любое количество раз из различных мест программы.

 

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

 

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

 

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

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

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

 

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

 

- Основная программа и подпрограммы могут объединяться в одном файле, при этом любая используемая подпрограмма должна быть объявлена до момента её использования.

 

- Текст подпрограммы может располагаться в отдельном от остальной программы файле, тогда для использования модуль, в котором содержатся подпрограмма требуется объявить в разделе uses, при этом на этапе компиляции происходит связывание вызова подпрограммы в основной программе и её описания в программном модуле.

 

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

 

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

 

function имя (набор параметров): возвращаемое значение;

секции const, type, var, label

Begin

тело подпрограммы

end;

 

Те данные, которые поступают в программу на обработку принято называть фактическими параметрами. Параметры, определенные в заголовке, называют формальными параметрами. Любая подпрограмма имеет описание (определение ее заголовка и тела), объявление и вызов (обращение к подпрограмме с целью её использования).

Определения области действия идентификаторов.

 

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

 

Данные, объявленные внутри подпрограммы, являются локальными данными, доступными только внутри подпрограммы и невидимыми на внешнем уровне. Если внутри A имеется B, то локальные данные A – глобальные для B.

 

В соответствии с правилами Pascal каждый идентификатор должен:

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

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

 

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

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