Оптимизация (если возможно).
2.3 Требования к учебному тексту
Текст должен быть доступен для понимания студентами, имеющими начальные навыки программирования и базовые знания алгебры.
Разделить текст на этапы, соответствующие этапам общего алгоритма перехода от индексов к указателям. Этапы, требующие более детального рассмотрения можно разделить на несколько пунктов.
Каждый этап должен:
начинаться с короткого тезиса, отражающего назначение соответствующего этапа;
содержать подробные инструкции, иллюстрирующие этап алгоритма перехода применительно к заявленной задаче;
приводить программу к виду, позволяющему легко проверить правильность выполнения инструкций.
В приложении к дипломной работе должны содержаться промежуточные версии программы соответствующие этапам алгоритма.
2.4 Требования к веб-странице
Сформировать веб-страницу на основе имеющегося методического материала, в соответствии с CSS-стилями раздела «Этюды по алгоритмизации» и общей стилистикой сайта [1], организовать соответствующую функциональность, обеспечить аддитивность по отношению к другим разделам сайта.
Исходные данные задачи тесно связаны с уже имеющимися материалами сайта, необходимо связать их гиперссылками. Организовать возможность скачивания промежуточных версий программы.
Предполагается для редактирования html-кода использовать обычный текстовый редактор. Для создания скриншотов кода на языке Pascal, формул и других изображений использовать бесплатные версии программ Free Pascal 2.6.0, Gimp 2.8.0, OpenOffice 3.4.0.
2.5 Решение поставленной задачи
Этап 1. Для начала нужно реализовать алгоритм без использования указателей. Надо вспомнить работу с индексами, рекурсией и написать функцию, вычисляющую определитель матрицы разложением по строке, отладить её.
Этот этап уже был подробно описан на сайте В.З. Цалюка [1]. На прилагающемся диске имеется полный текст функции (см. Приложение 1, файл DET0.PAS). Кратко опишем важные моменты.
В программе объявлена одна константа и два пользовательских типа данных:
CONST NN = 3;= ARRAY[1..NN,1..NN] OF LongInt;= ARRAY[1..NN] OF BOOLEAN;
Константа NN используется для определения двух типов массивов:
) Matrix - двумерный массив размерности [1..NN, 1..NN] чисел типа LongInt, который мы будем использовать для хранения элементов матрицы;
) Index - одномерный массив размерности [1..NN], состоящий из элементов логического типа Bool;
Массивы row и cols типа Index будут использоваться для того, чтобы указать, на персечении каких строк и столбцов матрицы расположены элементы вычисляемого минора. Равенство rows[i] = TRUE будет означать, что строка матрицы A с номером i участвует в определении минора, и аналогично в массиве cols будем указывать входящие в минор столбцы матрицы.
Объявим основную функцию:
det(VAR A: Matrix): LongInt;
Функция вычисляет значение определителя матрицы A
Входной параметр:: Matrix - массив элементов матрицы, передаваемый по ссылке;
Выходной параметр:
Функция возвращает определитель квадратной матрицы, расположенной в массиве A.
FUNCTION det(VAR A: Matrix): LongInt;: WORD;i := 1 TO NN DO[i] := TRUE; [i] := TRUE; ; := minor(A, rows, cols, NN);;
Замечание: функция det для своей работы использует два глобальных вспомогательных массива:
row, cols: Index
и две вспомогательные функции:
1) minor(VAR A: Matrix; VAR rows, cols: Index; n: WORD): LongInt;
) FindTrue(VAR mas: Index): WORD;
причем minor вызывается рекурсивно.
FUNCTION minor(VAR A: Matrix;rows, cols: Index; n: WORD): LongInt;, j: WORD; , sum: LongInt;: INTEGER;:= FindTrue(rows);n = 1 THEN:= FindTrue(cols);:= A[i,j];[i] := FALSE; (n); := 0; := 1; j := 1 TO NN DOcols[j] THEN[j] := FALSE;:= A[i, j]; aa <> 0 THEN := sum + jo * aa * minor(A, rows, cols, n);[j] := TRUE;:= -jo; ;:= sum;[i] := TRUE; ;
END;
В свою очередь minor использует функцию FindTrue для исследования массивов row, cols:
FUNCTION FindTrue(VAR mas:Index):WORD;i: WORD;i := 1 TO NN DOmas[i] THEN:= i;;
END;
FindTrue := 0;
END;
Рассмотрим теперь главную процедуру, где демонстрируется вызов функции Det:
BEGIN(f, 'num.txt');(f);i := 1 TO NN DOj := 1 TO NN DO(f, A[i,j]);(f);:= det(A);(d:5);
Здесь элементы матрицы считываются из текстового файла.
Итак, у нас есть правильно работающая программа, которая может вычислять определитель матрицы наперед (до компиляции) заданного размера. Следующие этапы будут направлены на то, чтобы позволить ей работать с матрицами произвольного размера.
Этап 2.
Размерности вносятся в список аргументов функций.
det(VAR A: Matrix; k: WORD): Real;(VAR mas: Index; k: WORD): WORD;(VAR A: Matrix; k: WORD; VAR rows, cols: Index; n: WORD): LongInt;
Так же нужно не забыть в теле каждой функции сменить константу NN на передаваемое значение k.
Так как мы получаем элементы матрицы путем считывания из файла, то удобно и ее размер получать таким же способом. Это значение мы и будем передавать функции det как второй параметр, при ее вызове в теле главной процедуры.
d := det(@A, m);
Теперь наша программа может работать с массивами любой размерности не более NN. Полный текст измененной программы в приложении (файл DETPT01.PAS).
Этап 3.
Все массивы, входящие в список аргументов функции, заменить указателями, указывающими на переменную того же типа, что и элементы массива.
det(pA: LongIntPtr; k: WORD): Real;(mas: BoolPtr; k: WORD): WORD;(A: LongIntPtr; k: WORD; pRow, pCol: BoolPtr; n: WORD): LongInt;
Ключевое слово VAR перед аргументами-указателями в объявлении каждой функции следует убрать, ведь мы и так передаем ссылку. Если же оставить VAR перед указателем, то функция не станет создавать его копию в оперативной памяти, а будет работать с ним непосредственно, следовательно, будет иметь возможность изменить значение указателя.
Очевидно, что предварительно необходимо объявить соответствующие типы данных:
TYPE= ^LongInt;= ^BOOLEAN;
Удаляем из глобальных переменных более не нужные здесь массивы rows и cols.
Сейчас функция не работает, т.к. после смены типов переменных поменялись и правила их использования. Рассмотрим один из способов решения этой проблемы.
Этап 4.
Преобразования внутри тела функции.
Нужно заменить каждое индексное выражение указателями и организовать их перемещение между элементами предполагаемых массивов.
FUNCTION FindTrue(mas: BoolPtr; k: WORD): WORD;i: WORD;i := 1 TO k DOmas^ THEN:= i;;(mas); := 0;
END;
Идентификатор переменной-указателя хранит адрес текущего элемента массива, а оператор "^" позволяет обратиться к значению, расположенному по этому адресу. Таким образом, конструкция mas^ фактически является текущим элементом. Перемещать указатель по массиву можно с помощью операций инкрементирования Inc и декрементирования Dec, например Inc(mas) переместит указатель mas на следующий элемент, а Inc(mas, i-1) переместит на элемент с номером i (если mas перед этим указывал на начало массива, т.е. на первый элемент). На самом деле инкрементация (декрементация) просто увеличивает (уменьшает) адрес указателя на число байт, равное количеству байт, необходимому для хранения переменной типа, соответсвующего типу данного указателя. Поэтому важно следить, чтобы все элементы массива располагались последовательно в памяти компьютера. Элементы двумерных массивов тоже располагаются в памяти последовательно, а именно по строкам. Поэтому если нужно переместить указатель по столбцу, то перемещать нужно ровно на длину строки столько раз, на сколько элементов надо переместиться по столбцу. Таким образом Inc(A, k*(i-1)) переместит указатель на начало строки с номером i.
С помощью оператора "@" можно получить адрес любой переменной. Этим можно воспользоваться при вызове функции Det(@A, m), так как глобальная переменная A все еще имеет тип Matrix.
Полезно сохранять адрес начала массива в одной переменной, а изменять другую. Например, в функции minor это необходимо, чтобы передать адреса массивов новому рекурсивному вызову minor:
FUNCTION minor(pA: LongIntPtr; k: WORD;, pCol: BoolPtr; n: WORD): LongInt;, j: WORD; : LongInt;: INTEGER;: LongIntPtr; , cols: BoolPtr;:= pA; := pRow;:= pCol;:= FindTrue(pRow, k);(A, k*(i-1));(rows, i-1);n = 1 THEN:= FindTrue(pCol, k);(A, j-1);(cols, j-1);:= A^;^ := FALSE; (n); := 0; := 1; j := 1 TO k DOcols^ THEN^ := FALSE;A^ <> 0 THEN := sum + jo * A^ * minor(pA, k, pRow, pCol, n);^ := TRUE; := -jo; ;(A);(cols);;:= sum;^ := TRUE; ;
END;
Внутри функции Det указатель A не изменяется, поэтому его копировать не нужно. А вот для бывших глобальных массивов rows и cols в разделе VAR функции необходимо выделить по 2 указателя, так как эти новые массивы теперь будут появляться во время вызова функции Det и исчезать после завершения ее работы.
FUNCTION det(A: LongIntPtr; k: WORD): LongInt;: WORD;, pRow, rows, cols: BoolPtr;:= rows; := cols;i:= 1 TO k DO^ := TRUE; ^ := TRUE; (pRow); (pCol); ;:= minor(A, k, rows, cols, k);;
Теперь наша программа может вести себя непредсказуемо, так как мы никаким образом не инициализировали массивы, на которые указывают rows и cols.
Этап 5.
Динамическое выделение памяти для вспомогательных массивов.
Предполагается, что наша функция det для своих нужд должна использовать вспомогательные массивы (row, cols), но теперь компилятору не известно, сколько необходимо выделить памяти для работы функции. В этом случае нужно выделять память динамически.
С помощью GetMem(p, n * s) можно выделить участок памяти необходимый для массива, состоящего из n элементов, каждый из которых занимает s байт, и получить адрес начала этого участка в указатель p. Выделенный таким способом участок памяти будет защищен, как минимум, от попыток использовать его повторно, но нужно помнить, что указатели могут перемещаться как по выделенной памяти, так и по свободной, поэтому ничто не спасет "защищенный" участок от ошибок программиста в работе с указателями.
Количество байт нужное для определенной переменной можно узнать с помощью функции sizeOf. Она может принимать как конкретную переменную, так и название типа. Например sizeOf(BOOLEAN) вернет единицу, так как размер переменной типа BOOLEAN равен одному байту.(p, n * s) позволяет освободить выделенную память. Все параметры должны совпадать по значениям с теми, которые использовались при выделении памяти.
FUNCTION det(A: LongIntPtr; k: WORD): LongInt;: WORD;, pRow, rows, cols: BoolPtr;(rows, k{*sizeof(rows^)}); (cols, k{*sizeof(cols^)}); := rows; := cols;i:= 1 TO k DO^ := TRUE; ^ := TRUE; (pRow); (pCol); ;:= minor(A, k, rows, cols, k);(rows, k{*sizeof(rows^)}); (cols, k{*sizeof(cols^)}); ;
Теперь в главной процедуре не стоит использовать матрицу типа Matrix, потому что элементы матрицы, передаваемой функции Det, должны последовательно располагаться в памяти, а для массивов данного типа это выполнено только для матриц размера NN x NN. Но теперь мы сами можем создать массив любого нужного нам размера:
BEGIN(f, 'num0.txt');(f);(f, m);(pA, m*m*4{sizeof(pA^)});:= pA;i := 1 TO m DOj := 1 TO m DO(f, A^);(A);;(f);:= det(pA, m);(pA, m*m*4{sizeof(pA^)});(d:5);
END.
Функция полностью готова. В приложении можно найти итоговый листинг программы (см. Приложение 1, файл DETPT03.PAS).
Тесты.
Программа успешно прошла следующий набор тестов:
1)
)
)
)
)
)
Заключение
Проделана методическая работа на тему программирования с использованием технологий адресации (указателей). Написана итоговая программа, демонстрирующая работу модифицированной функции, составлена система тестов, для нее.
На основе проделанной работы составлен учебно-методический текст, подробно описывающий алгоритм перехода от массивов к указателям, на нетривиальном примере. В частности, рекурсивный алгоритм вычисления определителя матрицы разложением по элементам строки был приведен к безразмерному виду. В силу достаточной сложности задачи, удалось затронуть заявленные специфические аспекты использования указателей, динамической памяти, рекурсии.
На основе учебно-методического текста была разработана веб-страница в формате html для возможного размещения на сайте [1]. Текст был переработан, добавлены ссылки для скачивания промежуточных версий программы, для создания скриншотов кода на языке Pascal, формул и других изображений использовались бесплатные версии программ Free Pascal 2.6.0, Gimp 2.8.0, OpenOffice 3.4.0. Html-верстка составлена с соблюдением CSS-стилей и DOM структуры страниц вышеуказанного сайта.
В приложении имеются листинги всех промежуточных версий программы, документация на итоговую функцию, тестирующая программа, разработанная веб-страница и текст дипломной работы.
Список литературы
- В.З. Цалюк Этюды по алгоритмизации:
<#"justify">Учебные материалы Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича:
<#"justify">