Рекурсивный алгоритм. Определение рекурсивной функцию int Lat, возвращающую количество латинских букв в текстовом файле, страница 6

Другие предметы \ Объектно ориентированное програмирование

Односвязный циклический список

Двухсвязный циклический список

Дерево поиска

точка (x, y) плоскости

точка (x, y, z) пространства

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

Символ s и позиция (x, y)

Длинное целое число

Каждое поле (x, y) будем рассматривать как вершину графа. Ребрами этого графа служат пары полей, отличающиеся ходом шахматного коня. Задача сводится к нахождению пути между двумя вершинами в простом неориентированном графе. Вместо пары чисел (x, y) можно рассматривать одно число x+8*y. Это позволяет присвоить номера вершинам полученного графа. Шахматная доска будет состоять из полей, имеющих номера 0, 1, …, 7 в верхней горизонтали, 8, 9, …, 15 – в следующей горизонтали и т.д.

Вместо матрицы смежности рассмотрим функцию

Int hod( int x0, int y0, int x1, int y1 );

возвращающую 1, если существует ход коня с поля (x0, y0) на поле (x1, y1), и 0 – в других случаях.

Определим массив цветов

int c[64];

в котором цвет вершины графа, соответствующий полю (x, y), имеет индекс x+8*y.

Пусть массивы dx[8] и dy[8] обозначают приращения координат поля за каждый из восьми возможных ходов.

Напишем программу:

// Путь коня

#include <stdio.h>

#include <conio.h>

int dx[8], dy[8]; // приращения координат

int c[64]; // цвет вершины (x,y) равен c[8*y+x]

struct del // массив удаленных полей

{

int x,y;

} ndel[3] = { {1,2}, {2,3}, {3,2} };

int nd = 3; // 3 поля удалены

int ppr = 0;

// возвращает 1, если существует ход коня из (x0,y0) в (x1,y1)

int hod (int x0,int y0, int x1, int y1)

{

int i;

if( x0<0 || x0>7|| x1<0 || x1>7 ||

y0<0 || y0>7|| y1<0 || y1>7 ) return 0;

for(i = 0; i < nd; i++)

if ((x0==ndel[i].x && y0 == ndel[i].y) ||

(x1==ndel[i].x && y1 == ndel[i].y) ) return 0;

for(i = 0; i < 8; i++)

if (x1==x0+dx[i] && y1==y0+dy[i]) return 1;

return 0;

}

void rec(int px, int py, int qx, int qy)

{

int i, rx, ry;

if (c[qx+8*qy]>=0) return ;

for (i = 0; i < 8; i++)

if (hod(px,py,rx=px+dx[i],ry=py+dy[i])&& c[rx+8*ry]<0 )

{

c[rx+8*ry] = px+8*py;

rec (rx,ry,qx,qy);

}

void path (int sx, int sy, int vx, int vy)

{

if (sx==vx && sy==vy)

{

printf("(%d,%d) ",sx,sy); ppr++; return;

}

if (c[vx+8*vy]>=0)

{

path(sx,sy,c[vx+8*vy]%8,c[vx+8*vy]/8);

printf("(%d,%d) ",vx,vy); ppr++;

if (ppr%10==0) puts("\n");

}

else printf("\n no path from (%d,%d) into (%d,%d)", sx,sy,vx,vy);

}

main()

{

int i;

int sx = 0, sy =0, qx=1, qy =1;

dx[0] = 2; dy[0] = 1; dx[1] = 1; dy[1] = 2;

dx[2] = -1; dy[2] = 2; dx[3] = -2; dy[3] = 1;

dx[4] = -2; dy[4] = -1; dx[5] = -1; dy[5] = -2;

dx[6] = 1; dy[6] = -2; dx[7] = 2; dy[7] = -1;

clrscr();

for (i=0; i<64; i++) c[i]=-1;

c[sx+8*sy] = sx+8*sy;

rec(sx,sy,qx,qy);

printf("\n path from (%d,%d) into (%d,%d) consists of fields",

sx,sy,qx,qy);

puts("\n");

path(sx,sy,qx,qy);

getch() ;

}

На экран будет выведен следующий маршрут шахматного коня, начинающийся с (0, 0) и кончающийся в (1, 1):

path from (0,0) into (1,1) consists of fields

(0,0) (2,1) (4,2) (6,3) (7,5) (6,7) (4,6) (2,7) (0,6) (1,4)

(3,5) (5,6) (7,7) (6,5) (5,7) (3,6) (1,7) (0,5) (2,6) (4,7)

(5,5) (7,6) (6,4) (4,5) (6,6) (5,4) (3,3) (2,5) (3,7) (1,6)

(2,4) (0,3) (1,5) (3,4) (1,3) (0,1) (2,2) (4,3) (3,1) (5,2)

(7,3) (6,1) (5,3) (7,4) (6,2) (4,1) (6,0) (7,2) (5,1) (3,0)

(1,1)

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 2

Задание 1

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

Варианты заданий

1 2 3 4 5 6 7 8 9 10 11 12

Скачать файл