Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»

С=Вставка(A,b)   i Dom(C) (c_i  A or c_i =b) & Упорядочена(С)

С=Удаление(A,b)   i Dom(C) (c_i  A and c_i b) & Упорядочена(С)
С=A  B   i Dom(C) (c_i  A or c_i  B) & Упорядочена(С)

С=A  B   i Dom(C) (c_i  A and c_i  B) & Упорядочена(С)

С=A \ B   i Dom(C) (c_i  A and c_i  B) & Упорядочена(С)
где x f   i Dom(f) (x=f(i))
Практическая мотивация их использования - в отличие от алгоритмов сортировки (см. след. тему), все следующие ниже алгоритмы однопроходные, т.е. сохранять упорядоченность легче, чем сортировать (особенно – для типов с последовательным доступом!)
Направляющая общая идея реализации - кратный ограниченный поиск в упорядоченной последовательности - для ответа на вопрос x  a, достаточно найти “барьер”, т.е. первый a_i такой, что xa_i. (Подробнее см. "Поиск").

1. 
   Разность упорядоченных файлов. Здесь и далее TInfo – произвольный тип, на котором определен некоторый линейный порядок <.
   

TFile=file of tInfo;

{предусловие – удобнее считать, что файл B не пуст}

procedure Разность( var A,B:tFile;

var C:tFile); {c:=a\b}

var

BarrierFound, {= i (сA<= b_i)}

found:boolean; {cA b}

begin

read(B,cB); {по условию файл B не пуст }

{ в противном случае, решение очевидно – скопировать A в C}

while not eof(A) do

begin

read(A,cA); BarrierFound:= cA<=cB ;

begin

end;

if not found then write(C,cA)

end;

end; { Разность }

type

tArray=array[tIndex] of tInfo;

procedure Слияние(A,B:tArray;LenA,LenB:tIndex;var C:tArray;var LenC:tIndex); {c:=ab}

var

BarrierFound: boolean; {= B[j]A[i] }

begin

LenC:=0; j:=1;

begin

{скопируй все элементы B[j], B[j]A[i] в С }

BarrierFound :=false;

while (j<=LenB) and not BarrierFound do

begin

if B[j]A[i]

else BarrierFound :=true;

end;

C[LenC]:=A[i];inc(LenC)

end {procedure Слияние }

Type

pList=^tList;

tList=record

info:tInfo; {некий тип со сравнением <}

next:pList

end;
Procedure Вставка( var pA:pList;

{А - исходная упорядоченная последовательность с барьером}

pX:pList; {ссылка на вставляемое значение x} );

var

x:tInfo;

Begin

{найди ссылку This на первую компоненту со значением info, не меньшим x}

Prev:=nil; This:=pA; found:=false

While (This<>nil) and not found do

If This^.info>=x

then found:=true

else begin Prev:=This;This:=This^.next end;

{found=true и This<>nil, по определению барьера}

{вставляем между Prev и This}

pX^.next:=This; if Prev<>nil then Prev^.next:=pX

End;

§ 7. Сортировка.

F

a₁… a_i+N+1

Задача - найти такой оператор F - по возможности, с достаточно быстро растущим N, N=N(a). Наиболее простые для понимания идеи нахождения нужного F основаны непосредственно на определении (спецификации) упорядоченности.

Последовательность а  [1..n]T упорядочена

 a)  i  [1..n-1] (a_i  a_i+1) (идея - сортировка простым обменом - обмен значений "неправильных" соседних пар)

 b)  i  [1..n-1]  j  [i+1..n] (a_i  a_j) (идея - "пузырьковая" сортировка - обмен значений "неправильных" пар нужного вида)  с)  i  [1..n-1] (a_i = min (a[i,n]) (идея - поиск соответствующего минимума)

{здесь и далее tIndex=1..MaxLen; tArray=array[tIndex] of T, для некоторого типа T с некоторым определенным на его элементах сравнением <, LenA - фактическая длина массива А};

var ПустойПроход:boolean; {= i  [1..n-1] (a_i  a_i+1) }

begin

repeat

for i:=1 to n-1 do

if a[i]>a[i+1] then begin Обмен(a[i],a[i+1]); ПустойПроход:=false end;

until ПустойПроход

end; { СортировкаПростымОбменом }

Замечание о сходимости алгоритма. 1 проход не упорядочивает массив, но - увеличивает отсортированную часть!

var i:tIndex;

begin

for i:=1 to LenA do {Вставить A[i] в упорядоченный к этому времени массив A[1..i-1]}

procedure СортировкаСлиянием(var A:tArray;LenA:tIndex);

var

i,

l, {=2ⁱ , длина сливаемых подмассивов}

l:=1; m:=LenA;

for i:=1 to LenA div 2 do

{Слить попарно все упорядоченные к этому времени подмассивы длины 2ⁱ , всего 2^n-i слияний }

t:=1; for k:=1 to m do

begin

end; { for k:=1 to m }

A:=B;l:=l*2;m:=m div 2;

end; { i:=1 to LenA div 2 }

end; { procedure СортировкаСлиянием }

§8. Машинно-ориентированное программирование.

1. 
   Бинарное присваивание вида v:=[v]v', где v -переменная, v' - переменная или константа. Семантика - обычная, но с очевидным оттенком "довычисления"
   
2. 
   Составной оператор ; (в машинных языках обычно никак не обозначается)
   
3. 
   Оператор условного перехода вида [if B then] goto M, где B элементарная логическая формула (т.е. формула, не содержащая логических операций) - например, сравнение. Содержательная семантика - "после этого оператора будет выполняться не следующий за ним, но тот, перед которым стоит метка вида M: "
   

Формальная семантика этого оператора довольно сложна - в кажущемся противоречии с определением оператора, этот оператор как будто не меняет значения ни одной переменной (на деле, он не меняет значений пользовательских переменных). Именно поэтому оператором goto не рекомендуют использовать в обычной программистской практике. Больше того, реальность еще сложнее - машинные языки содержат операторы перехода на переменные-метки вида goto x^ - перейди на оператор, метка на который содержится в переменной x.

while B do S  M1: if B=false then goto M2; goto M1; M2:

1. 
   их запись в двоичной системе счисления (двоичный формат). Алгоритмы перевода в k-ичную систему счисления, k Z, см. "Задачи текстовой обработки" или
   
2. 
   их запись в обычной 10-ной системе счисления (предварительно перекодировав алфавит {'0'..'9'} битовыми строками) (символьный формат)
   

Этот способ "работает" для любых типов данных - значения любого типа можно как-то выразить в некоторой системе обозначений! Далее для простоты мы полагаем, что работаем лишь с одним выбранным форматом каждого скалярного типа - их представлением в виде строк некоторой фиксированной длины Len(T).

Пример. Написать программу на определенном выше языке, определяющую, есть ли данное значение x в последовательности a из 10 чисел, если известны адрес AdrX числа x и AdrA начала поля, содержащего числа из а. Все числа представлены в некотором формате длины L=16.

i:=1;

if a[i]=x then b:=true else i:=i+1

1. 
   Избавимся от операций выборки.
   

i:=1;

while (i<=n) and not b do

if Memory[CurrentAdr,16]=x

then b:=true

else begin i:=i+1; CurrentAdr:=CurrentAdr+16 end;

2. 
   Избавимся от сложных выражений
   

i:=1;

{go:= (i<=n) and not b}

{предполагаем быстрое означивание -см. "Вычисление свойств"}

go:=false; if i<=n then if b=false then go:=true

while go do

begin

if a[i]=x then b:=true else begin i:=i+1; CurrentAdr:=CurrentAdr+16 end;

end;

3. 
   Избавимся от структурных операторов.
   

i:=1;

go:=false;

{if i<=n then if b=false then go:=true }

if i<=n then goto M1

if b=false then goto M1

go:=true;

M1: if go=false then goto M2 {while go }

{if a[i]=x then b:=true else inc(i);}

if a[i]=x then goto M3

i:=i+1;

M3: b:=true

M4: {go:=false; if i<=n then if b=false then go:=true}

if i<=n then goto M5

if b=false then goto M5

go:=true;

M5: goto M1
Окончание - надо заменить идентификаторы на указание адреса xMemory[AdrR,16] и соответствующие выражения для остальных переменных.
§ 9. Абстрактные линейные типы.
Напомним, понятие абстрактного типа относительно - это те типы, существующие как математическое понятие, т.е. пара , F AA (см. "Основные понятия"), которые отсутствуют в данном языке программирования. Тип, абстрактный для одного языка, может быть вполне конкретным для другого.
Рассмотрим некоторые общие принципы реализации абстрактных типов на примере двух простых и естественных типов - стек и очередь. (Применение - см. далее "Перечисление последовательностей" и "Нелинейные абстрактные типы данных").
В обоих случаях, основным множеством типа является множество всех (конечных) последовательностей f произвольной длины LenF над некоторым базовым типом T - f  NT, Dom(f)=[1..LenF], LenF  N. Т.е. оба типа, вообще говоря, - динамические; в случае фиксированной длины можно говорить о статических, (или, чуть точнее - псевдодинамических стеках и очередях, см. "Классификация типов").

(Строго говоря, в случае очереди удобнее считать последовательностью функцию f c областью определения - интервалом [n,m]=[n,n+LenF], отождествляя все такие интервалы одинаковой длины c интервалом [1..LenF]. См. определение операторов обработки очереди далее)

var

r:tStack; {символьный стек}

begin

create(r); reset(InputFile);

close(InputFile);

rewrite(OutputFile);

while not Empty(r) do begin pop(r,c); write(OutputFile,c) end;

close(OutputFile);

destroy(r)

end;
Интуитивная идея очереди - "тот, кто пришел первым, первым и уйдет" (First In First Out, англ.)
Операторы и функции определения очереди.
Операторы.

Create(r), Destroy(r) - тождественны соответствующим стековым операциям.

Put(r,x) - Поставить В Очередь - добавить компоненту x (базового типа T) в конец очереди - начиная работать в состоянии rR, cо очередью длины Len(R) Dom(R)=[n..m], этот оператор неявно доопределяет Dom(R) до [n..m+1] и осуществляет присваивание R[m]:=x.

Get(r,x) - Вывести Из Очереди - осуществляет присваивание x:=R[n] (кладет первую компоненту очереди в x) и сокращает Dom(R) до [n+1..m] (уничтожает начало очереди).
Предикат Empty(r) (очередь пуста) - тождественен соответствующему предикату над стеком.
Стек и очередь - абстрактные для Паскаля типы, потому их необходимо реализовать имеющимися в нем средствами.
Реализация стеков и очередей (псевдодинамическими) массивами.
Псевдодинамические массивы - последовательности переменной длины m, mMaxLen, где MaxLen - константа.

const MaxLen=100;

type

tIndex=1..MaxLen;

tPseudoArray=

record content:tArray; {содержимое/компоненты массива}

{можно задать len:tIndex; фактическая длина массива}

{или - принимаемый далее вариант}

top:tIndex; {len+1, первое свободная позиция в массиве, начало кучи -незаполненной части массива }

end;

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

type

tStack=tPseudoArray;

begin with stack do begin top:=top-1; x:=Content[top] end; end;

procedure Push(var stack:tStack;x:T);

begin with stack do begin Content[top]+1; top:=top+1; end; end;

{при неосмотрительном использовании, выполнение операторов чревато }

{выходом за границы массива [1..MaxLen]}

{но ситуация не совсем симметрична, у пользователя есть функция проверки пустоты стека, но нет функции проверки переполнения стека }

function Empty(Stack:tStack):boolean;

begin Empty:=Stack.top=1 end

procedure Create(var Stack:tStack); begin Stack.top:=1 end;

procedure Destroy(Stack:tStack) ); begin Stack.top:=1 end;
Одинаковая реализация разных операций, конечно, настораживает. Create призвана порождать функцию (с пустой областью определения), Destroy - уничтожать функцию (с любой областью определения), наша релизация лишь опустошает область определения функции. Причина ясна - мы никак не моделируем понятие состояния (см. далее) Пока оставим нюансы - так или иначе, главные стековые операции push и pop работают правильно.
Обратимся к моделированию очередей. Определим "псевдодинамические" массивы с двумя концами.

tPseudoArray2=

record content:tArray; {содержимое/компоненты массива}

start, finish:tIndex; {начало+1 и конец-1 массива -}

{начало правой кучи и конец левой кучи}

end;

Правда, в этом частном случае ее нетрудно решить, объединяя две части кучи, мысленно рассматривая массив как кольцо.

procedure Put(var Queue:tQueue; x:T); { Поставить В Очередь }

begin

with Queue do

if finish=nMax then finish:=1 else inc(finish) { finish:=finish+1 (mod nMax)}}

{интересно - см. понятие модульной арифметики в курсе дискретной математики}

end; end;

procedure Get(r,x); { Вывести Из Очереди }

begin

begin x:= content[start];

if start=1 then start:=nMax else dec(start) { start:=start-1 (mod nMax)}}

end; end;

function Empty(r):boolean;

begin Empty:= (start=finish) or ((start=nMax) and (finish=1)) {start=finish (mod nMax)} end;

• 
  необходимо сохранить некоторую последовательность f,
  
• 
  но нет ни одной кучки (сплошного незанятого участка памяти), достаточной для хранения всех элементов последовательности f в естественном порядке,
  
• 
  
  хотя совокупного объема свободной памяти для этого достаточно.
  

О
чевидный вариант решения проблемы - дефрагментация - копирование полезной информации в одну, а куч свободной памяти - в другую часть памяти - действительно, иногда применяется, но очевидно, крайне трудоемок (по времени).

2,f(1)>, F(n₂)=3,f(2)>,.., F(n_i)=_i+1,f(i)>,… F(n_k)=< n_k+1,f(k)>
Такой способ хранения последовательностей называется списковой организацией памяти, или просто списком. По определению, список F хранит значения f и индекс (указатель,"имя") следующего ее значения. Указатель n₁ называют головой списка, указатель n_k+1, не принадлежащий Dom(F) - признаком конца списка. Обычно, в качестве признака выделяют специальный "пустой" указатель 0 (например, число 0 или -1), единственный смысл которого - ни на что не указывать (по определению, 0 Dom(F) для всех списков F).
Основные операции над списками - перечисление, вставка и удаление компонент - никак не используют арифметические операции на Dom(F), т.е. тот факт, Dom(F)N, а лишь то, что они, в качестве имен, указывают (ссылаются) на значения. Это и делает возможным реализацию списков ссылочным типом.

type

tComponent=record value:T;next:p:pComponent end;

pComponent=^tComponent;

pList=pComponent;

{список задается ссылкой на голову - первую компоненту списка}

{или значением nil, если такового не существует, т.е. список пуст}
{перечисление компонент списка}

procedure Enumeration(List:pList);

var pt:pComponent;

{если ptnil, pt^.value=компонента хранимой последовательности f_i}

begin

pt:=List; { i:=1}

while not (pt<>nil) { i<=длины f} do

begin {Обработка f_i = pt^.value } pt:=pt^.next { i:=i+1} end;

end;
{порождение списка (здесь: из компонент файла f: file of T)}

procedure Generation(var List:pList; var f: FileOfT);

var pt:pComponent;

{если ptnil, pt^.value=компонента хранимой последовательности f_i}

begin

reset(f); List:=nil; { i:=0}

while not eof(f) { i<=длины f} do

begin new(pt); read(f, pt^.value); { pt^.value:= f_i }

pt^.next:=List; List:=pt

end;

end;
Здесь список хранит компоненты исходной последовательности в обратном порядке, что не всегда приемлимо и удобно. Мы обязаны хранить ссылку на начало (первую компоненту) списка, но мы можем хранить ссылки и на другие его компоненты. Такие компоненты назовем активными.

Реализацию операций вставки и исключения из списка - см. "Задачи текстовой обработки"

Реализация стеков и очередей списками.
Применим общее решение проблемы распределения памяти в виде списков к реализации абстрактных линейных типов - поставив значениям стека список с одной, а очереди - с двумя активными компонентами.
type

tComponent=record value:T;next:p:pComponent end;

pComponent=^tComponent;

pStack=pComponent; {ссылка на голову - первую или "верхнюю" компоненту списка}

procedure create(var Stack: pStack); begin Stack:=nil end;
procedure push (var Stack: pStack; x:T);

var p:pComponent;

begin

new(p); p^.value:=x; p^.next:=Stack; Stack:=p

end;
{ стек предполагается непустым }

procedure pop( var Stack: pStack; var x:T);

var p:pComponent;

begin

p:=Stack; x:=Stack^.value; Stack:=Stack^.next; dispose(p); {сборка мусора}

end;
function empty(Stack: pStack): boolean; begin empty:= Stack=nil end;

{Реализация очередей.}
type

tQueue= record Нулевой, Последний: pComponent end;

{указатели на начало и конец очереди}
{предусловие: первый элемент существует}

{для этого при создании добавляем нулевой фиктивный элемент, "фантом"}

procedure Put(var Queue: tQueue; x: T); { Поставить В Очередь }

var p:pComponent;

begin

new(p); p^.next:=nil; p^.value:=x;

with Queue do begin Последний^.next:=p; Последний:=p end;

end;
procedure Create(var Queue: tQueue);

begin

with Queue do

begin

new(нулевой); {нулевой элемент - фиктивный}

нулевой^.next:=nil;

последний:=нулевой

end;end;
function Empty(Queue:t Queue):boolean;

begin with Queue do empty:=нулевой=последний end;

procedure Get(Queue: tQueue; var x: T);{ Вывести Из Очереди }

{предполагается, что очередь не пуста; аналогична pop, но надо не забыть про фантом}

var первый:pComponent;

begin

with Queue do

begin

первый:=нулевой^.next;

x:=первый^.value;

нулевой^.next:= первый^.next;

dispose(первый); {сборка мусора}

end; end;

жүктеу/скачать 418 Kb.

Достарыңызбен бөлісу: