Моделирование представления в памяти таблиц

 














Лабораторная работа №1

Тема: Моделирование представления в памяти таблиц


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

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


Описание алгоритма работы программы


.Индивидуальное задание.

Все нулевые элементы расположены в шахматном порядке, начиная со

-го элемента 1-й строки

2.Выбор метода.

Во внутреннем представлении нет необходимости хранить элементы, нулевые по определению:

[x,y] = 0 при x + y mod 2.


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

Если XM mod 2=0 то d:= (y-1)*(XM/2) в другом случае цикл от 1 до у-1

Если i mod 2=0 то d:=d+(XM-1)/2, иначе d:=d+(XM+1)/2

:=round(d+(x/2 + 0.1))


где x, y - номера столбца и строки соответственно;- число элементов в строке.

3.Описание переменных

Переменные, глобальные для всего модуля:

matrix - массив, представляющий матрицу традиционным образом, используется для сравнения времен доступа;

arrp - массив, представляющий сжатую матрицу;

XM - размер матрицы

4.Описание программы

Функция NewIndex реализует вычисления по формуле (1).

Функция PutTab проверяет условие нахождения элемента по заданию

(x+y mod 2). Если это так, функция возвращает 0, в противном случае при помощи функции NewIndex вычисляется индекс в массиве arrp, производится запись в arrp и возврат value.

Функция GetTab проверяет условие нахождения элемента. Если это так, функция возвращает 0, в противном случае при помощи функции NewIndex вычисляется индекс в массиве arrp, и возвращаемое значение выбирается из arrp.

Алгоритм основной программы может быть разбит на 2 части.

Часть 1 предназначена для проверки правильности формирования сжатого представления матрицы. Она работает с матрицей размера 20х20, поэтому в начале этой части задается XM:=20. Далее формируется содержимое матрицы таким образом, чтобы в ненулевые элементы записывались последовательно возрастающие числа. Затем проверяется правильность доступа к матрице - при всех возможных значениях x и y выводятся на печать значения, возвращаемые функцией GetTab. И наконец проверяется сжатое представление матрицы - последовательно выводится на печать массив arrp.


Блок-схема программы


Блок-схема программы приведена в Приложении.


Текст программы


Program LAB2;crt, dos;: array[1..5050] of integer;: array[1..100, 1..100] of integer;: integer;, finish, x1, x2: longint;, min, sec, ssec: word;NewIndex(y, x : integer) : integer;i, j: integer;: real;:=0;XM mod 2 = 0 then:= (y-1)*(XM/2)i:=1 to y-1 doi mod 2 = 0 then:=d+(XM-1)/2:=d+(XM+1)/2;;:=round(d+(x/2 + 0.1));;PutTab(y,x,value : integer) : integer;(x+y) mod 2 <> 0 then PutTab:=0begin[NewIndex(y,x)]:=value;:=value;;;GetTab(y,x: integer) : integer;(x+y) mod 2 <> 0 then:=0GetTab:=arrp[NewIndex(y,x)];;time: longint;(hour, min, sec, ssec);:= sec*100+min*6000+ssec;, y : integer;, h: integer;clrscr;;:=20;:=1;y:=1 to XM dox:=1 to XM do:=PutTab(y,x,k);:=k+1;;('====Массив====');:= time;y:=1 to XM do beginx:=1 to XM do(GetTab(y,x):3);;;;:= time;:=finish - start;;:=0;y:=1 to XM dox:=1 to XM do:=k+1;(x+y) mod 2 <> 0 then[y][x] := 0[y][x] := k;

end;('====Матрица после обработки====');

start:= time;y:=1 to XM do beginx:=1 to XM do(matrix[y][x]:3);;;:= time;:=finish - start;('time1 = ', x1);('time2 = ', x2);('<< >>');y:=1 to round(XM*XM/2+0.1) do(arrp[y]:4);; writeln;

readln;.

<<матрица выборки из сжатого представления массива>>

0 3 0 5 0 7 0 9 0

12 0 14 0 16 0 18 0 20

0 23 0 25 0 27 0 29 0

32 0 34 0 36 0 38 0 40

0 43 0 45 0 47 0 49 0

52 0 54 0 56 0 58 0 60

0 63 0 65 0 67 0 69 0

72 0 74 0 76 0 78 0 80

0 83 0 85 0 87 0 89 0

92 0 94 0 96 0 98 0100

<< матрица >>

0 3 0 5 0 7 0 9 0

12 0 14 0 16 0 18 0 20

0 23 0 25 0 27 0 29 0

32 0 34 0 36 0 38 0 40

0 43 0 45 0 47 0 49 0

52 0 54 0 56 0 58 0 60

0 63 0 65 0 67 0 69 0

72 0 74 0 76 0 78 0 80

0 83 0 85 0 87 0 89 0

92 0 94 0 96 0 98 0100= 4= 4

===== Матрица (внутр.представление) =====

3 5 7 9 12 14 16 18 20 21 23 25 27 29 32 34 36 38 40

43 45 47 49 52 54 56 58 60 61 63 65 67 69 72 74 76 78 80

83 85 87 89 92 94 96 98 100

Поскольку по данным результатам нельзя определить вывод, какой матрицы осуществляется быстрей (матрицы, которая восстанавливается из сжатого представления массива или просто матрицы которая хранится в памяти) я повторил исследование, увеличив размер матрицы до 30х30 и повторил вывод каждой матрицы по 10 раз. Таким образом, я получил большое время выполнение операций, и за счет этого я узнал разницу между выполнением операций. 1 матрица вывелась за 1091 сс, а 2 - 1295 сс. Следует вывод, что матрица в сжатом виде распечатывается быстрей.


Вывод

память таблица хронометраж

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


Приложение



Рис. 1 - блок-схема главной программы

Рис. 2 - блок-схема подпрограммы NewIndex.


Рис. 3 - блок-схема подпрограммы PutTab.


Рис. 4 - блок-схема подпрограммы GetTab.


Рис. 5 - блок-схема подпрограммы time.


Лабораторная работа №1 Тема: Моделирование представления в памяти таблиц Цель: Приобретение и закр

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ