» Главная
eXcode.ru » Статьи » Задачи » С решениями
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 4





Анализ программы




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

Входные данные состоят из N строк (1 <= N <= 10000), полученных в результате синтаксического анализа исходного текста программы. Каждая строка этого файла соответствует одному оператору исходного текста и содержит следующие данные:

NEXT - после оператора, соответствующего этой строке, может быть выполнен лишь следующий по порядку оператор;

JUMP номер - после оператора, соответствующего этой строке, может быть выполнен лишь оператор с указанным номером (нумерация операторов начинается с единицы);

JUMP номер1 OR номер2 -после оператора, соответствующего этой строке, может быть выполнен один из двух операторов, номера которых указаны.

Номера операторов отделены от служебных слов одним или несколькими пробелами. Известно, что программа всегда начинает выполняться с оператора с номером 1.

Выходные данные состоят из нескольких строк. Первая строка содержит число невыполняемых операторов, каждая из последующих строк - их номера, расположенные в порядке возрастания.

Пример входных данных

NEXT
JUMP 4 OR 6
NEXT
JUMP 3
NEXT
JUMP 8
NEXT
NEXT

Пример выходных данных

2
5
7

Мое решение на Delphi


program Project1;

{$APPTYPE CONSOLE}
uses SysUtils;

var a: array[1..10001,1..2] of integer;
s,st: string;
i,ii,i2,i3,count: integer;

procedure eraser(t : integer);
var x,y:integer;
begin
if a[t,1]=0 then exit;
if t>i-1 then exit;
if a[t,1]=-1 then begin a[t,1]:=0; eraser(t+1); end else
if a[t,2]=0 then begin x:=a[t,1]; a[t,1]:=0; eraser(x); end
else begin
x:=a[t,1]; a[t,1]:=0; eraser(x);
y:=a[t,2]; a[t,2]:=0; eraser(y); end;
end;

begin
i:=1;
while not SeekEof do begin
readln(s);
if (s[1]=′N′) then a[i,1]:=-1;
if (s[1]=′J′) then begin
for ii:=3 to length(s) do begin
if ((s[ii]=′ ′)or (s[ii]=#10)) and (st<>′′) then break;
if (s[ii]=′0′) or (s[ii]=′1′) or (s[ii]=′2′) or (s[ii]=′3′) or (s[ii]=′4′) or (s[ii]=′5′) or (s[ii]=′6′) or (s[ii]=′7′) or (s[ii]=′8′) or (s[ii]=′9′) then st:=st+s[ii];
end;
a[i,1]:=strtoint(st);
st:=′′;
for i2:=ii-1 to length(s) do begin
if (s[i2]=′R′) then begin
for i3:=i2 to length(s) do begin
if ((s[i3]=′ ′) or (s[i3]=#10)) and (st<>′′) then break;
if (s[i3]=′0′) or (s[i3]=′1′) or (s[i3]=′2′) or (s[i3]=′3′) or (s[i3]=′4′) or (s[i3]=′5′) or (s[i3]=′6′) or (s[i3]=′7′) or (s[i3]=′8′) or (s[i3]=′9′) then st:=st+s[i3];
end;
a[i,2] := strtoint(st);
st:=′′;
break;
end;
end;
end; //jump
inc(i);
end; // seekeof
eraser(1);
count := 0;
for i2:=1 to i do begin
if a[i2,1]<>0 then inc(count);
end;
writeln(count);
if count>0 then
for i2:=1 to i do begin
if a[i2,1]<>0 then writeln(i2);
end;
end.
К началу статьи





Добавил: LedWormДата публикации: 2005-09-24 19:47:04
Рейтинг статьи:3.00 [Голосов 5]Кол-во просмотров: 6969

Комментарии читателей

Всего комментариев: 3

2005-12-13 16:45:05
romodos
Темная задачка, ничё не скажешь

2005-12-04 11:44:11
LedWorm
Евгений, конечно же твои замечания верны. Но нужно отметить, что эту задачу я писал на время, и написал я ее примерно минут за 30, поэтому времени переписывать тот же strtoint не было. А переписывать потом как то не хотелось. Задача решена, цель достигнута.

З.Ы. Твой код действитьльно работает быстрее.

2005-12-02 17:29:31
Eugene
Гутен Таг! Прочитал решение задачи “Анализ программы“, выполненное LedWorm(ом), и в голову постучались некоторые думы об улучшении этого алгоритма. Ну, во-первых, можно сократить жрачку памяти исполняемой программой за счет неподключения модуля SysUtils, так как, если я внимательно просканировал код, из него просится только одна функция strtoint(...), которую эргономичнее написать вручную. Также, неэргономично использовать подобный двумерный массив, а лучше сформировать структурный его аналог. Ну, и ,возможно, гибкости решению добавило бы динамическое распределение памяти под этот злополучный массив. Все это заставило бы программу есть примерно в 2 раза меньше памяти, чем оно происходит в этом коде.
Во-вторых, если позволите, приведу свой анолог куска программы, где происходит расщепление адресов операторов. Думаю, что он выполняется быстрее:

procedure sozdanie(i:word);
var j:byte;e:string[8];
begin with a[i] do begin r:=false;
if s[1]=′N′ then woh1:=i+1 else if not(pos(′R′,s)=0) then begin j:=6;e:=′′;
while s[j]<>′O′ do begin if s[j] in chisla then e:=e+s[j];inc(j);end;
woh1:=strtoint(e);j:=length(s);while s[j]<>′R′ do dec(j);
woh2:=strtoint(copy(s,j+1,length(s)-j));end else
woh1:=strtoint(copy(s,5,length(s)-5+1));end;end;

a[...].woh1,a[...].woh2-поля, хранящие адреса операторов. За сим прощаюсь!Вон из Москвы - сюда я больше не ездок!

Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Как вы относитесь к AJAX?
Считаю это ЗЛОМ
11% (12)
Бесполезная технология
2% (2)
Мне параллельно
9% (10)
Неплохая технология
20% (23)
Рулез, как я без нее жил!
7% (8)
Я разработчик AJAX-приложений
5% (6)
А что? Хороший футбольный клуб!
12% (14)
Я в танке!!!
34% (38)

Проголосовало: 113
- Исправил ли ты ошибку в программе?
- В разумных пределах...
Рейтинг: 4.2/10 (4)
Посмотреть все анекдоты