10. Заданы два человека – p и q. Ответить, являются ли они родственниками.
11. Родом называется максимальное подмножество людей, любые два из которого являются родственниками. Найти число родов, содержащихся в данном множестве {0, 1, 2, …, n-1}.
12. Заданы два человека p и q. Найти цепь детей и родителей, соединяющих p и q, если такая цепь существует.
13. Заданы два человека p и q. Найти соединяющую их цепь родителей, доказывающих, что p – потомок q, при условии, что это верно.
14. Заданы два человека p и q. Определить, имеют ли они общего предка.
В вариантах 15 – 18 задан лабиринт, соединяющий узлы 0, 1, 2, …, n-1. Узлы лабиринта 0 £ i, j £ n-1 считаются соединенными тоннелями, если aij = 1. Узел 0 является выходом из лабиринта.
15. Найти все узлы, из которых существуют пути к выходу.
16. Задан узел p. Существует ли путь к выходу из узла p?
17. Задан узел p. Найти путь в лабиринте, приводящий к выходу.
18. Найти пути к выходу из всех узлов лабиринта.
В вариантах 19 – 23 через (x, y) обозначается поле шахматной доски, находящееся на горизонтали y и на вертикали x.
19. Из шахматной доски удалили клетки (a0, b0), (a1, b1), …, (an-1, bn-1). Найти все поля, в которые можно попасть конем из заданного поля (x, y).
20. Из шахматной доски удалили клетки (a0, b0), (a1, b1), …, (an-1, bn-1). Определить, можно ли попасть конем с поля (x, y) на поле ( x', y' ).
21. Из шахматной доски удалили клетки (a0, b0), (a1, b1), …, (an-1, bn-1). Разбить оставшиеся поля на подмножества, поля которых связаны маршрутами шахматного коня.
22. Для каждого поля шахматной доски найти по крайней мере один маршрут шахматного коня в поле (0, 0).
23. Найти маршруты шахматного коня во все поля шахматной доски из поля (0, 0), по одному маршруту для каждого поля.
В вариантах 24 – 30 заданы n человек и квадратная матрица (aij) размерности n, элементы которой принимают значения aij = 1, если i – родитель человека с номером j, 0 £ i, j £ n-1, в других случаях aij = 0.
24. Найти всех предков человека с номером p.
25. Найти всех потомков человека с номером p.
26. Найти всех родственников человека с номером p.
27. Ответить, являются ли родственниками заданные p и q.
28. Найти все роды΄, содержащиеся во множестве {0, 1, 2, …, n-1}. Определение рода см. в варианте 11.
29. Заданы два человека p и q. Найти цепь детей и родителей, соединяющих p и q и содержащую информацию о родственных связях.
30. Найти цепь предков человека p, соединяющую его с предком q.
Примеры выполнения задания 2
Пример 1
Направленный граф задан с помощью матрицы смежности (aij), 0 £ i, j £ n-1. Если существует стрелка из i в j, то aij = 1. В противном случае aij = 0. Написать подпрограмму, определяющую, существует ли направленный путь из p в q, где p и q – заданные вершины.
Решение
Будем раскрашивать вершины с помощью рекурсивной функции, начиная с вершины p. Как только вершина q раскрашена, возвращаем значение 1.
Текст программы:
#include <stdio.h>
#include <conio.h>
int a[5][5] = { 0, 0, 1, 0, 1,
0, 1, 0, 0, 1,
0, 0, 0, 0, 1,
0, 1, 0, 0, 0,
0, 0, 0, 0, 0 };
int c[5]; // цвета вершин
int rec( int p, int q, int n )
{
int i, s;
if( c[q] ) return 1;
{
c[p] = 1;
for(i = 0; i < n; i++)
if( a[p][i] ) s = s || rec( i, q, n );
} // раскрашиваются концы стрелок, выходящих из p
return s;
}
main ( )
{
int i;
for(i = 0; i < 5; i++) c[i] = 0; // не раскрашены
if( rec( 0, 3, 5 ) ) puts(“\n Существует путь из 0 в 3”);
else puts(“\n Нет пути”); }
Программа выведет:
Существует путь из 0 в 3
Пример 2
Из шахматной доски удалили клетки (a0, b0), (a1, b1), …, (an-1, bn-1). Найти маршрут шахматного коня из поля (x, y) в поле ( x', y' ).
Решение
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.