ВУЗ: Пермский национальный исследовательский политехнический университет
Категория: Лекция
Дисциплина: Программирование
Добавлен: 19.10.2018
Просмотров: 5240
Скачиваний: 10
СОДЕРЖАНИЕ
Лабораторная работа №11, вариант № 5.
9.3.1. Слияние упорядоченных последовательностей.
9.3.2. Сортировка сбалансированным слиянием
9.3.3. Сортировка простым слиянием
9.3.4. Сортировка естественным слиянием.
9.3.5. Сортировка многофазным слиянием.
Выполнение операций над списковыми структурами.
Выполнение операций над списковыми структурами.
Работа со стеками и очередями.
Работа со стеками и очередями.
11. Организация меню с использованием средств среды Turbo Pascal
10) проверить, является ли содержимое текстового файла t правильной записью формулы следующего вида:
<формула>::=<терм><терм>+<формула>
<терм>-<формула>
<терм>::=<имя>(<формула>)[<формула>]
<имя>::=xyz
11) в текстовом файле f записана без ошибок формула следующего вида:
<формула>::=<цифра>М<формула>,<формула>
m<формула>,<формула>
<цифра>::=0123456789,
где М обозначает функцию max, m - min.
Вычислить (как целое число) значение данной формулы (например, М(5,m(6,8))=6).
12) в текстовом файле записано без ошибок логическое выражение (ЛВ) в следующем виде:
<ЛВ>::=true false (\<ЛВ>) (<ЛВ>^<ЛВ>) (<ЛВ>V<ЛВ>),
где знаки \ , ^ , V обозначают соответственно отрицание, конъюнкцию, дизъюнкцию.
Вычислить (как boolean) значение этого выражения.
5. Используя очередь и/или стек (считать уже описанными их типы и операции над ними ) решение описать в виде процедуры).
В текстовом файле записан текст, сбалансированный по круглым скобкам :
<текст>::=<пусто><элемент><текст>
<элемент>::=<буква><текст>
Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте , упорядочив пары номеров в порядке возрастания номеров позиций
13)закрывающих скобок;
14)открывающих скобок.
Например, для текста A+(45-F(X)*(B+C)) надо напечатать:
13) 8 10; 12 16; 3 17;
14) 3 17; 8 10; 12 16;
Под <выражением> будем понимать конструкцию следующего вида
<выражение>::=<терм><терм><знак+-><выражение>
<знак+->::=+-
<терм>::=<множитель><множитель>*<терм>
<множитель>::=<число><переменная>(<выражение>)
<множитель>^<число>
<число>::=<цифра>
<переменная>::=<буква>,
где знак ^ обозначает возведение в степень.
Постфиксной формой записи выражения a^b называется запись, в которой знак операции размещен за операндами: ab^.
Например:
a+b-c это ab+c-
a*b+c это ab*c+
15) описать функцию value(postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в постфиксной форме в текстовом файле postfix.
Использовать следующий алгоритм вычисления:
Выражение просматривается слева направо. Если встречается операнд (число), то его значение (целое) заносится в стек, а если встречается знак операции , то из стека исключаются два последних элемента (это операнды данной операции) над ними выполняется операция и ее результат записывается в стек. В конце концов в стеке остается только одно число - значение всего выражения.
16) описать процедуру translate ( infix, postfix ), которая переводит выражение, записанное в обычной (инфиксной) форме в текстовом файле infix в постфиксную форму и в таком виде записывает его в текстовый файл postfix. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая тоже удаляется из стека, и все эти знаки в (порядке извлечения) записываются в файл postfix. Когда же встречается знак операции, то из конца стека извлекаются (до ближайшей скобки, которая сохраняется в стеке ) знаки операций, старшинство которых больше или равно старшинству данной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В заключение выполняются такие же действия, как если бы встретилась закрывающая скобка.
17) описать (нерекурсивную) процедуру infixprint(postfix), которая печатает в обычной (инфиксной) форме выражение, записанное в постфиксной форме в текстовом файле postfix.
18) описать (нерекурсивную) процедуру postfixprint(infix), которая печатает в постфиксной форме выражение, записанное в инфиксной форме в текстовом файле infix.
Для решения следующих задач использовать двоичные деревья при следующем их описании:
type тип= некоторый тип элементов дерева;
дерево=^вершина;
вершина=record элем: тип элементов дерева;
лев, прав: дерево end;
В задачах Т, Т1, Т2 обозначают деревья, Е - величину некоторого типа элементов дерева.
6. Используя очередь или стек (считать уже описанными их типы и операции над ними ) описать процедуру или функцию, которая :
1) присваивает параметру Е элемент из самого левого листа непустого дерева Т;
2) определяет число вхождений элемента Е в дерево Т;
3) вычисляет среднее арифметическое всех элементов непустого дерева Т (тип элементов дерева real);
4) заменяет в дереве Т все отрицательные элементы на их абсолютные значения (тип элементов дерева real);
5) меняет местами максимальный и минимальный элементы непустого дерева Т, все элементы которого различны (тип элементов дерева real);
6)печатает все элементы из всех листьев дерева Т (тип элементов дерева char);
7) печатает все элементы дерева Т по уровням: сначала - из корня дерева, затем (слева направо) - из вершин дочерних по отношению к корню, затем (слева направо) - из вершин дочерних по отношению к этим вершинам и т. д. (тип элементов дерева integer);
8) находит в непустом дереве Т длину пути от корня до ближайшей вершины с элементом Е, если Е не входит в Т , то за ответ принять -1.
9) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня).
7. Написать рекурсивную функцию или процедуру, которая:
10) определяет, входит ли элемент Е в дерево Т;
11) определяет число вхождений элемента Е в дерево Т;
12) вычисляет сумму всех элементов непустого дерева Т (тип элементов дерева real);
13) находит величину наибольшего элемента непустого дерева Т (тип элементов дерева real);
14)печатает все элементы из всех листьев дерева Т (тип элементов дерева char);
15) определяет максимальную глубину непустого дерева Т, т. е. число ветвей в самом длинном из путей от корня дерева до листьев;
16) подсчитывает число вершин на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня);
17) Рекурсивно и нерекурсивно описать логическую функцию equal(T1, T2), проверяющую на равенство деревья Т1 и Т2;
18) описать процедуру copy(T, T1) , которая строит дерево Т1 - копию дерева Т;
19) описать логическую функцию same (T), которая определяет , есть ли в дереве Т хотя бы два одинаковых элемента;
Опишем следующий вид дерева, который можно назвать “деревом-формулой”. Формулу вида:
<формула>::=<терминал><формула><знак><формула>
<знак>::=+-*
<терминал>::=0123456789
можно представить в виде двоичного дерева с типом элементов дерева = char согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1 s f2 ) - деревом, в котором корень это знак s, а левое и правое поддеревья - это соответствующие представления формул f1 и f2. На рис. 5 показано дерево-формула, соответствующее формуле(5*(3+8))).
Рис. 5
Описать рекурсивную функцию или процедуру, которая:
20) вычисляет (как целое число ) значение дерева-формулы Т;
21) по формуле из текстового файла F строит соответствующее дерево- формулу Т;
22) печатает дерево- формулу Т в виде соответствующей формулы;
23) проверяет, является ли двоичное дерево Т деревом формулой.
11. Организация меню с использованием средств среды Turbo Pascal
Turbo Pascal предоставляет возможность организации меню с помощью встроенного стандартного модуля CRT.
Инициализация модуля CRT:
Program name;
Uses CRT, {через запятую перечисляются другие нужные в данной программе модули};
Type ……
……
var ……
……
begin
end.
В модуле CRT сосредоточены процедуры и функции, обеспечивающие управление текстовым режимом работы экрана. С помощью входящих в модуль программ можно перемещать курсор в произвольную позицию экрана, менять цвет выводимых символов и окружающего их фона, создавать окна. Кроме того, в модуль включены также процедуры “слепого” чтения клавиатуры и управления звуком.
В режиме текстового вывода используются следующие координаты экрана: левый верхний угол экрана имеет координаты 1,1; горизонтальная координата возрастает слева направо, вертикальная -сверху вниз. Если на экране определено окно, все координаты определяются относительно границ окна.
Для чтения клавиатуры используются две функции –KeyPressed и ReadKey. Функция KeyPressed определяет факт нажатия на любую клавишу и не приостанавливает дальнейшего исполнения программы.
Функция ReadKey читает расширенный код нажатой клавиши. Если к моменту обращения к функции не была нажата ни одна клавиша, то программа приостанавливает работу, ожидая действия пользователя.
Управления звуковым генератором строится по схеме: Sound –Delay –NoSound. Процедура Sound(n), (где n-параметр в Герцах type n:Word), включает звуковой генератор и заставляет его непрерывно генерировать звук нужного тона. Процедура Delay(n), (где n-параметр в миллисекундах type n:word), приостанавливает роботу программы на заданное число миллисекунд реального времени. Процедура NoSound отключает звуковой генератор.
Определение текстового окна на экране выполняется с помощью процедуры Window(x1,y1,x2,y2: byte), где x1,y1 –координаты левого верхнего угла, x2,y2 –правого нижнего угла.
Clrscr; - процедура без параметра, очищает текущее окно и придает ему цветовые параметры заданные прежде.
Определение цвета текстового окна на экране выполняется с помощью процедур:
Textcolor(код цвета), цвет символов,
Textbackground(код цвета), цвет фона.
0 |
Чёрный |
1 |
Синий |
2 |
Зелёный |
3 |
Голубой |
4 |
Красный |
5 |
Фиолетовый |
6 |
Коричневый |
7 |
Тёмно-серый |
8 |
Светло-серый |
9 |
Ярко-голубой |
10 |
Ярко-зелёный |
11 |
Ярко-голубой |
12 |
Розовый |
13 |
Ярко-фиолетовый |
14 |
Жёлтый |
15 |
Белый |
Лабораторная работа №17.
Составления меню.
Цель работы:
-
Закрепить полученные теоретические знания и практические навыки.
-
Изучить стандартный модуль TurboPascal CRT.
-
Познакомится с работой с окнами.
-
Освоить некоторые методы сортировки записей.
Постановка задачи:
-
Написать программу, которая формирует меню, состоящее из 9 пунктов
1. Открыть.
2. Создать.
3. Поиск.
4. Добавить.
5. Удалить.
6. Корректировка.
7. Просмотр.
8. Сортировка.
9. Выход.
Каждый пункт должен быть оформлен в виде отдельной процедуры.
-
В каждой процедуре должна быть проверка существования файла.
-
Программа должна работать с данными, приведёнными в конкретном варианте.
Содержание отчёта:
-
Постановка задачи для конкретного варианта.
-
Распечатать исходные данные.
-
Текст программы.
-
Распечатка результатов работы программы после выполнения пунктов меню 4,5,6 и 8.
Образец выполнения работы.
Лабораторная работа № 17.
Составления меню.
Постановка задачи:
Написать программу, которая формирует меню, состоящее из 9 пунктов
-
Открыть.
-
Создать.
-
Поиск.
-
Добавить.
-
Удалить.
-
Корректировка.
-
Просмотр.
-
Сортировка.
-
Выход.
Анкетные данные на абитуриентов в конце методического пособия.
Текст программы:
program menu;
uses crt,dos;
const text1='Год рождения..........';
text2='Год окончания школы...';
text3=' Оценки в атестате';
text4='Метематика............';
text5='Физика................';
text6='Русский язык..........';
text7=' Оценки на вступительных экзаменах';
text8='Нуждается в общежитии';
text9='Не нуждается в общежитии';
type data=record
fio:string[30];
godr,godo:integer;
ates:record
mat,fiz,rus:integer;
end;
haus:boolean;
ekz:record
mat,fiz,rus:integer;
end;
end;
filetype=file of data;
var stu:data;
files,filetemp:file of data;
name,path,namefile:string;
keys:char;
menuunit:byte;
rec,position,freeunit:integer;
quit,openfile:boolean;
procedure sortirovka;
var a,b,c:filetype;
z:integer; {для подсчета числа серий}
eor:boolean; {индикатор конца серии}
procedure copys(var x,y:filetype);
var buf,buf1:data;
begin
read(x,buf);write(y,buf);
if eof(x) then eor:=true
else begin
{заглядываем вперед}
read(x,buf1);
{возвращаемся на исходную запись}
seek(x,filepos(x)-1);
if keys='1' then eor:=copy(buf1.fio,1,1)<copy(buf.fio,1,1);
if keys='2' then eor:=buf1.godr<buf.godr;
if keys='3' then eor:=buf1.godo<buf.godo;
end;
end;
procedure copyrun(var x,y:filetype);
{переписать серии из x в y}
begin
repeat
copys(x,y);
until eor;
end;
procedure mergerun;
{слияние серий из А и В в С}
var bufa,bufb:data;
begin
repeat
read(a,bufa);seek(a,filepos(a)-1);
read(b,bufb);seek(b,filepos(b)-1);
if keys='1'then if copy(bufa.fio,1,1)<copy(bufb.fio,1,1)
then begin;copys(a,c);if eor then copyrun(b,c);end
else begin;copys(b,c);if eor then copyrun(a,c);end;
if keys='2'then if bufa.godr<bufb.godr
then begin;copys(a,c);if eor then copyrun(b,c);end
else begin;copys(b,c);if eor then copyrun(a,c);end;
if keys='3'then if bufa.godo<bufb.godo
then begin;copys(a,c);if eor then copyrun(b,c);end
else begin;copys(b,c);if eor then copyrun(a,c);end;
until eor
end;
procedure distribute; {из С в А и В}
begin
reset(c);rewrite(a);rewrite(b);
repeat
copyrun(c,a);
if not eof(c) then copyrun(c,b);
until eof(c);
close(a);close(b);close(c);
end;
procedure merge;
begin
reset(a);reset(b);rewrite(c);
while (not eof(a))and(not eof(b)) do
begin
mergerun;z:=z+1;
end;
while not eof(a) do begin;copyrun(a,c);z:=z+1;end;
while not eof(b) do begin;copyrun(b,c);z:=z+1;end;
close(a);close(b);close(c);
end;
begin {main}
close(files);
assign(c,namefile);
assign(b,'c:\file2');
assign(a,'c:\file3');
repeat
distribute;z:=0;
merge;
until z=1;
erase(a);erase(b);
reset(files)
end;
procedure intemp;
begin
reset(files);rewrite(filetemp);
repeat read(files,stu);write(filetemp,stu);until eof(files);
reset(filetemp);rewrite(files);
end;
procedure outtextmenu(nmenu:byte;invert:boolean);
begin
window(30,nmenu+7,43,nmenu+7);
if invert then begin textbackground(2);textcolor(0);end
else begin textbackground(0);textcolor(15);end;
case nmenu of
1:write('Открыть ');
2:write('Создать ');
3:write('Поиск ');
4:write('Добавить ');
5:write('Удалить ');
6:write('Корректировка');
7:write('Просмотр ');
8:write('Сортировка ');
9:write('Выход ');
end;
end;
procedure reader;
begin
writeln(' Вводим данные об абитуриентах');
writeln(' Фамилия Имя Отчество');readln(stu.fio);
write(text1);readln(stu.godr);
write(text2);readln(stu.godo);
writeln(text3);
write(text4);readln(stu.ates.mat);
write(text5);readln(stu.ates.fiz);
write(text6);readln(stu.ates.rus);
writeln('Нуждается ли в общежитии (1-да/2-нет)');
keys:=readkey;if keys='1' then stu.haus:=true
else stu.haus:=false;
writeln(text7);
write(text4);readln(stu.ekz.mat);
write(text5);readln(stu.ekz.fiz);
write(text6);readln(stu.ekz.rus);
end;
function outfile:boolean;
begin
if fsearch(namefile,'')='' then begin;
outfile:=true;
namefile:='**********';
end
else outfile:=false;
end;
procedure cls;
begin
window(1,1,80,25);textcolor(15);textbackground(0);clrscr;
nosound;
end;
procedure sort;
begin
window(1,1,39,6);textcolor(0);textbackground(14);clrscr;
nosound;
writeln(' Сортировка');
writeln('1-по Фамилие');
writeln('2-по Году рождения');
writeln('3-по Году поступления');
writeln('4-Выход');
repeat
keys:=readkey;
if keys='1' then begin sortirovka;keys:='4';end;
if keys='2' then begin sortirovka;keys:='4';end;
if keys='3' then begin sortirovka;keys:='4';end;
until keys='4';
cls;writeln('Фамилия Имя Отчество');
end;
procedure startmenu;
label ex;
begin
if not openfile then goto ex;
reset(files);
rec:=0;
while not eof(files) do begin read(files,stu);rec:=rec+1;end;
ex:window(1,1,80,25);textcolor(15);textbackground(0);clrscr;
writeln('Рабочий файл :',namefile,', записей в файле:',rec);
for menuunit:=1 to 9 do outtextmenu(menuunit,false);
end;
procedure koreckt;
var zamena:data;
begin
window(1,1,39,22);textcolor(0);textbackground(14);clrscr;
nosound;
reader;
zamena:=stu;
intemp;
freeunit:=1;
while not eof(filetemp) do
begin
read(filetemp,stu);
if freeunit=position then write(files,zamena)
else write(files,stu);
freeunit:=freeunit+1;
end;
cls;writeln('Фамилия Имя Отчество');
end;
procedure delet;
begin
intemp;
freeunit:=1;
while not eof(filetemp) do
begin
read(filetemp,stu);
if position=freeunit then rec:=rec-1
else write(files,stu);
freeunit:=freeunit+1;
end;
if position=rec+1 then begin position:=position-1;if position=0 then position:=1;end;
end;
procedure lookmenu;
label ex;
const fiounit=20;
begin
if not(openfile) or (rec=0) then goto ex;
if menuunit=3 then position:=freeunit
else position:=1;
writeln('Фамилия Имя Отчество');
repeat
freeunit:=1;
reset(files);while not(freeunit=position) do begin read(files,stu);freeunit:=freeunit+1;end;
window(40,7,80,20);textcolor(3);textbackground(0);clrscr;
read(files,stu);