Тема: Элементы лексического и синтаксического разбора

Заданы две фразы. Определить наибольшую последовательность отличных от пробелов символов, входящую в обе фразы в одном и том же порядке.

Входные данные.В первой строке входного файла INPUT.TXT содержится первая фраза, во второй строке содержится вторая фраза.

Выходные данные.В файл OUTPUT.TXT выводится найденная последовательность символов.

Пример.

INPUT.TXT	OUTPUT.TXT
ПРИШЛА ВЕСНА РАССТАЯЛ СНЕГ	РЛСН

Решение

Program F1;

constk=255;

input='input.txt';

output='output.txt';

varx: array[1..k] ofinteger;

m,n,j: integer;

s1,s2,s: string;

f:text;

label1;

{функция, которая на основе очередного сочетания

получает следующее по порядку сочетание}

functionposl(m:integer):boolean;

varj,f:integer;

label10,20;

Begin

f:=0;

posl:=true;

forj:=m downto1 do

ifx[j]=n+j-m thenf:=j

Else

Begin

inc(x[j]);

goto10

end;

10: iff<>0 then iff=1 then

Begin

posl:=false;

goto20

End

else forj:=f tom dox[j]:=x[f-1]+j-f+1;

20:

end;

{процедура вывода результата на экран и записи в файл}

procedureprints(m:integer);

vari:integer;

z:string;

Begin

write(m,': ');

fori:=1 tom do

z:=z+s1[x[i]];

writeln(z);

assign(f,output);

rewrite(f);

write(f,z);

close(f);

readln;

end;

{функция spc удаляет из переданной в неё строки пробелы.}

functionspc(s:string):string;

varstr:string;

i:integer;

Begin

str:='';

fori:=1 tolength(s) do

ifs[i]<>' ' thenstr:=str+s[i];

spc:=str;

end;

{функция equal проверяет, входит ли очередная последовательность,

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

functionequal(m:integer):boolean;

vari,j:integer;

Begin

j:=1;

fori:=1 tolength(s2) do

if(s1[x[j]]=s2[i])and(j<=m) thenj:=j+1;

ifj>m thenequal:=true elseequal:=false;

end;

{тело программы}

Begin

assign(f,input);

reset(f);

readln(f,s1);

read(f,s2);

close(f);

s1:=spc(s1); s2:=spc(s2);

if(length(s2)<length(s1)) then begins:=s1; s1:=s2; s2:=s end;

n:=length(s1);

form:=n downto1 do

Begin

forj:=1 tom dox[j]:=j;

Repeat

ifequal(m) then

Begin

prints(m);

goto1;

end;

until notposl(m);

end;

end.

В этой программе процедура prints печатает найденную последовательность символов и её длину, функция equal проверяет, входит ли очередная последовательность, составленная из символов одной строки в другую, функция spc удаляет из переданной в неё строки пробелы.
Работу полученной программы можно значительно ускорить, если добавить в неё часть, в которой перед началом перебора из обеих строк удалялись бы те символы, которые встречаются только в одной из них. (Например, заданные в условии строки после такого преобразования приняли бы вид: РЛАЕСНА и РАСАЛСНЕ).

Тема: Эффективные структуры данных

Условие задачи: В арифметическом выражении разрешается использовать только число 1, действия сложения и умножения и скобки. Какое минимальное количество единиц необходимо использовать, чтобы получить заданное натуральное число N (1≤ N ≤ 5000)?

INPUT. TXT		Значение N
OUTPUT.TXT		Минимальное количество единиц

Комментарии: Для решения данной задачи применяем методы «динамических структур», т.е. для того, чтобы найти ответ для N, сначала необходимо найти наименьшее количество единиц для значений 1..N-1. Рассмотрим соответствующие выражения для нескольких начальных значений N:

Значение N	Наименьшее количество 1	Арифметическое выражение

		1+1
		1+1+1
		(1+1)*(1+1)
		1+ (1+1)*(1+1)
		(1+1)*(1+1+1)
		1+(1+1)*(1+1+1)

Динамическая структура строится следующим образом:

для N=1 количество единиц будет x[1]=1;

каждое следующее x[N] будет наименьшим из двух величин:

a=x[N-1]+1;

b=min(x[i] + x[N div i]).

Самого арифметического выражения программа не выдает, только минимальное количество единиц.

Решение:

Program olimp2;

сonst

_N=5000;

var

N: integer;

x: array[1.._N] of byte;

fD, fs: Text;

procedure init;

begin

assign(fD, ‘D:\input.txt’);

reset(fD);

readln(fD, N);

close(fD);

end;

procedure Run;

var i, a, b, m: word;

begin

Fillchar(x, Sizeof(x), 0);

x[1]:=1;

for M:=2 to N do

begin

a:=N;

for i:=1 to M div 2 do

if x[i] +x[M-i]< a then a:=x[i]+x[M-i];

b:=N;

for i:=2 to M div 2 do

if (M mod i=0) and (x[i]+x[M div i]<b) then b:=x[i]+x[M div i];

if a<b then x[M]:=a else x[M]:=b;

end;

procedure Done;

begin

assign (fs, ‘D:\output.txt’);

rewrite(fs);

write(fs, x[N]);

close(fs);

end;

begin

init;

run;

done

end.

Тема:Работа с большими числами

Условие задачи: Гарри Поттер на досуге занимается исследованием свойств чисел. Однажды ему захотелось узнать факториал числа 100. Напишите программу, помогающую Гарри решить эту проблему для любого N (0<N<10³).

Формат входных данных:

Исходный файл содержит одно число N.

Формат выходных данных:

В выходной файл вывести факториал заданного числа

Пример:

INPUT.TXT	OUTPUT.TXT

programFactorial;

typetlargenumber=record

number:array[1..3000]ofbyte;

power:word;

end;

varfact:tlargenumber;

n:word;

i:word;

f:text;

procedureproduct(n:word);

vartemp:tlargenumber;

i,p:word;

procedureadd(n:word;power:word);

vart,s,d,e:byte;

first:word;

Begin

t:=n div1000;

s:=(n mod1000)div100;

d:=(n mod100)div10;

e:=n mod10;

first:=1+power;

inc(temp.number[first],e);

inc(temp.number[first+1],d+(temp.number[first]div10));

temp.number[first]:=temp.number[first]mod10;

inc(temp.number[first+2],s+(temp.number[first+1]div10));

temp.number[first+1]:=temp.number[first+1]mod10;

inc(temp.number[first+3],t+(temp.number[first+2]div10));

temp.number[first+2]:=temp.number[first+2]mod10;

inc(temp.number[first+4],temp.number[first+3]div10);

temp.number[first+3]:=temp.number[first+3]mod10;

end;

Begin

fori:=1 to3000 dotemp.number[i]:=0;

temp.power:=0;

p:=fact.power;

fori:=0 top do

add(fact.number[i+1]*n,i);

iftemp.number[p+4]<>0 thentemp.power:=p+4

Else

iftemp.number[p+3]<>0 thentemp.power:=p+3

Else

iftemp.number[p+2]<>0 thentemp.power:=p+2

Else

iftemp.number[p+1]<>0 thentemp.power:=p+1

Else

temp.power:=p;

fact:=temp;

end;

Begin

assign(f,'in.txt');

reset(f);

read(f,n);

close(f);

fact.number[1]:=1;

fact.power:=1;

fori:=2 ton do

Begin

product(i);

end;

assign(f,'out.txt');

rewrite(f);

fori:=fact.power downto1 dowrite(f,fact.number[i]);

close(f);

end.

Задача «Треугольник»

Input file: input.txt

Output file: output.txt

В файле in.txt даны координаты трех вершин A,B и С на трех строках соответственно. Координаты в файле разделены пробелом.

Необходимо определить существует ли треугольник АВС с указанными координатами вершин. Если существует, то вывести в файл out.txt слово «exist», иначе – «do not exist».

INPUT.TXT	OUTPUT.TXT
1 3 5 7 8 9	exist

Решение

Programtriangle;

Var

i,xa,xb,xc,ya,yb,yc,xAB,xBC,yAB,yBC: integer;

AB,BC: real;

f1,f2: text;

Begin

assign(f1,'input.txt');

assign(f2,'output.txt');

reset(f1);

read(f1,xa,ya);

readln(f1);

read(f1,xb,yb);

readln(f1);

read(f1,xc,yc);

readln(f1);

close(f1);

xAB:=xb-xa;

yAB:=yb-ya;

xBC:=xc-xb;

yBC:=yc-yb;

rewrite(f2);

ifxAB/xBC <> yAB/yBC thenwriteln(f2,'exist')

elsewriteln(f2,'do not exist');

close(f2);

end.

Тема: Эффективные структуры данных.

Условие задачи: В преддверии начала 13-го чемпионата страны по футболу в 1-й лиге организаторы решили провести жеребьевку календаря. Секретарь федерации предоставил списки команд с учетом занятых мест в 12-м чемпионате, но для того, чтобы жеребьевка прошла непредвзято и корректно необходимы списки команд по алфавиту, независимо от их достижений в прошлом году. Составить программу, преобразующую турнирную таблицу 12-го чемпионата, состоящую из N команд, в алфавитный список.

INPUT. TXT	Реал Барселона Атлетико Депортиво Сельта Севилья Гранада Валенсия	Количество команд (N) Названия команд
OUTPUT.TXT	Атлетико Барселона Валенсия Гранада Депортиво Реал Севилья Сельта

Решение:

Program olimp1;

var

x: array[1..32] of string;

y: string;

i, j, n: integer;

Fd, Fs: Text;

begin

assign(Fd, ‘D:\input.txt’);

reset(Fd);

assign(Fs, ‘D:\output.txt’);

rewrite(Fs);