Разработка системы задач (алгоритмы-программы) по дискретной математике
procedure Init(z:string); {инициализация входных данных}
Var i,j:integer;
f:text;
begin
Assign(f,z);
Reset(f);
ReadLn(f,m);
For i:=1 to m do
begin
For j:=1 to m do
Read(f,A[i,j]);
ReadLn(f);
end;
Close(f);
end;
function MinZn(R:mn):integer; {вычисляет номер района, путь до которого из района отправления минимален}
var i,minn:integer;
Begin
minn:=MaxInt;
For i:=1 to m do
If (D[i]
begin
MinZn:=i;
minn:=D[i];
end;
End;
Function Min(i,j:integer):integer;{возвращает минимальное значение из двух возможных}
Begin
If i<>0 then
begin
If j<>0 then
begin
If j
end Else Min:=i;
end Else Min:=j;
End;
procedure Milicia(s:integer);
var v,u:integer;
T:mn;
Begin
for v:=1 to m do D[v]:=A[s,v];
D[s]:=0; T:=[1..m]-[s];
While T<>[] do
Begin
u:=MinZn(T);
T:=T-[u];
For v:=1 to m do
If v in T then
If A[u,v]<>0 Then
D[v]:=Min(D[v],D[u]+A[u,v]);
end;
End;
Begin
clrscr;
Init('A:milicia.txt');
WriteLn('Введите пункт отправления и пункт назначения');
ReadLn(first,last);
Milicia(first);
WriteLn(D[last]);
readkey;
End.
4 Задача о футболистах.
uses crt;
Const k=100;
Type mas=array[1..k]of Integer;
Var m,q:integer;
A,B:mas;
procedure Init(z:string); {инициализация исходных данных}
var i:integer;
f:text;
begin
Assign(f,z);
Reset(f);
ReadLn(f,m,q);
For i:=1 to m do
Read(f,A[i]);
ReadLn(f);
For i:=1 to q do
Read(f,B[i]);
Close(f);
end;
procedure Solve;
var i,j,t:integer;
D:mas;
begin
i:=1; j:=1; t:=1;
While (i<=m)and(j<=q)do {пока не вышли футболисты хотя бы из одного автобуса}
Begin
{сравниваем номера футболистов в разных автобусах, выходит в строй футболист с наименьшим номером}
If A[i]<=B[j] Then begin D[t]:=A[i]; Inc(i); end
Else begin D[t]:=B[j]; Inc(j); end;
Inc(t);
end;
{из одного автобуса вышли все футболисты, осталось выйти остальным}
While i<=m do begin D[t]:=A[i]; Inc(i); Inc(t); end;
While j<=q do begin D[t]:=B[j]; Inc(j); Inc(t); end;
For i:=1 to t-1 do Write(D[i],' ');
end;
begin
clrscr;
Init('A:socker.txt');
Solve;
readkey;
end.
5 Задача о семьях.
Uses crt;
Const MaxN=1000;
Var A:array[1..maxN]of byte;
N, cnt,i,j:integer;
Procedure Swap(var a,b:byte);
Var c:byte;
Begin
c:=a; a:=b; b:=c;
End;
Begin
Write(‘введите N’); readln(N);
Write(‘введите массив через пробел(0 – Петров, 1 - Иванов)’);
For i:=1 to N do read(A[i]);
i:=1; j:=N; cnt:=0;
While i
If A[i]=1 then Inc(i) else
If A[j]=0 then Dec(j) else begin
Swap(A[i],A[j]);
Inc(i); dec(j);
Inc(cnt);
End;
writeLn(‘Число
обменов
- ’, cnt);
End.
6
Метро.
uses crt;
const p=100;
Type mas=array[1..p,1..p]of 0..1;
var k,n:integer;
A:mas;
procedure Init(z:string);
{инициализация
данных}
var f:text;
i,j:integer;
begin
Assign(f,z);
Reset(f);
ReadLn(f,n);
For i:=1 to n do
begin
For j:=1 to n do
Read(f,A[i,j]);
ReadLn(f);
end;
Close(f);
end;
procedure
Get(i:integer);
{i
– номер станции,
из которой
необходимо
отправится}
var S,T:Set of 1..p;
j,l:integer;
begin
T:=[i];
Repeat
S:=T;
For l:=1 to n do
If l in S then {по строкам
матрицы смежности
А, принадлежащим
множеству S}
For j:=1 to n do
If
A[l,j]=1
Then
T:=T+[j];
{смотрим если
есть путь из
данного пункта
в пункт j,
то добавляем
номер пункта
j в
множество Т}
Until S=T;
For j:=1 to n do
If (j in T)and(i<>j) then Write(j,' ');
{просматриваем
содержится
ли номер пункта
j в
множестве
имеющих путь
из пункта i}
end;
begin
clrscr;
Init('A:metro.txt');
readLn(k);
Get(k);
readkey;
end.
7
Роботы.
Program
Robots;
Const max=50;
Type Sset=Set of 1..max;
Mas=array[1..max]of Sset;
Var
A,B:Mas;
{A
– матрица
достижимостей,
B[i]
– какие роботы
могут быть в
i
пункте}
SOne,
STwo:
SSet;
{SOne
– роботы, которые
едут со скоростью
1, STwo
– роботы, которые
едут со скоростью
2}
N,
M:integer;
{N
– число пунктов,
M –
число роботов}
Procedure
Init;
{инициализация
входных данных}
Var K, i, FrP, ToP:integer;
Begin
FillChar(A,SizeOf(A),0);
Write(‘Число
пунктов:’);
ReadLn(N);
Write(‘Число
дорог:’);
ReadLn(K);
For i:=1 to K do begin
writeLn(‘Введите
пункты, которые
соединяет
дорога №’, i);
ReadLn(FrP, ToP);
Include(A[FrP],ToP);
Include(A[ToP],FrP);
End;
Write(‘Число
роботов:’);
ReadLn(M);
For i:=1 to M do Begin
Write(‘Пункт,
где находится
робот №’,i,’:’);
ReadLn(K);
Include(B[k],i);
Write(‘скорость
робота
№’,i,’:’);
ReadLn(k);
If K=1 then Include(SOne,i) Else Include(STwo,i);
End;
End;
Function ProvCanMet: Boolean;
Var i:integer;
Begin
i:=1;
While (i<=N)and(B[i]<>[1..M])do Inc(i);
ProvCanMet:=i<=N;
End;
Function InTwoNear: Boolean;
Var i,j:integer;
Begin
i:=1; j:=N+1;
while (i
j:=i+1;
while(j<=N)and Not((j in
A[i])and(B[i]+B[j]=[1..M]))do Inc(j);
Inc(i);
End;
InTwoNear:=j<=N;
End;
Function AddIfCan(mode:integer; S:Sset):Boolean;
Var i,j:integer;
C:mas;
Begin
AddIfCan:=false;
{S
– множество
роботов, которые
едут}
If mode=0 then
For i:=1 to N do C[i]:=B[i]-S
Else C:=B;
For i:=1 to N do
For j:=1 to N do
If (i<>j)and(j in A[i])and(C[i]*B[j]*S<>B[j]*S)
Then Begin
AddIfCan:=true;
C[i]:=C[i]+B[j]*S;
End;
B:=C;
End;
Function InTwoForC: byte;
Var i,j:integer;
Begin
i:=1; j:=N+1;
while (i
j:=i+1; While
(j<=N)and (not(j in A[i])or(B[i]+B[j]<>[1..m])or
Not((SOne=[])or(STwo=[])or((B[i]*SOne=SOne)and(B[j]*STwo=STwo))or
(B[j]*SOne=SOne)and(B[i]*STwo=STwo)))do Inc(j);
Inc(i);
End;
If j>N Then InTwoForC:=0 Else
If STwo=[] Then InTwoForC:=1 Else
If SOne=[] Then InTwoForC:=2 Else
InTwoForC:=3;
End;
Procedure SolveC;
Var time:integer;
FindS, IncS: Boolean;
ForMet: integer;
Begin
Time:=0;
IncS:=true;
ForMet:=InTwoForC;
FindS:=ProvCanMet;
While IncS and Not FindS and(time<=N*2)and(ForMet=0)do
begin
Inc(time);
If Time Mod 2=0 then IncS:=AddIfCan(0,[1..m])
Else incS:=AddIfCan(0,STwo);
ForMet:=InTwoForC;
FindS:=ProvCanMet and(time mod 2=1);
End;
If Time>N*2 then WriteLn(‘Пункт
В:
Роботы
не
встретятся’)
Else begin
Write(‘Пункт
В: Роботы встретятся
через’);
If FindS Then Write(Time/2:0:3)
Else Case ForMet of
1: write((time+1)/2:0:3);
2: write(time/2+1/4:0:3);
3: write(time/2:0:3,’+1/’,(time mod 2+1)*3);
End;
WriteLn(‘Момент(а,ов)
времени’);
End;
End;
Procedure SolveAB;
Var time:integer;
ForB, FindS, IncS: Boolean;
Old:mas;
Begin
Old:=B;
Time:=0;
IncS:=true; FindS:=ProvCanMet;
While IncS and Not FindS do begin
ForB:=InTwoNear;
Inc(time);
incS:=AddIfCan(1,[1..m]);
FindS:=ProvCanMet;
End;
If FindS Then begin
WriteLn(‘Пункт
А:’,time,’момент(а,ов)
времени’);
WriteLn(‘Пункт
Б:’,time
– Byte(ForB)*0.5:0:1,’момент(а,ов)
времени’);
SolveC;
End
Else begin
WriteLn(‘Пункт
А: Роботы не
встретятся’);
writeLn(‘Пункт
Б: Роботы не
встретятся’);
writeLn(‘Пункт
В: Роботы не
встретятся’);
end;
B:=Old;
End;
Begin
Init;
SolveAB;
End.
8
Вожатый в лагере.
uses crt;
Const k=50;
Type mas=array[1..k]of integer;
var col:integer;
A:mas; {массив
представляющий
собой список
возрастов
детей}
procedure Init(z:string);
{инициализация
данных}
var i:integer;
f:text;
begin
Assign(f,z);
Reset(f);
i:=0;
While not EoLn(f) do
begin
Inc(i);
Read(f,A[i]);
end;
col:=i;
Close(f);
end;
procedure Print; {вывод
списка
на
экран}
var i:integer;
begin
For i:=1 to col do
Write(A[i],' ');
end;
procedure Solve(m,t:integer);
var i,j,w,x:integer;
begin
If m>=t then exit;
i:=m;
j:=t;
x:=A[(m+t)div
2]; {x-
барьерный
элемент, т.е.
возраст, относительно
которого будет
сортироваться
список, i,j
– нижний и верхний
номер, рассматриваемой
части списка}
While i
If
A[i]>x
then
Inc(i)else
{смотрим элементы
списка относительно
If
A[j]
Begin левой
части по элементу,
которые стоят
не на
w:=A[i]; A[i]:=A[j]; A[j]:=w;
своем
месте.
Меняем
их местами}
end;
Solve(m,j-1);
Solve(i+1,t);
{ищем далее
барьерный
элемент, сначала
в правой
end; части списка,
затем в левой}
begin
clrscr;
Init('A:alfa.txt');
Print;
WriteLn;
Solve(1,col);
Print;
readkey;
end.
9
Егерь.
Program Eger;
uses crt;
Const n=4;
var
A,P,D:array[1..n,1..n]of
Integer;
{A
– матрица смежности;
D –
массив кратчайших
путей, где D[i,j]
– минимальное
время, которое
потребуется,
чтобы добраться
из станции i
до станции j;
P –
массив, элементами
которого являются
номера станций,
которые будут
составлять
путь с минимальным
временем}
k,m:integer; {начальная
и конечная
станции движения}
procedure Init(z:string);
{инициализация
данных}
var i,j:integer;
f:text;
begin
Assign(f,z);
Reset(f);
For i:=1 to n do
begin
For j:=1 to n do
Read(f,A[i,j]);
ReadLn(f);
end;
Close(f);
end;
Procedure Solve;
var i,j,k:integer;
begin
For i:=1 to n do
For j:=1 to n do
begin
D[i,j]:=A[i,j];
P[i,j]:=i;
end;
for k:=1 to n do begin
for i:=1 to n do
for j:=1 to n do
If
D[i,j]>D[i,k]+D[k,j]
then
begin
{определение
пути с минимальным
D[i,j]:=D[i,k]+D[k,j];
временем}
P[i,j]:=k; {заносим
номер станции,
которая будет
end;
предпоследней,
посещенной
напарником}
end;
end;
procedure Way(i,j:integer);
{рекурсивная
процедура,
выводит
begin
последовательность
станций, которые
посетит
If
P[i,j]<>i
then
begin
напарник,
отталкиваясь
от данных,
Way(i,P[i,j]); занесенных
в массив P}
Write
(P[i,j]:2,'->');
Way(P[i,j],j);
end
end;
begin
clrscr;
Init('A:eger.txt');
Solve;
Writeln('Введите
из какой станции
и в какую будем
искать путь:');
Readln(k,m);
Write(k:2,'->');
Way(k,m);
WriteLn(m:2);
WriteLn(‘Время
пути= ‘,D[k,m]);
readkey;
end.
10
Игра «Найди
друга».
uses crt;
Const n=20;
type mas=array[1..n]of Integer;
var A:mas;
X,b:integer;
procedure Init(z:string);
var i:integer;
f:text;
begin
Assign(f,z);
Reset(f);
For i:=1 to n do
Read(f,A[i]);
Close(f)
end;
procedure Print;
var i:integer;
begin
For i:=1 to n do
Write(A[i],' ');
end;
procedure Solve(i,j:integer;Var t:integer);
var m:integer;
begin
If i>j then Writeln('No')
else begin m:=(i+j)div 2;
Inc(b);
If A[m]
else If A[m]>X then Solve(i,m-1,t)
else Write(b);
end;
end;
begin
clrscr;
Init('A:game.txt');
Print;
WriteLn;
ReadLn(x);
Solve(1,n,b);
readkey;
end.
Заключение.
В данном
курсовом проекте
мы разработали
свой набор
задач и критерии,
по которым
данный набор
можно классифицировать.
Несмотря на
то, что разрабатывая
критерии
классификации,
мы оперировали
с конкретным
набором задач,
данная классификация
может быть
применима ко
многим наборам
задач. Единственное
несоответствие,
которое может
произойти, это
несоответствие
по тематике.
Таким образом,
данная классификация
достаточно
универсальна
и может иметь
широкое практическое
применение.
При выполнении
данного курсового
проекта основные
трудности
пришлись на
выбор литературы,
так как по данной
теме литературы
немного и ее
необходимо
рассматривать
с точки зрения
методики преподавания
информатики.
В сборниках
задач большое
место отведено
задачам, имеющим
строгую формулировку,
которую изменить
на ситуативную
достаточно
сложно, так как
задачи имеют
маленькую
практическую
значимость
в жизни.
Таким образом,
цели поставленные
при выполнении
данного курсового
проекта достигнуты.
Литература:
Б.Н. Иванов
Дискретная
математика.
Алгоритмы и
программы.
Москва 2001г.
С.М. Окулов
Программирование
в алгоритмах.
Москва 2002г.
Н.Вирт Алгоритмы
и структуры
данных. Москва
«Мир» 1989г.
В.М. Кирюхин,
А.В. Лапунов,
С.М. Окулов Задачи
по информатике.
Международные
олимпиады
1989-1996гг. Москва
ABF
1996г.
С.М. Окулов,
А.А. Пестов, О.А.
Пестов Информатика
в задачах. Киров
1998г.