Xreferat.com » Рефераты по информатике и программированию » Разработка системы задач (алгоритмы-программы) по дискретной математике

Разработка системы задач (алгоритмы-программы) по дискретной математике

A:mas;


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]0)and(i in R) then

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 (iN)do begin

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 (iN)do begin

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.

Заключение.

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

Таким образом, цели поставленные при выполнении данного курсового проекта достигнуты.


Литература:

  1. Б.Н. Иванов Дискретная математика. Алгоритмы и программы. Москва 2001г.

  2. С.М. Окулов Программирование в алгоритмах. Москва 2002г.

  3. Н.Вирт Алгоритмы и структуры данных. Москва «Мир» 1989г.

  4. В.М. Кирюхин, А.В. Лапунов, С.М. Окулов Задачи по информатике. Международные олимпиады 1989-1996гг. Москва ABF 1996г.

  5. С.М. Окулов, А.А. Пестов, О.А. Пестов Информатика в задачах. Киров 1998г.

  6. Н.Вирт Систематическое программирование. Под ред. Ю.М. Баяковского. Москва «Мир» 1977г.
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: