3. Из данного списка спортсменов распечатать сведения о тех из них, кто занимается плаванием. Указать того, кто занимается спортом дольше всех.
program lab10;
type k=record
name:string;
vid_sporta:string;
god:integer;
end;
var f:file of k;
i,l,x:integer;
min:real;
n:string;
a:k;
begin
assign(f,'sport');
rewrite(f);
writeln('Vvedite 4islo sportsmenov');
readln(x);
for i:=1 to x do
begin
writeln('imya');
readln(a.name);
writeln('vid_sporta');
readln(a.vid_sporta);
writeln('skolko let zanimaetsya');
readln(a.god);
write(f,a);
end;
close(f);
reset(f);
writeln('name | vid_sporta | zanimaetsya(let)');
writeln('________________________________________');
while not (eof(f)) do
begin
read(f,a);
writeln(a.name:10,' ',a.vid_sporta:13, ' ', a.god:3);
end;
close(f);
l:=0;
reset(f);
writeln('zanimaetsya plavaniem:');
while not (eof(f)) do
begin
read(f,a);
if a.vid_sporta='plavanie' then
begin
writeln(a.name);
l:=l+1;
end;
end;
if (l=0) then writeln('Nikto');
close(f);
reset(f);
l:=0;
while not (eof(f)) do
begin
read(f,a);
if a.god>l then
begin
l:=a.god;
n:=a.name;
end;
end;
writeln('zanimaetsya sportom dolshe vseh:');
writeln(n,' ',l, ' let');
close(f);
readln;
end.
Билет №35
1. Проблема разрешимости (разрешения) для класса однотипных задач. Проблема разрешимости в алгебре высказываний и способы их разрешения.
I часть.Рассмотрим множество каких-нибудь однотипных задач, например задачи на решение системы m линейных уравнений с n неизвестными, где m, n - произвольные натуральные числа. Для этой серии задач можно поставить следующий вопрос: Существует ли метод, по которому решаются все задачи данной серии? Причем этот метод должен быть одинаковым для любой задачи серии. Поставленная задача носит название проблемы разрешения.
Например, для системы m уравнений с n неизвестными существует несколько способов решения: метод Гаусса, метод Крамера. Значит, для системы m линейных уравнений с n неизвестными проблема разрешения разрешима.
Если для серии М однотипных задач единый метод решения (алгоритм) существует, то говорят, что для этой серии М проблема разрешения решена и разрешима.
Если же доказано, что единого метода решения задач из серии М не существует, то говорят, что для данной серии задач проблема разрешения решена и неразрешима.
Если для серии М однотипных задач единый метод решения не найден, и не доказано, что такого метода не существует, то говорят, что для данной серии М задач проблема разрешения не решена (открыта).
Если проблема разрешения для некоторой серии задач неразрешима, то каждую задачу данной серии приходится решать отдельно или, в лучшем случае, разбивать класс задач на несколько подклассов.
Точное определение проблемы разрешения можно будет дать только после строгого математического определения понятия алгоритм. Такое определение существует, оно появилось в 30-ых годах XX-ого века.
Наличие строгого определения алгоритма сделало возможным доказательство неразрешимости задач, т.к. стало понятно, отсутствие чего нужно доказывать. До этого в математике существовал только один путь разрешения любой задачи - нахождение способа ее решения, и если способ не был найден, то считалось, что знаний недостаточно для решения такой трудной задачи. Никто не задумывался над тем, что решения вовсе может и не быть и, следовательно, его никогда, никем найти не удастся.
Появление новой отрасли в математике - математической логики и теории алгоритмов сделало возможным решать такие задачи, т. е. доказывать, что они не разрешимы в рамках данной аксиоматической теории.
II часть. Проблема разрешения состоит в том, чтобы дать способ, позволяющий для каждой формулы алгебры высказываний конечным числом действий выяснить, является ли она тождественно истинной или нет. Имея такой способ, мы можем определить, является ли формула φ выполнимой или нет.
В самом деле, если ¬φ тождественно истинная формула, то φ тождественно ложная, т. е. невыполнима.
Если же ¬φ не тождественно истинная формула, то φ - выполнима.
Известно, что проблема разрешения для алгебры высказываний разрешима. Существуют два способа ее разрешения:
Поскольку формулы алгебры высказываний конечнозначны, то их можно проверить по таблице, составленной для каждой формулы отдельно. Правда это может быть очень долгим занятием, ведь если формула содержит n элементарных высказываний, то нужно определить значения функции для 2n наборов.
Приводим формулу алгебры высказываний к конъюнктивному нормальному виду. Если каждая элементарная дизъюнкция К.Н.Ф. содержит пару, состоящую из какого-нибудь высказывания и его отрицания, то эта формула тождественно истинна. Если нет - то не тождественно истинна.
Алгоритм проблемы выполнимости:
Берем формулу ¬φ.
Приводим ¬φ к К.Н.Ф. и узнаем, является ли ¬φ тождественно истинной или нет.
Если формула ¬φ тождественно истинна, то φ невыполнима, если же ¬φ не тождественно истинна, то φ выполнима.
