ЛР№4-Вариант 6

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра компьютерных систем в управлении и проектировании (КСУП)

ОТЧЕТ

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

по дисциплине “программирование”

по учебно-методическому пособию Потаповой Е.А.

Выполнил студент

2015 г.

СОДЕРЖАНИЕ

1. Введение 3

2. Анализ задачи № 1 4

3. Решение задачи №1 5

3.1. Описание используемых переменных, обоснование выбора типа данных 5

3.2. Описание алгоритма 6

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

5. Решение задачи №2 10

5.1. Описание используемых переменных, обоснование выбора типа данных 10

5.2. Описание алгоритма 11

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

6. Заключение 14

Приложение 1. Листинг программ 15

Задача 1. 15

Задача 2. 17

Приложение 2. Распечатки тестов 19

Задача 1. 19

Задача 2. 20

1. Введение

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

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

Операция включения элемента в начало списка определяет, как можно построить список: начиная с пустого списка, последовательно добавляя элементы в его начало.

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

2. Анализ задачи № 1

Задача 1

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

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

3. Решение задачи №1

3.1. Описание используемых переменных, обоснование выбора типа данных

Переменные:

S – ссылка на очередное звено

L,L1 – списки с исходной и обратной последовательностью;

N – N-количество чисел, тип byte;

i – счетчик, тип byte;

x – переменная для ввода чисел, тип integer;

3.2. Описание алгоритма

1. Запрашиваем ввод количества чисел;

2. Создаем список путем добавления элемента в конец;

3. Выводим полученный список на печать;

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

5. Выводим обратный список на печать;

6. Очищаем память.

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

4. Анализ задачи № 2

Задача 2

Соединить конечное множество точек на плоскости замкнутой ломаной линией без самопересечений с вершинами в этих точках. (Полный перебор не делать; ответом будет порядок обхода точек плоскости.)

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

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

5. Решение задачи №2

5.1. Описание используемых переменных, обоснование выбора типа данных

Переменные и константы:

N – количество точек, const;

i – счетчик, тип byte;

XY – двумерный массив для хранения декартовых координат;

Polar – двумерный массив для хранения полярных координат.

5.2. Описание алгоритма

1. С помощью генератора случайных чисел заполняем массив XY координатами точек. Сразу переводим декартовые координаты в полярные и заполняем массив Polar;

2. Рисуем точки;

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

4. Соединяем линии согласно сортировки.

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

6. Заключение

В ходе лабораторной работы были проанализированы и разработаны алгоритмы решения задач с использованием списков и графического модуля. Был написан программный код и проведены тесты программ на работоспособность. Таким образом были усвоены базовые методы работы с динамическими структурами данных и графикой.

Приложение 1. Листинг программ

Задача 1.

Program lab4_var6_z1;

Type

link=^node;

node=record num:integer; next:link end; // тип описывает запись состоящую из числа и указателя на запись

var S, //ссылка на очередное звено

L,L1:link; //списки с исходной последовательностью и обратной

N // N-количество чисел

,i:byte; //счетчик

x:integer;//переменная для ввода чисел

procedure out_spisok(l : link); //процедура вывода списка на экран

begin

while l<> nil do

begin

s:=l^.next;

write(l^.num,' ');

l:=s;

end;

writeln;

end;

//процедура формирования исходного списка путем добавления элемента в конец линейного списка

procedure add(var l:link;m:integer);

var t,p:link;

begin

if l=nil then begin

new(l);

l^.num:=m;

l^.next:=nil;

end

else begin

t:=l;

while t^.next<>nil do t:=t^.next;

new(p);

t^.next:=p;

p^.num:=m;

p^.next:=nil;

end;

end;

//Процедура формирования обратного списка

procedure Rev(var S1,S2:link);

begin

while S1<>nil do

begin

new(S2);

S2^.next:=S;

S2^.num:=S1^.num;

S:=S2;

S1:=S1^.next;

end;

end;

//процедура освобождения динамической памяти

procedure Clear(var L:link);

begin

while L<> nil do

begin

s:=L^.next;

dispose(L);

L:=s;

end;

end;

BEGIN

Repeat

Writeln('Введите N(количество чисел) > 1 ');

Readln(N);

Until N>1;

//Создание списка

S:=nil;

For i:=1 to N do

begin

Writeln('Введите ',i,'-e число:');

readln(x);

add(L,x);

end;

writeln('Введенный список L:');

out_spisok(L);

Rev(L,L1);

writeln('Обратный список L1:');

out_spisok(L1);

//освобождаем динамическую память}

clear(L);

clear(L1);

END.

Задача 2.

Program lab4_var6_z2;

Uses GraphABC;

Const N=15; // Количество точек

Var i:byte;

XY:array[1..N]of array[1..2] of integer; // XY[i][1]-координата по X

// XY[i][2]-координата по Y

Polar:array[1..N]of array[1..2]of real;

// Polar[i][1]- угловая координата в полярной системе координат

// Polar[i][2]- радиальная координата в полярной системе координат

Procedure SwapCoords(Num:byte); //процедура обмена значений координат для сортировки

begin

swap(Polar[Num][1],Polar[Num+1][1]);

swap(Polar[Num][2],Polar[Num+1][2]);

swap(XY[Num][1],XY[Num+1][1]);

swap(XY[Num][2],XY[Num+1][2]);

end;

Procedure SORT; //процедура сортировки простым обменом

var i,j:byte;

begin

for i:=1 to N-1 do

for j:=1 to N-1 do

begin

// сравниваем округленные значения угловой координаты

if Round(Polar[j][1])>Round(Polar[j+1][1]) then SwapCoords(j)

// если равны, то сравниваем расстояние до полюса

else if Round(Polar[j][1])=Round(Polar[j+1][1]) then

if Polar[j][2]>Polar[j+1][2] then SwapCoords(j)

end;

end;

BEGIN

setwindowsize(900,600);

randomize;

For i:=1 to N do begin

XY[i][1]:=random(850)+25; //С помощью генератора случайных чисел

XY[i][2]:=random(550)+25; //устанавливаем координаты точек

Polar[i][1]:=arctan(XY[i][2]/XY[i][1])*180/pi; //высчитываем значение угла в градусах

Polar[i][2]:=sqrt(sqr(XY[i][1])+sqr(XY[i][2]));//и расстояние до точки

SetBrushColor(clRed);

Circle(XY[i][1],XY[i][2],3); //Отрисовываем точки

Sleep(333);

end;

SORT; //Сортируем точки

for i:=1 to N-1 do //Соединяем точки линиями согласно сортировки

begin

SetPenWidth(2);

Line(XY[i][1],XY[i][2],XY[i+1][1],XY[i+1][2]);

Sleep(333);

end;

END.

Приложение 2. Распечатки тестов

Задача 1.

1. Тестирование работы программы:

Задача 2.

1.Тестирование работы программы: