История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-11-22 | 303 |
5.00
из
|
Заказать работу |
Заданы две фразы. Определить наибольшую последовательность отличных от пробелов символов, входящую в обе фразы в одном и том же порядке.
Входные данные. В первой строке входного файла INPUT.TXT содержится первая фраза, во второй строке содержится вторая фраза.
Выходные данные. В файл OUTPUT.TXT выводится найденная последовательность символов.
Пример.
INPUT.TXT | OUTPUT.TXT |
ПРИШЛА ВЕСНА РАССТАЯЛ СНЕГ | РЛСН |
Решение
Program F1;
const k=255;
input='input.txt';
output='output.txt';
var x: array [1..k] of integer;
m,n,j: integer;
s1,s2,s: string;
f:text;
label 1;
{функция, которая на основе очередного сочетания
получает следующее по порядку сочетание}
function posl(m:integer):boolean;
var j,f:integer;
label 10,20;
Begin
f:=0;
posl:=true;
for j:=m downto 1 do
if x[j]=n+j-m then f:=j
Else
Begin
inc(x[j]);
goto 10
end;
10: if f<>0 then if f=1 then
Begin
posl:=false;
goto 20
End
else for j:=f to m do x[j]:=x[f-1]+j-f+1;
20:
end;
{процедура вывода результата на экран и записи в файл}
procedure prints(m:integer);
var i:integer;
z:string;
Begin
write(m,': ');
for i:=1 to m do
z:=z+s1[x[i]];
writeln(z);
assign(f,output);
rewrite(f);
write(f,z);
close(f);
readln;
end;
{функция spc удаляет из переданной в неё строки пробелы.}
function spc(s:string):string;
var str:string;
i:integer;
Begin
str:='';
for i:=1 to length(s) do
if s[i]<>' ' then str:=str+s[i];
spc:=str;
end;
{функция equal проверяет, входит ли очередная последовательность,
составленная из символов одной строки в другую}
function equal(m:integer):boolean;
var i,j:integer;
Begin
j:=1;
for i:=1 to length(s2) do
if (s1[x[j]]=s2[i]) and (j<=m) then j:=j+1;
if j>m then equal:=true else equal:=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 begin s:=s1; s1:=s2; s2:=s end;
n:=length(s1);
for m:=n downto 1 do
Begin
for j:=1 to m do x[j]:=j;
Repeat
if equal(m) then
Begin
prints(m);
goto 1;
end;
until not posl(m);
end;
1:
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;
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<103).
Формат входных данных:
Исходный файл содержит одно число N.
Формат выходных данных:
В выходной файл вывести факториал заданного числа
Пример:
INPUT.TXT | OUTPUT.TXT |
program Factorial;
type tlargenumber= record
number: array [1..3000] of byte;
power:word;
end;
var fact:tlargenumber;
n:word;
i:word;
f:text;
procedure product(n:word);
var temp:tlargenumber;
i,p:word;
procedure add(n:word;power:word);
var t,s,d,e:byte;
first:word;
Begin
t:=n div 1000;
s:=(n mod 1000) div 100;
d:=(n mod 100) div 10;
e:=n mod 10;
first:=1+power;
inc(temp.number[first],e);
inc(temp.number[first+1],d+(temp.number[first] div 10));
temp.number[first]:=temp.number[first] mod 10;
inc(temp.number[first+2],s+(temp.number[first+1] div 10));
temp.number[first+1]:=temp.number[first+1] mod 10;
inc(temp.number[first+3],t+(temp.number[first+2] div 10));
temp.number[first+2]:=temp.number[first+2] mod 10;
inc(temp.number[first+4],temp.number[first+3] div 10);
temp.number[first+3]:=temp.number[first+3] mod 10;
end;
Begin
for i:=1 to 3000 do temp.number[i]:=0;
temp.power:=0;
p:=fact.power;
for i:=0 to p do
add(fact.number[i+1]*n,i);
if temp.number[p+4]<>0 then temp.power:=p+4
Else
if temp.number[p+3]<>0 then temp.power:=p+3
Else
if temp.number[p+2]<>0 then temp.power:=p+2
Else
if temp.number[p+1]<>0 then temp.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;
for i:=2 to n do
Begin
product(i);
end;
assign(f,'out.txt');
rewrite(f);
for i:=fact.power downto 1 do write(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 |
Решение
Program triangle;
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);
if xAB/xBC <> yAB/yBC then writeln(f2,'exist')
else writeln(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);
readln(Fd, N);
for i:=1 to N do
begin
readln(Fd, x[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if x[i]>x[j] then
begin
y:=x[i];
x[i]:=x[j];
x[j]:=y;
end;
for i:=1 to n do
writeln (Fs, i:2,’.’+x[i]);
end.
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!