Автор: Пользователь скрыл имя, 18 Марта 2012 в 15:39, курсовая работа
В настоящее время теория алгоритмов и смежные с ней разделы привлекают большое внимание специалистов различных областей науки и техники, являясь эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Особое значение с практической точки зрения имеет теория графов, использующаяся при проектировании интегральных схем и схем управления, исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, при разработке вычислительных и информационных сетей, в схемотехническом и конструкторско-топологическом проектировании и т.д.
Visited: array[1..n] of boolean;
f: boolean;
i: integer;
Procedure Depth(p: integer);
var k: integer;
Begin
Visited[p]:=True;
For k:=1 to n do
If not f then
If m[p, k] and not Visited[k] then
If k=B then
Begin
f:=True;
Write(B);
Break
End
else Depth(k);
If f then write('<--', p);
End;
Begin
For i:=1 to n do Visited[i]:=False;
f:=false;
Depth(A);
If not f then write('Пути из ', A, ' в ', B, ' нет')
End;
Procedure spravka(st:string);
var
s,s1,s2:string;
begin
s1:='Программу разработала студентка группы ис-10-1 Здерева Е.С.';
s2:='Рекомендации: А-начальная вершина, В- конечная вершина.Резльтатом работы программы является путь, по которому можно попасть из вершины А в вершину В.';
writeln(s1);
writeln(s2);
end;
begin
write('A=');readln(a);
write('B=');readln(b);
writeln('1-поиск в глубину 2-поиск в ширину 3-справка пользователя');readln(w);
case w of
1: breadth_search(A, B);
2: depth_search(A, B);
3: spravka(st);
end;
readln;
end.
Листинг программы на языке С++
#include <stdio.h>
#include <conio.h>
int m [9] [9]={
{0,1,1,0,0,0,0,0,0},
{1,0,1,0,0,0,1,1,0},
{1,1,0,1,1,0,0,0,0},
{0,0,1,0,1,0,0,0,0},
{0,0,1,1,0,1,0,1,0},
{0,0,0,0,1,0,1,1,1},
{0,1,0,0,0,1,0,1,1},
{0,1,0,0,1,1,1,0,0},
{0,0,0,0,0,1,1,0,0}
};
int a,b,w,j,f, visited [9];
void search(int a,int b)
{
int prev [9];
int c [9];
int head,tail;
int i,v,k;
head=0;
tail=0;
f=0;
for(i = 0; i<9; i++)
{
visited[i] = 0;
prev[i] = 0;
}
c[tail] = a;
visited[a] = 1;
while((head<=tail) && !f)
{
v = c[head];
head++;
for(k = 0; k<9; k++)
if((m[v][k])&&(!visited[k]))
{
tail++;
c[tail] = k;
visited[k] = 1;
prev[k] = v;
if(k==b){f = 1; break;}
}
}
if (f) {k = b;
printf("%i",b+1);
while (prev[k] != 0){
printf("<= %i",prev[k]+1);
k = prev[k];
}
}else{printf("Put iz %i v %i net",a,b);}
}
void Depth(int p)
{
int i;
int k;
visited[p]=1;
for (k=0;k<9;k++)
if (f==0)
if ((m[p][k]) && (!visited[k]))
if (k==b) {
f=1;
printf("%i",b+1);
break;}
else {Depth(k);}
if (f) {printf("<= %i",p+1); }
}
void main()
{
printf("A="); scanf("%i",&a);
printf("B="); scanf("%i",&b);
printf("1 – poisk v glubinu\n2 – poick v shirinu \n");
scanf("%i",&w);
a--;b--;
switch(w){
case 1:{
for ( j=0;j<9;j++) {visited[j]=0;}
f=0;
Depth (a);
if (f==0) {printf("Puti iz %i v %i net",a,b);}
getch();break; }
case 2: { search(a,b);getch(); break; }
}
}