Рефераты

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

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

Вятский Государственный Гуманитарный Университет

Кафедра прикладной математики

Курсовая работа по информатике

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

дискретной математике.

Выполнил:Студент 4 курса

факультета информатики

Лепешкин Антон Геннадъевич

Проверила: Ашихмина Татьяна Викторовна

Киров 2004

Содержание.

Содержание. 2

Введение. 3

Глава 1 Теоретический материал. 4

Перебор с возвратом. 4

Поиск данных. 5

Логарифмический(бинарный) поиск 5

Методы сортировки. 6

Сортировка слияниями. 6

Быстрая сортировка Хоара. 6

Графы. 6

Представление графа в памяти компьютера 6

Достижимость 7

Кратчайшие пути. 8

Алгоритм Дейкстры 8

Алгоритм Флойда (кратчайшие пути между всеми парами вершин). 9

Глава 2 Система задач и упражнений. 9

Классификация задач. 9

Комнаты музея. 12

Пират в подземелье. 13

Диспетчер и милиция. 14

Задача о футболистах. 15

Задача о семьях. 16

Метро. 16

Роботы. 17

Вожатый в лагере 20

Егерь. 21

Игра «Найди друга». 22

Приложение. 22

1 22

2 25

3 27

4 30

5 32

6 32

7 34

8 39

9 41

10 43

Заключение. 45

Литература 45

Введение.

Несмотря на то, что для решения задач в основном используются общие методы,

все-таки мышление каждого конкретного человека немного отличается от

мышления других людей, если он обладает достаточной базой знаний. Таким

образом, при решении задач «начиная с нуля» можно зайти в тупик, если

выбрать неверный путь решения задачи. В данном курсовом проекте мы

разработаем собственную классификацию задач, позволяющую определить

наиболее подходящий способ решения, чтобы облегчить процесс моделирования и

составления алгоритма и предотвратить выбор неверного способа, также

рассмотрим данную классификацию с точки зрения методики преподавания

информатики. выбор неверного способа. В этом заключается актуальность

данного курсового проекта.

Цель: Разработать собственную классификацию для задач по дискретной

математике. Для достижения этой цели были поставлены следующие задачи:

1) Разработать собственную систему задач и упражнений по дискретной

математике.

2) Определить способы решения данных задач, используя теоретический

материал курса дискретной математики.

3) Составить алгоритм – программу для каждой задачи, реализующий

выбранный способы решения.

4) Разработать систему критериев классификации данной системы задач.

Глава 1 Теоретический материал.

Перебор с возвратом.

Общая схема

Даны N упорядоченных множеств U1 U2,..., Un (N - известно), и требуется

построить вектор А=(а1 а2, ..., аn), где a1€U1, a2€U2, ..., an€Un,

удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева

направо. Предположим, что уже найдены значения первых (к-1)

компонент, A=(a1, a2, ..., a(k-1)), ?, ..., ?), тогда заданное множество

условий ограничивает выбор следующей компоненты аk некоторым

множеством SkCUk. Если Sk<>[ ] (пустое), мы вправе выбрать в

качестве ак

наименьший элемент Sk и

перейти к выбору ^/^ "^выборы п«я»,

(к+1) компоненты и

так далее. Однако /[ + Д Jfcv при данном а,

если условия условия

а,, ^иаз

таковы, что Sk оказалось пустым, то мы возвращаемся к выбору

(к-1) компоненты, отбрасываем

а(k-1) и выбираем в качестве нового a(k-1) тот элемент S(k-i), который

непосредственно следует за только что отброшенным. Может оказаться, что для

нового a(k-1) условия задачи допускают непустое Sk, и тогда мы пытаемся

снова выбрать элемент ак. Если невозможно выбрать a(k-1), мы возвращаемся

еще на шаг назад и выбираем новый элемент а(к-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень)

есть пустой вектор. Его сыновья суть множество кандидатов для выбора а1 и,

в общем случае, узлы k-го уровня являются кандидатами на выбор ак при

условии, что а1, а2, ..., a(k-1) выбраны так, как указывают предки этих

узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются

ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим

получить все такие узлы.

Рекурсивная схема реализации алгоритма,

procedure Backtrack(Beктop,i);

begin

if then

else begin ;

for a€Si do Васкtrаск(вектор| | a,i+l); вектору компоненты

end; end;

Оценка временной сложности алгоритма. Данная схема реализации перебора

приводит к экспоненциальным алгоритмам. Действительно, Пусть все решения

имеют длину N, тогда исследовать требуется порядка | Si| *| S2| *...*| SN|

узлов дерева. Если значение S; ограничено некоторой константой С, то

получаем порядка CN узлов.

Поиск данных.

Логарифмический(бинарный) поиск

Логарифмический (бинарный или метод деления пополам) поиск данных применим

к сортированному множеству элементов а1 < а2 < ... < ап, размещение

которого выполнено на смежной памяти. Для большей эффективности поиска

элементов надо, чтобы пути доступа к ним стали более короткими, чем просто

последовательный перебор. Наиболее очевидный метод: начать поиск со

среднего элемента, т.е. выполнить сравнение с элементом а. Результат

сравнения позволит определить, в какой половине последовательности а{,

а2,..., а, 1+„ ,,..., ап продолжить поиск,

применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска

довольно проста, однако «для многих хороших программистов не одна попытка

написать правильную программу закончилась неудачей». Чтобы досконально

разобраться в алгоритме, лучше всего представить данные ах < а2 < ... < ап

в виде двоичного дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево называется деревом сравнений , если для любой его вершины

(корня дерева или корня поддерева) выполняется условие:

{Вершины левого поддерева}, s - вершина источник; матрица смежности

A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги

неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний - D.

В данном алгоритме формируется множество вершин Т, для которых еще не

вычислена оценка расстояние и, это главное, минимальное значение в D по

множеству вершин, принадлежащих Т, считается окончательной оценкой для

вершины, на которой достигается этот минимум. С точки зрения здравого

смысла этот факт достаточно очевиден. Другой "заход" в эту вершину возможен

по пути, содержащему большее количество дуг, а так как веса неотрицательны,

то и оценка пути будет больше.

Пример

Его матрица смежности:

| ? 3 7 ? ? ? |

|1 ? 2 ? ? 1 |

|А= ? 1 ? 4 4 ? |

|? ? ? ? 1 5 |

|? ? 1 ? ? 3 |

|? ? ? 2 ? ? |

В таблице приведена последовательность шагов (итераций) работы алгоритма.

На первом шаге минимальное значение D достигается на второй вершине. Она

исключается из множества Т, и улучшение оценки до оставшихся вершин

(3,4,5,6) ищется не по всем вершинам, а только от второй.

| | | | | | | |

| | | | | | | |

| | | | | | | |

11. 6 11 6 3 10 6

7 9 6 13 5 7 5

1 10 12 7 13 13 5

13 11 10 8 10 14 13

Цифровая карта

Площадь музея состоит из клеток: m рядов и p столбцов. В каждой клетке

такой матрицы (цифровая карта) проставляется число, в котором кодируется

наличие стен у данной клетки. Значение числа в каждой клетке является

суммой чисел: 1 (клетка имеет стену на западе), 2 (клетка имеет стену на

севере), 4 (клетка имеет стену на востоке), 8 (клетка имеет стену на

юге). Например, если в клетке стоит число 11 (11=8 + 2 + 1), то клетка

имеет стену с южной стороны, с северной и с западной.

Исходные данные представляются в текстовом файле со следующей

структурой. Первая строка: m, p – размерность сетки. Вторая строка,

третья и следующие строки содержат описание матрицы цифровой карты по

строкам. Расчетные данные вывести на экран в следующем порядке: первая

строка – площадь каждой комнаты музея, вторая строка – количество комнат

в музее.

Пример файла исходных данных:

4. 7

11 6 11 6 3 10 6

7 9 6 13 5 7 5

1 10 12 7 13 13 5

13 11 10 8 10 14 13

Пример выходных данных:

9 3 8 2 6

5

Идея решения:

Данную задачу можно решить используя метод перебора с возвратом.

Используя массив координат перемещения, смотрим, где отсутствуют стены,

для каждой клетки, и последовательно двигаемся в ту клетку, в которую

возможно, предварительно помечая клетку, в которой уже были. Если мы

зашли в тупик, то возвращаемся в клетку, из которой вышли. Одновременно

считаем количество клеток в каждой комнате. Когда происходит возврат в

начальную точку движения, делаем всю комнату просмотренной (при помощи

массива логического типа). Затем ищем клетку, в которой ещё не были и

делаем её начальной точкой движения.

(Текст программы см. Приложение 1)

Пират в подземелье. В поисках драгоценных камней пират проваливается в

подземелье. План подземелья – матрица N*M комнат с драгоценными камнями.

Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой

комнате разрешается взять всего лишь один камень с собой и следовать в

любую другую соседнюю с ней комнату. Каждую из комнат пират может

посещать всего лишь один раз. Требуется составить алгоритм-программу

определения маршрута посещения пиратом К комнат лабиринта таким образом,

чтобы он набрал камней на максимально возможную сумму. Входные и выходные

данные: В первой строке входного файла содержатся числа N,M,K. В

следующих N строках располагается матрица N*M лабиринта. Каждый элемент

матрицы представляется стоимостью камня соответствующей комнаты. Маршрут

начинается с левой верхней угловой комнаты лабиринта. Выходные данные:

содержат единственное число, равное общей стоимости взятых с собой

камней.

Пример файла исходных данных:

3 4 7

1 1 1 1

1 1 2 1

1 1 2 3

Выходные данные для данного примера:

12

Идея решения: Данную задачу можно решить используя метод перебора с

возвратом. Двигаясь последовательно по комнатам считаем общую стоимость

камней и выбирая наибольшую перебираем все возможные варианты

передвижения пирата по комнатам.

(Текст программы см. Приложение 2)

Диспетчер и милиция. У диспетчера имеется схема города, на которой

изображены районы и дороги, связывающие данные районы. На схеме указаны

расстояния от одного пункта к другому и направление движения, которое

разрешено. Схема выглядит следующим образом:

Диспетчеру поступают запросы из патрульных машин милиции, патрульные

сообщают район, где они находятся и район, в который им необходимо

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

помогла диспетчеру найти минимальное расстояние, которое предстоит

покрыть патрульной машине. Необходимо учесть направление движения,

которое разрешено на данном участке пути.

Решение. Входные и выходные данные:

Первая строка входного файла содержит количество районов города. Затем

идет матрица смежности, где занесены все пути из одной вершины в другую с

расстоянием:

6

0 3 7 0 0 0

1 0 2 0 0 1

0 1 0 4 4 0

0 0 0 0 1 5

0 0 1 0 0 3

0 0 0 2 0 0

Номер района, из которого выехала милицейская машина и в который ей

необходимо попасть вводятся с клавиатуры.

Выходные данные:

Единственное число, которое представляет собой минимальный путь, который

предстоит покрыть милицейской машине.

Идея решения: данную задачу можно решить с помощью алгоритма поиска

кратчайших путей в графе (алгоритм Дейкстры).

(Текст программы см. Приложение 3)

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

как команда большая, то все игроки залезли в два автобуса, в произвольном

порядке и в разных количествах. В автобусах игроки по привычке

построились по возрастанию номеров и сели. Необходимо составить алгоритм

– программу, помогающую игрокам, на выходе из двух автобусов, сразу же

вставать по возрастанию номеров.

Исходные и выходные данные:

Входной файл содержит три строки. В первой строке находятся два числа –

количество игроков в первом и втором автобусах. Вторая строка содержит

номера игроков, находящихся в первом автобусе. Третья строка содержит

номера игроков, находящихся во втором автобусе:

5 8

4 7 9 15 23

1 2 3 5 6 8 10 17

Выходные данные: номера футболистов, вышедших из автобусов в порядке

возрастания. Выходные данные для данного примера:

1 2 3 5 6 7 8 9 10 15 17 23

Идея решения:

Оптимального решения данной задачи можно добиться, используя метод

сортировки слияниями.

(Текст программы см. Приложение 4)

Задача о семьях. На сельской улице живут Ивановы и Петровы. Необходимо,

используя минимальное число обменов, расселить их так, чтобы Ивановы жили с

одного конца улицы, а Петровы – с другого.

Исходные и выходные данные. С клавиатуры вводится n - количество человек,

проживающих на данной улице. Затем вводится массив А[1..n], состоящий из 0

и 1, где 0 – Петров, 1 – Иванов. Выходными данными является число обменов.

Идея решения:

Задача по методам сортировки. Один из способов её решения заключается в

следующем. Пусть Ивановы должны жить в начале улицы, а Петровы – в конце.

По индексу i (i=0 do

begin

If A[i,j]sum1 then {сравниваем текущую стоимость набранных камней со

стоимотью набранных ранее, с целью увеличения стоимости}

sum1:=sum;

end

Else begin

For i:=1 to 4 do

If (A[x+dx[i],y+dy[i]]>0)and B[x+dx[i],y+dy[i]] then

{просматриваем варианты перехода пирата в другую комнату, проверяя не был

ли пират в ней до этого}

begin

sum:=sum+A[x+dx[i],y+dy[i]]; {прибавляем стоимость камня,

находящегося в данной комнате к суммарной стоимости}

B[x+dx[i],y+dy[i]]:=false; {отмечаем, что в данной комнате мы уже

были}

Solve(x+dx[i],y+dy[i],p-1);

sum:=sum-A[x+dx[i],y+dy[i]];

B[x+dx[i],y+dy[i]]:=true;

end;

end;

end;

begin

clrscr;

Init('A:241.txt');

sum1:=0; sum:=A[1,1];

Solve(1,1,col);

WriteLn('Result= ',sum1);

readkey;

end.

3 Диспетчер и милиция.

Uses crt;

Const n=100;

Type mas=array[1..n,1..n]of Integer;

mas1=array[1..n]of Integer;

mn=Set of 1..n;

Var m,first,last:integer;

D:mas1;

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[] 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 (ij) 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[1..M])do Inc(i);

ProvCanMet:=iN)do begin

j:=i+1;

while(jj)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[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(timeN*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 ix then Inc(i)else {смотрим элементы списка относительно

If A[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]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г.

-----------------------

Начало

Выборы для А1

Выборы для А2 при А1

Выборы для А3 при данных А1 и А2

1

6

2

2

3

4

4

1

3

5

1

1

1

2

7

5

4

3

1

1

2

3

4

5

6

1

2

3

4

5

6

7

8

1

1

2

3

4

5

6

Задачи с использованием алгоритма перебора с возвратом

Задачи с использованием

алгоритмов поиска данных

Задачи с использованием методов сортировки

Задачи с использова -нием алгоритмов на графах

Логарифмический поиск

Линейный поиск

Сортировка Хоара

Сортировка слияниями

Достижимость

Кратчайшие пути в графе

Алгоритм Дейкстры

Алгоритм Флойда

Задачи высокого уровня сложности

Задачи среднего уровня сложности

Задачи низкого уровня сложности

По формулировке задачи.

Ситуативные задачи

Задачи со строгой формулировкой

По количеству способов решения.

Задачи с единственным способом решения

Задачи с несколькими способами решения

По массовости решения задачи.

Задачи, имеющие решение применимое только к конкретным задачам.

Задачи, имеющие решение применимое к целому классу подобных задач.


© 2010 Современные рефераты