Отримання знань

дистанційна підтримка освіти школярів

• Відгуки

Тут ви можете виконати завдання чи задати питання по змiсту цього уроку.

Михальов Володимир (StarRover) 2013-09-26 14:03:05
// 24.09.2013 р.
// 25.09.2013 р.
Завдання для самостійної роботи
---------------------------------
1. Спробуйте оцінити порядок в двох запропонованих алгоритмах розв'язку задачі про дужки.

Для 1-го способу -- O(n), для другого -- O(n^2).

2. Отримайте працюючі програми будь-якою мовою програмування на основі запропонованих алгоритмів.

// 26.09.2013 р.

Вариант 2 алгоритму

{Bracket}
var
s,rez,stek:string;
i,j,k:longint;
b:boolean;
f1,f2:text;
begin
Assign(f1,'input.txt');
Assign(f2,'output.txt');
Reset(f1);
Rewrite(f2);
Read(f1,s);
b:=true; rez:=''; stek:=''; k:=0; i:=1;
while (i<=Length(s))and b do begin
case s[i] of
'(','{','[':begin
stek:=stek+s[i];
k:=k+1;
end;
')':
if (length(stek)=0)or(stek[length(stek)]<>'(')
then b:=false
else Delete(stek,length(stek),1);
'}':
if (length(stek)=0)or(stek[length(stek)]<>'{')
then b:=false
else Delete(stek,length(stek),1);
']':
if (length(stek)=0)or(stek[length(stek)]<>'[')
then b:=false
else Delete(stek,length(stek),1);

end;
//????? ДЛЯ ЧОГО В АЛГОРИТМІ СУРЖИКОМ ЦЯ СТРІЧКА КОДУ? АДЖЕ НІДЕ НИЖЧЕ
//????? ЦЕ ЗНАЧЕННЯ rez НЕ ВИКОРИСТОВУЄТЬСЯ.
//rez:=rez+s[i];
i:=i+1;
end;
if (length(stek)=0) and b
then begin
rez:=s;
WriteLn(f2,rez);
WriteLn(f2,'Balans duzok e');
end
else begin
rez:='';i:=1;j:=1;
//????? ЧОМУ В АЛГОРИТМІ СУРЖИКОМ i СТРОГО МЕНШЕ k?
//while i while i<=k do begin
rez:=rez+s[j];
if (s[j]='(')or(s[j]='{')or(s[j]='[')
then i:=i+1;
j:=j+1;
end;
WriteLn(f2,rez);
WriteLn(f2,'Balansu duzok nema');
end;
Close(f1);
Close(f2);
end.

Михальов Володимир (StarRover) 2013-09-26 14:25:59
// 26.09.2013 р.
4. Розв'яжіть та здайте на перевірку олімпіадну задачу Bracket.

{Bracket}
var
s,stek:string;
b:boolean;
i:longint;
begin
Read(s);
stek:=''; i:=1; b:=true;
while (i<=length(s)) and b do begin
case s[i] of
'(':
stek:=stek+s[i];
')':
if (stek[length(stek)]<>'(')or(length(stek)=0)
then b:=false
else Delete(stek,length(stek),1);
end;
i:=i+1;
end;
if (length(stek)=0)and b
then WriteLn('True')
else WriteLn('False');
end.

Михальов Володимир (StarRover) 2013-09-27 12:08:18
//27.09.2013 р.
3. Зробіть модифікацію розв'язку на основі однопрохідного алгоритму, моделюючи стек не символьним рядком, а з використанням описаних процедур та функцій роботи зі стеком.

{Bracket}
{Алгоритм реалізовано за допомогою функцій і процедур роботи зі стеком}
const
n=255;
var
s: string;
st: array[1..n+1] of char;
i,p: longint;
r: char;
b:boolean;
procedure StackInit;
begin
for i:=1 to n+1 do st[i]:=' ';
p:=1;
end;
procedure StackPut;
begin
st[p]:=r;
p:=p+1;
end;
procedure StackGet;
begin
r:=st[p-1];
p:=p-1;
end;
function StackUp:boolean;
begin
if p=n+1
then StackUp:=True
else StackUp:=False;
end;
function StackDown:boolean;
begin
if p=1
then StackDown:=True
else StackDown:=False;
end;

begin
Read(s);
StackInit;
b:=True;r:=' ';i:=1;
while (i<=length(s))and b do begin
case s[i] of
'(','{','[':begin
r:=s[i];
StackPut;
end;
')':
if not StackDown
then begin
StackGet;
if not(r='(')
then b:=false;
end
else b:=false;
'}':
if not StackDown
then begin
StackGet;
if not(r='{')
then b:=false;
end
else b:=false;
']':
if not StackDown
then begin
StackGet;
if not(r='[')
then b:=false;
end
else b:=false;
end;
i:=i+1;
end;
if not StackDown
then b:=false;
if b
then WriteLn('True')
else WriteLn('False');
end.

Юрій (searching) 2015-11-07 23:09:39
Var R : String[255];
K, I : Integer;
Begin
Read (R);
K := 0;
For I :=1 To Length (R) Do Begin
Case R[I] Of
'(' : Inc (K);
')' : Dec (K);
End;
If K < 0
Then Break;
End;
Write (K = 0);
End.

Повернутися до уроку

Повернутися до перелiку уроків курсу

В системі: гості - (1); користувачі - (0)