Элементы дискретной математики - 72 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

72
80.
Граф задан матрицей смежности. Найти
· Какой-либо путь из вершины 2 в вершину 4;
· кратчайший путь из вершины 2 в вершину 4;
· кратчайшие пути из вершины 2 ко всем остальным вершинам.
1 2 3 4 5 6 7 8 9 10
1 0 1 0 0 1 0 0 0 0 0
2 1 0 1 0 0 0 0 0 1 0
3 0 1 0 1 0 0 0 0 0 0
4 0 0 1 0 1 1 0 1 1 0
5 1 0 0 1 0 0 0 0 0 0
6 0 0 0 1 0 0 1 0 0 0
7 0 0 0 0 0 1 0 1 0 1
8 0 0 0 1 0 0 1 0 0 0
9 0 1 0 1 0 0 0 0 0 0
10 0 0 0 0 0 0 1 0 0 0
81. На планете Глюк живет группа людей. Про некоторые пары людей известно, что они близкие
родственники. Назовем А и В родственниками, если А и В близкие родственники, или найдется
третий человек С, который по отдельности является родственником А и родственником В.
Опишите алгоритм нахождения всех родственников человека Х.
82.
На клетчатом листе бумаги размером 10 х 10 закрашены некоторые клетки. Разрешается ходить
по не закрашенным клеткам, переходя на каждом шаге вверх, вниз, вправо или влево. Описать
алгоритм, отвечающий на следующие вопросы:
А. Есть ли путь из левой нижней клетки в правую верхнюю;
Б. Какое минимальное число шагов нужно сделать, чтобы пройти этот
путь;
В. По каким клеткам при этом надо идти
83.
В двузначном числе за один ход разрешается заменить любую цифру суммой цифр по модулю
10. Заданы два двузначных числа a и b. Написать программу, которая определяет: можно ли
построить цепочку ходов, которая переводит a в b; минимальную такую цепочку. В двузначном
числе старшая цифра может быть и нулем.
84.
На шахматной доске N х N, несколько клеток, которой вырезано, заданы две клетки. Построить
минимальный путь коня из одной данной клетки в другую.
85.
В таблице N x N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9.
Предложить алгоритм, позволяющий найти маршрут из клетки (1,1) в клетку (N,N) и
удовлетворяющий следующим условиям:
·
любые две последовательные клетки в маршруте имеют общую сторону;
·
количество клеток маршрута минимально;
· из всех маршрутов, удовлетворяющих условиям 1) и 2), искомый маршрут тот, сумма
цифр в клетках которого максимальна.

Страницы