|
Banned
Регистрация: 18.11.2008
Сообщений: 51
Провел на форуме:
664036
Репутация:
68
|
|
Срочно!!!!! Нада решить задачи по Структуре Данных
Кто возьмется писать на Паскале?
Мудреный код мне не нужен)
Все должно быть с комментариями, т.е. разжёвано так, чтобы я потом не ждал вас в аське, чтобы вы мне объясняли.
Кто возьмется, то с ценами пишем в аську) 6218200(можно в офф, приду отвечу)
Деньги вперёд не даю!
koi8 | win | dos | utf-8 | mac
СТРУКТУРЫ ДАННЫХ
ЗАДАЧА 1:
Вводится последовательность, состоящая из N пар символов (ai,bi). Каждая пара определяет порядок предшествования символов,
например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a).
Необходимо определить, является ли введенная последовательность: а) полной, т.е. все использованные для формирования
пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,...,As) в порядке предшествования;
б) противоречивой, т.е. для некоторых символов x,y можно получить одновременно порядок как (x,y) так и (y,x);
РЕШЕНИЕ(написать код, не забывай про комментарии):
Пусть при записи этих N пар встретилось всего K различных символов, которые образуют множество X.
Идея решения задачи состоит в последовательном присвоении каждому символу s из Х номера, который определяет
количество Р(s) элементов, предшествующих ему, с учетом свойства транзитивности (из (с,b) и (b,а) следует (с,а)).
Это осуществляется следующим образом: Первоначально предполагается, что каждому символу не предшествует ни один символ,
т.е. Р(s)=0 для любого s. При просмотре очередной пары (x,y) символу y присваивается большее из значений P(x)+1, P(y).
Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2,
т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров
входной строкивозможно несколько вариантов. Не произошло изменения ни одного из номеров символов. Если при этом номера символов
различны и лежат в пределах от 0 до N-1, то эта нумерация определяет полный порядок. Иначе порядок неполный. Номер некоторого символа
превысил N-1. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.
Легко понять, что число просмотров не превысит N. Вариант 2. Рассмотрим следующий метод: Заведем массивы A: array [1..N,0..N] of byte и
Cnt: array[1..N] of byte; сначала A[i,0]=0 и Cnt[i]=0 для любого i. Пусть среди 2*N символов, образующих N пар, есть ровно K различных.
Перенумеруем их от 1 до K. Будем считать, что пары составлены не из символов, а из соответствующих им номеров. В i-ю строчку матрицы A будем
заносить те элементы, которые являются вторыми элементами в парах с первым элементом i. В A[i,0] будет храниться текущее число этих элементов.
Обработка пары (i,j) будет выглядеть следующим образом: A[i,0]:=A[i,0]+1; {количество увеличилось на 1} A[i,A[i,0]]:=j; {вставляем j на первое свободное место}
В Сnt[i] будет храниться число пар, у которых элемент i является вторым в паре. Если все символы без повторений, использованные для записи пар, можно выписать
в цепочку в порядке предшествования, то у этой цепочки должен быть первый символ s, у которого нет предшествующего и которому соответствует Cnt[s]=0.
Может быть несколько ситуаций: 1. Такой элемент единственный - следовательно, это начало цепочки. Отбрасываем s из цепочки и убираем все пары с первым элементом s
из множества пар, корректируя при этом массив Cnt: for i:=1 to A[0,s] do Сnt[A[s,i]]:=Cnt[A[s,i]]-1; после чего опять ищем элемент s, у которого нет предшествующего
и которому соответствует Cnt[s]=0. 2. Таких элементов несколько, следовательно, между ними нельзя определить порядок предшествования - система неполна. 3. Таких элементов нет - следовательно, система противоречива.
ГРАФЫ
ЗАДАЧА 2:
Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2, ..., An}. Необходимо составить цепочку
максимальной длины по правилу (Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak). При образовании этой цепочки любая пара может быть использована не более одного раза.
РЕШЕНИЕ(написанный в конце программы код с ошибкой. надо найти эту ошибку и исправить её; не забываем про комментарии):
Для более удобного хранения информации заведем матрицу C[1...n,1..n] (так называемую матрицу смежности) в которой
C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе. Будем строить все возможные цепочки (по правилу, данному
в условии) и искать среди них ту, которая имеет максимальную длину. В качестве начального символа цепочки можно взять
любой символ из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы C слева направо элемент C[i,j]=1
(другими словами, ищем пару с первым элементом Ai). Если такого элемента не существует, то берем в качестве начала
строки другой элемент множества A. Если элемент C[i,j]=1 найден, то ему соответствует пара (Ai,Aj). Помечаем ее как
уже использованную полагая, например, C[i,j]=-1. Далее просматриваем слева направо строку j матрицы C в поисках еще не
использованной пары (Aj,Ak) (C[j,k]=1). Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный
элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку Ai Aj Ak ... As Al Ap и в строке p матрицы
больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную
по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем эту строку как рекорд. После этого "отщепляем"
от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с индексом, большим p. Если да, то приписываем
уже этот элемент к строке и пытаемся затем снова увеличить длину полученной строки, если же нет, то "отщепляем" от строки элемент A1,
в строке S ищем единичный элемент с индексом, большим l и т.д. Останов осуществляется тогда, когда мы должны "отщепить" от строки Ai.
Перебираем цепочки, начинающиеся со всех возможных элементов множества A. Находим строку максимальной длины: const M=10; {максимально число элементов в A}
{будем считать, что A состоит из чисел от 1 до N} var c:array[1..M,1..M] of integer; curstr, maxstr: array[0..M] of integer; {в этих переменных хранятся текущая цепочка и}
{цепочка максимальной длины.} {В нулевом элементе хранится длина цепочки} N,E : integer; {N - число элементов в A} i,j,k : integer; {E - число пар в наборе} procedure find;
var l,j : integer; begin l:=curstr[curstr[0]]; {l = последний элемент цепочки} for j:=1 to N do {просмотр строки l} if C[l,j]=1 then begin curstr[0]:=curstr[0]+1; curstr[curstr[0]]:=j; {j -> в цепочку}
c[l,j]:=-1; {пара использована} find; c[l,j]:=1; {пару снова разрешено использовать} curstr[0]:=curstr[0]-1; end; if curstr[0]>maxstr[0] {если нашли более} then maxstr:=curstr {длинную строку} end; begin readln(N); readln(E);
for i:=1 to N do for j:=1 to N do C[i,j]:=0; for k:=1 to E do begin write('очередная пара: ',i,j); c[i,j]:=1 end; for i:=1 to N do begin curr[0]:=1; {поиск цепочки} curr[1]:=i; {начинающейся элементом i} find; end; for i:=1 to maxstr[0] do write(maxstr[i]); {печать максимальной строки} end.
ЗАДАЧА 3:
Найти и удалить (левым удалением) среднюю по значению вершину дерева, у которой высота левого поддерева отличается от высоты правого поддерева на 2. Выполиь прямой (левый) обход полученного дерева.
Для реализации этой задачи можно использовать данное (ниже) построение бинарного дерева, но естественно нужно переделать всё так, как сказано в условии данной задачи:
Uses Graph,crt;
Type PEl = ^El;
El = record
Data : integer;
W, H :integer;
L, R : PEl
end;
var T : PEl;
i, w, h, gd, gm, _global_counter : integer;
hg,wg:string;
x3,y3,kl, kr,d,s,s1:integer;
//----------------------------
Const n=12;
Gl :integer=0;
Procedure AddNode(var P:PEl; n:integer);
begin
if P<> Nil
then if n < P^.Data
then AddNode(P^.L,n)
else if n > P^.Data
then AddNode(P^.R,n)
else writeln('est')
else
begin
New(P); //elsi novoe
P^.Data:=n;
P^.L:=Nil;
P^.R:=Nil
end;
end;
{------------------------------------------------------}
Function MaxHeight(P:PEl):integer; //vysota dereva
var Hl, Hr : integer;
begin
if P=Nil then MaxHeight:=0
else begin
Hl:=MaxHeight(P^.L);
Hr:=MaxHeight(P^.R);
MaxHeight:=Hl+1;
P^.H:=Hl+1;
if Hr > Hl
then begin
MaxHeight:=Hr+1;
P^.H:=Hr+1
end
end;
end;
{------------------------------------------------------}
Function MaxWidth(P:PEl):integer; //shirina dereva
begin
if P=Nil then MaxWidth:=0
else begin
MaxWidth:=1+MaxWidth(P^.L)+MaxWidth(P^.R)
end
end;
Procedure PrintTree(P:PEl;x1,y1,DX:byte);
{$R-}
begin
if P=Nil then begin Exit end
else
begin
PrintTree(P^.r,x1+trunc(dx),y1+2,trunc(dx/2));
{delay(300);} gotoxy(x1,y1+1);
writeln(P^.Data:3);
PrintTree(P^.l,x1-trunc(dx),y1+2,trunc(dx/2));
end
{$R+}
end;
{------------------------------------------------}
Procedure GTree( P:Pel;XL,XR,Y,dy:integer; var x2,y2:integer );
var dat:string; //
s,xn,yn,kl,kr,d:integer;
{$R-}
Begin
if P=nil then begin exit end
else
begin
kl:=maxwidth(p^.l)+1;
kr:=maxwidth(p^.r)+1;
d:=(xr-xl) div (kl+kr);
s:=xl+d*kl;
Str(P^.data,dat);
OutTextXY(s,y,dat);
circle(s,y,15);
if P^.R<>Nil then
begin
GTree(P^.R,s,xr,y+dy,dy,xn,yn);
line(s,y+15,xn,yn-15);
end;
if P^.L<>Nil then
begin
GTree(P^.l,xl,s,y+dy,dy,xn,yn );
line(s,y+15,xn,yn-15);
end;
x2:=s;
y2:=y;
end;
{$R+}
End;
{----------------------------------------------------------}
var lw,rw:integer;
begin
Clrscr;
gd:=Detect;
InitGraph(gd, gm, '');
T:=Nil;
Randomize;
for i:=1 to 30
do
begin
AddNode(T, Random(30)-15);
end;
w:=MaxWidth(T);
h:=MaxHeight(T);
lw:= MaxWidth(t^.L);
Rw:= MaxWidth(t^.R);
//------------------------
PrintTree(t,40,0,16);
gotoxy(0,26);
writeln('vusota ',h);
write('shirina ',w);
SetTextJustify(CenterText, CenterText);
GTree(t,10,Getmaxx -10,30,getmaxy div h ,x3,y3 );
setcolor(yellow);
Str(h,hg);
Str(w,wg);
OutTextXY(getmaxx-100,getmaxy-100,'Vusota '); OutTextXY(getmaxx-50,getmaxy-100,hg);
OutTextXY(getmaxx-100,getmaxy-110,'Shirina ');OutTextXY(getmaxx-50,getmaxy-110,wg);
readkey;
CloseGraph;
end.
!!!ПОВТОРЮСЬ: НЕ ЗАБЫВАЙ ПИСАТЬ КОММЕНТАРИИ!!!
|
Похожие темы
Линейный вид
