Задача 3.1.1. На рисунке приведен граф (множество вершин, соединенных ребрами). Сколько существует путей из вершины А в K?
Начиная с вершин ближайшего окружения вершины старта А, считайте количество путей в них. У просчитанных вершин ставьте числовую метку, равную количеству путей из А в эту вершину. Подумайте, как посчитать количество путей в текущую вершину, если известно количество путей в вершины, из которых есть ребра в текущую вершину.
Поставим в точку старта метку 1.
Рассмотрим вершины, в которые напрямую идут ребра из вершины А и ни из каких других вершин нет ребер. Это вершины В и D. Очевидно, что в них идет только 1 путь из А, поэтому у них делаем метку «1» (фактически – повторение метки вершины А):
Далее рассмотрим вершины, у которых все вершины-источники (то есть вершины, из которых ведут ребра в данные) уже имеют метки. Это вершины C и Е. В каждую из них ведут два пути. Например, в С ведут пути АВС и АС. Ставим у вершин C и Е метку 2:
Рискнем предположить, что метка 2 в вершине C получилась как сумма меток входящих вершин А и B.
Далее метки заполнены у входящих вершин для F и H. У F только одна входная вершина – B, поэтому в неё просто перепишем метку вершины B. Проверим предположение, что в H ведет количество путей, равное сумме меток входящих вершин C, D, E = 2 + 1 + 2 = 5, перечислив возможные пути:
АВСH
ACН
ADH
ADEH
AEH
Количество перечисленных путей совпадает с суммой меток. Методика подсчета количества путей разработана.
Ошибка. Некоторые ученики, не знающие методики, пытаются перечислить все возможные пути. Это долго и в больших графах легко может привести к ошибкам.
Продолжение хода решения.
На следующих двух шагах просчитаем вершину J = 2 + 5 = 7, затем I = 7 + 5 = 12
Просчитываем вершину G = F + B + C + H + I = 1 + 1 + 2 + 5 + 12 = 21
И вершину K = F + G + I = 1 + 21 + 12 = 34
Ответ: 34
Задача 3.1.1А. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж, но не проходящих через город К?
Так как пути не должны проходить через город K, вычеркнем все дороги, ведущие в K и исходящие из К:
Вычеркнем пути, идущие в обход Ж:
Посчитаем количество путей, как в предыдущей задаче:
Ответ. 16
Задача 3.1.2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
|
A
|
B
|
C
|
D
|
E
|
F
|
|
A
|
|
4
|
|
|
|
|
|
B
|
4
|
|
6
|
3
|
6
|
|
|
C
|
|
6
|
|
|
4
|
|
|
D
|
|
3
|
|
|
2
|
|
|
E
|
|
6
|
4
|
2
|
|
5
|
|
F
|
|
|
|
|
5
|
|
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
В табличном виде искать короткий путь трудно. Вместо табличного представления постройте граф.
Представим маршруты в виде графа:
При таком представлении видно, что без участков AB и EF нам не обойтись, а между B и E проходят следующие пути:
BE = 6
BDE = 3 + 2 = 5
BCE = 6 + 4 = 10
Самый короткий путь:
ABDEF = 4 + 5 + 5 = 14
Ответ: 14
Примечание. Старайтесь располагать вершины в одну линию. Так проще увидеть и сравнить альтернативные маршруты.
Задача 3.1.3. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длинах этих дорог.
|
|
|
|
П1
|
П2
|
П3
|
П4
|
П5
|
П6
|
П7
|
|
П1
|
|
5
|
|
10
|
|
|
|
|
П2
|
45
|
|
|
40
|
|
55
|
|
|
П3
|
|
|
|
|
15
|
60
|
|
|
П4
|
10
|
40
|
|
|
|
20
|
35
|
|
П5
|
|
|
15
|
|
|
55
|
|
|
П6
|
|
55
|
60
|
20
|
55
|
|
45
|
|
П7
|
|
|
|
35
|
|
45
|
|
|
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Д в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
По количеству путей в вершины поищите соответствия между вершинами в графе и в таблице.
По графу видно, что вершина с максимальным количеством ребер – это B. В неё входят 5 ребер. Единственный пункт в таблице, в который ведут 5 путей – это П6 (в строчке П6 пять чисел и в столбце П6 пять чисел). Значит B = П6.
|
|
П1
|
П2
|
П3
|
П4
|
П5
|
B
|
П7
|
|
П1
|
|
45
|
|
10
|
|
|
|
|
П2
|
45
|
|
|
40
|
|
55
|
|
|
П3
|
|
|
|
|
15
|
60
|
|
|
П4
|
10
|
40
|
|
|
|
20
|
35
|
|
П5
|
|
|
15
|
|
|
55
|
|
|
B
|
|
55
|
60
|
20
|
55
|
|
45
|
|
П7
|
|
|
|
35
|
|
45
|
|
Следующая вершина по количеству ребер – это E, в неё входят четыре ребра. Ей соответствует Е = П4
|
|
П1
|
П2
|
П3
|
E
|
П5
|
B
|
П7
|
|
П1
|
|
45
|
|
10
|
|
|
|
|
П2
|
45
|
|
|
40
|
|
55
|
|
|
П3
|
|
|
|
|
15
|
60
|
|
|
E
|
10
|
40
|
|
|
|
20
|
35
|
|
П5
|
|
|
15
|
|
|
55
|
|
|
B
|
|
55
|
60
|
20
|
55
|
|
45
|
|
П7
|
|
|
|
35
|
|
45
|
|
Единственная вершина с тремя ребрами Г = П2.
|
|
П1
|
Г
|
П3
|
E
|
П5
|
B
|
П7
|
|
П1
|
|
45
|
|
10
|
|
|
|
|
Г
|
45
|
|
|
40
|
|
55
|
|
|
П3
|
|
|
|
|
15
|
60
|
|
|
E
|
10
|
40
|
|
|
|
20
|
35
|
|
П5
|
|
|
15
|
|
|
55
|
|
|
B
|
|
55
|
60
|
20
|
55
|
|
45
|
|
П7
|
|
|
|
35
|
|
45
|
|
Вершин с двумя ребрами у нас четыре. Но вершину Д мы можем опознать, так как она соединяет уже найденные нами вершины B и E:
Д = П7
|
|
П1
|
Г
|
П3
|
E
|
П5
|
B
|
Д
|
|
П1
|
|
45
|
|
10
|
|
|
|
|
Г
|
45
|
|
|
40
|
|
55
|
|
|
П3
|
|
|
|
|
15
|
60
|
|
|
E
|
10
|
40
|
|
|
|
20
|
35
|
|
П5
|
|
|
15
|
|
|
55
|
|
|
B
|
|
55
|
60
|
20
|
55
|
|
45
|
|
Д
|
|
|
|
35
|
|
45
|
|
Таким образом, путь ДЕ = (П7, П4) = 35
Ответ: 35
Задача 3.1.4. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
|
П1
|
П2
|
П3
|
П4
|
П5
|
П6
|
П7
|
П8
|
|
П1
|
|
|
|
3
|
|
|
|
23
|
|
П2
|
|
|
25
|
|
|
44
|
|
46
|
|
П3
|
|
25
|
|
|
|
|
|
|
|
П4
|
37
|
|
|
|
34
|
|
42
|
|
|
П5
|
|
|
|
34
|
|
24
|
28
|
|
|
П6
|
|
44
|
|
|
24
|
|
29
|
|
|
П7
|
|
|
|
42
|
28
|
29
|
|
3
|
|
П8
|
23
|
46
|
|
|
|
|
31
|
|
|
|
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.
ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.
Это задача является усложненным аналогом предыдущей задачи.
Посчитаем количество входящих в каждую вершину ребер:
Уникальными по количеству ребер являются вершины: Л, В, Г. Найдем в таблице пункты, в которых количество входящих ребер (заполненных клеток по столбцу или строке) равно количеству входящих ребер перечисленных вершин:
|
|
В
|
П2
|
Л
|
П4
|
П5
|
П6
|
Г
|
П8
|
|
В
|
|
|
|
37
|
|
|
|
23
|
|
П2
|
|
|
25
|
|
|
44
|
|
46
|
|
Л
|
|
25
|
|
|
|
|
|
|
|
П4
|
37
|
|
|
|
34
|
|
42
|
|
|
П5
|
|
|
|
34
|
|
24
|
28
|
|
|
П6
|
|
44
|
|
|
24
|
|
29
|
|
|
Г
|
|
|
|
42
|
28
|
29
|
|
31
|
|
П8
|
23
|
46
|
|
|
|
|
31
|
|
|
|
Вершина Л соединяется только с вершиной К. Найдем К по таблице. Это П2:
|
|
В
|
K
|
Л
|
П4
|
П5
|
П6
|
Г
|
П8
|
|
В
|
|
|
|
37
|
|
|
|
23
|
|
К
|
|
|
25
|
|
|
44
|
|
46
|
|
Л
|
|
25
|
|
|
|
|
|
|
|
П4
|
37
|
|
|
|
34
|
|
42
|
|
|
П5
|
|
|
|
34
|
|
24
|
28
|
|
|
П6
|
|
4
|
|
|
24
|
|
29
|
|
|
Г
|
|
|
|
42
|
28
|
29
|
|
31
|
|
П8
|
23
|
46
|
|
|
|
|
31
|
|
|
|
Мы уже опознали все вершины, с которыми соединяется вершина Е. Найдем Е по таблице. Это П8:
|
|
В
|
K
|
Л
|
П4
|
П5
|
П6
|
Г
|
Е
|
|
В
|
|
|
|
37
|
|
|
|
23
|
|
К
|
|
|
25
|
|
|
44
|
|
46
|
|
Л
|
|
25
|
|
|
|
|
|
|
|
П4
|
37
|
|
|
|
34
|
|
42
|
|
|
П5
|
|
|
|
34
|
|
24
|
28
|
|
|
П6
|
|
44
|
|
|
24
|
|
29
|
|
|
Г
|
|
|
|
42
|
28
|
29
|
|
31
|
|
Е
|
23
|
46
|
|
|
|
|
31
|
|
|
|
Вершина А соединяется с В и Г. Это П4. Вершина Д соединяется с Г и К. Это П6:
|
|
В
|
K
|
Л
|
А
|
П5
|
Д
|
Г
|
Е
|
|
В
|
|
|
|
37
|
|
|
|
23
|
|
К
|
|
|
25
|
|
|
44
|
|
46
|
|
Л
|
|
25
|
|
|
|
|
|
|
|
А
|
37
|
|
|
|
34
|
|
42
|
|
|
П5
|
|
|
|
34
|
|
24
|
28
|
|
|
Д
|
|
44
|
|
|
24
|
|
29
|
|
|
Г
|
|
|
|
42
|
28
|
9
|
|
31
|
|
Е
|
23
|
46
|
|
|
|
|
31
|
|
|
|
Методом исключения найдем Б. Это П5:
|
|
В
|
K
|
Л
|
А
|
Б
|
Д
|
Г
|
Е
|
|
В
|
|
|
|
37
|
|
|
|
23
|
|
К
|
|
|
25
|
|
|
44
|
|
46
|
|
Л
|
|
25
|
|
|
|
|
|
|
|
А
|
37
|
|
|
|
34
|
|
42
|
|
|
Б
|
|
|
|
34
|
|
24
|
28
|
|
|
Д
|
|
44
|
|
|
24
|
|
29
|
|
|
Г
|
|
|
|
42
|
28
|
29
|
|
31
|
|
Е
|
23
|
46
|
|
|
|
|
31
|
|
|
|
По таблице найдем расстояние БГ = 28.
Ответ: 28
Задача 3.1.5. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
|
|
|
|
П1
|
П2
|
П3
|
П4
|
П5
|
П6
|
П7
|
|
П1
|
|
|
7
|
|
13
|
12
|
|
|
П2
|
|
|
|
|
5
|
|
10
|
|
П3
|
7
|
|
|
|
15
|
6
|
11
|
|
П4
|
|
|
|
|
|
10
|
|
|
П5
|
13
|
5
|
15
|
|
|
|
8
|
|
П6
|
12
|
|
6
|
10
|
|
|
|
|
П7
|
|
10
|
11
|
|
8
|
|
|
|
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите кратчайший путь из пункта А в пункт К. В ответе перечислите все населённые пункты, через которые проходит путь. Например, путь из Г в Д через Е и К записывается как ГЕКД.
Посчитаем для каждой вершины, сколько в неё входит ребер:
|
А
|
Б
|
В
|
Г
|
Д
|
Е
|
К
|
|
1
|
3
|
3
|
4
|
4
|
3
|
2
|
Видно, что уникальными по количеству вершин являются А и К. Найдем строчку и столбец, в котором заполнена только одна клетка; это будет вершина А. И найдем строчку и столбец, в которых заполнены две клетки; это будет К:
|
|
П1
|
К
|
П3
|
А
|
П5
|
П6
|
П7
|
|
П1
|
|
|
7
|
|
13
|
12
|
|
|
К
|
|
|
|
|
5
|
|
10
|
|
П3
|
7
|
|
|
|
15
|
6
|
11
|
|
А
|
|
|
|
|
|
10
|
|
|
П5
|
13
|
5
|
15
|
|
|
|
8
|
|
П6
|
12
|
|
6
|
10
|
|
|
|
|
П7
|
|
10
|
11
|
|
8
|
|
|
Вершина А соединяется с Б. Найдем по строчке А заполненную клетку, ей будет соответствовать столбец Б:
|
|
П1
|
К
|
П3
|
А
|
П5
|
Б
|
П7
|
|
П1
|
|
|
7
|
|
13
|
12
|
|
|
К
|
|
|
|
|
5
|
|
10
|
|
П3
|
7
|
|
|
|
15
|
6
|
11
|
|
А
|
|
|
|
|
|
10
|
|
|
П5
|
13
|
5
|
15
|
|
|
|
8
|
|
Б
|
12
|
|
6
|
10
|
|
|
|
|
П7
|
|
10
|
11
|
|
8
|
|
|
Рассмотрим строчку Б. У Б есть соединение с П1, П3 и А. Рассмотрим колонки П1 и П3. В П1 входит три ребра, в П3 – четыре ребра. По графу в Б входит В с тремя ребрами и Г с четырьмя. Следовательно, П3 = Г и П1 = В:
|
|
В
|
К
|
Г
|
А
|
П5
|
Б
|
П7
|
|
В
|
|
|
7
|
|
13
|
12
|
|
|
К
|
|
|
|
|
5
|
|
10
|
|
Г
|
7
|
|
|
|
15
|
6
|
11
|
|
А
|
|
|
|
|
|
10
|
|
|
П5
|
13
|
5
|
15
|
|
|
|
8
|
|
Б
|
12
|
|
6
|
10
|
|
|
|
|
П7
|
|
10
|
11
|
|
8
|
|
|
Аналогично предыдущему рассуждению рассматриваем строчку К и определяем, что П5 = Д и П7 = Е. Мы полностью идентифицировали вершины:
|
|
В
|
К
|
Г
|
А
|
Д
|
Б
|
Е
|
|
В
|
|
|
7
|
|
13
|
12
|
|
|
К
|
|
|
|
|
5
|
|
10
|
|
Г
|
7
|
|
|
|
15
|
6
|
11
|
|
А
|
|
|
|
|
|
10
|
|
|
Д
|
13
|
5
|
15
|
|
|
|
8
|
|
Б
|
12
|
|
6
|
10
|
|
|
|
|
Е
|
|
10
|
11
|
|
8
|
|
|
Если мы нанесем на граф длины ребер, то мы не сможем сразу посчитать длину пути из А в К, как мы это делали в предыдущих задачах, так как граф нетривиален:
Применим алгоритм Декстры для поиска кратчайшего пути в графе. Начнем с вершины А и для каждой следующей вершины, анализируя ребра, будем искать кратчайший путь, записывая у вершин метки расстояния из А:
Проанализируем первое ребро из вершины А в Б:
Добавим вершины, связанные Б, то есть В и Г:
Между вершинами В и Г есть ребро. Так как В > Г, проверим возможность обновления метки В: Г + ГВ = 16 + 7 = 23 > В, то есть метку В оставляем прежней и зачеркиваем путь ГВ (он не будет входить в искомый ответ):
Таким образом, у нас сейчас образуются два пути - кандидата на ответ: АБВ = 22 и АБГ = 16. Несмотря на то, что АБГ < АБВ, мы не будем спешить избавляться от АБВ, возможно, при наращивании новых вершин его длина будет меньшей.
Добавим вершины Д и Е с ребрами ВД и ГЕ:
Есть еще два ребра, которые связаны с вновь добавленными вершинами. Начнем с ребра ГД = 15. Так как Д > Г, возможно, надо обновить Д. Г + ГД = 16 + 15 = 31 < Д. Поэтому перечеркиваем ребро ВД и обновляем метку Д = 31: 
Добавим ребро ДЕ = 8. Так как Е < Д, возможно, требуется обновление метки Д. Проверим: Е + ДЕ = 27 + 8 = 35 > Д, поэтому обновление метки не требуется, а путь ДЕ мы перечеркиваем:
Добавим вершину К с путем ЕК = 10:
Добавим последнее ребро ДК = 5. Проверим, требуется ли обновление метки К. Д + ДК = 31 + 5 = 36 < 37. Следовательно, перечеркиваем путь ЕК и получаем новое значение метки К:
Сейчас мы имеем граф, в вершинах которого написаны метки – кратчайшие расстояния от вершины А. По неперечеркнутым путям находим кратчайший путь из А в К: АБГДК.
Ответ: АБГДК
Задача 3.1.6. Путешественник пришел в 08:00 на автостанцию поселка ЛЕСНОЕ и увидел следующее расписание автобусов:
|
Отправление из
|
Прибытие в
|
Время отправления
|
Время прибытия
|
|
Лесное
|
Озерное
|
07:45
|
08:55
|
|
Луговое
|
Лесное
|
08:00
|
09:10
|
|
Полевое
|
Лесное
|
08:55
|
11:25
|
|
Полевое
|
Луговое
|
09:10
|
10:10
|
|
Лесное
|
Полевое
|
09:15
|
11:45
|
|
Озерное
|
Полевое
|
09:15
|
10:30
|
|
Лесное
|
Луговое
|
09:20
|
10:30
|
|
Озерное
|
Лесное
|
09:25
|
10:35
|
|
Луговое
|
Полевое
|
10:40
|
11:40
|
|
Полевое
|
Озерное
|
10:45
|
12:00
|
Определите самое раннее время, когда путешественник сможет оказаться в пункте ПОЛЕВОЕ согласно этому расписанию.
Задача вполне жизненная. Многим приходилось путешествовать с пересадкой. Постройте дерево, в вершинах которого будут населенные пункты со временем прибытия.
В Лесном мы находимся в 8:00. Смотрим строчки расписания:
Ошибка. Первый автобус нам не годится, так как его отправление на 15 минут раньше, чем мы появимся в Лесном:
|
Лесное
|
Озерное
|
07:45
|
08:55
|
Продолжение хода решения.
Нам подходят следующие электрички:
|
Лесное
|
Полевое
|
09:15
|
11:45
|
|
Лесное
|
Луговое
|
09:20
|
10:30
|
Первая приведет нас сразу в пункт назначения, но, возможно, это не самый быстрый вариант. Начнем строить дерево:
Обратите внимание, что в дереве мы отмечаем только время прибытия. Этого нам достаточно.
Смотрим, куда можно поехать из Лугового не раньше, чем в 10:30:
|
Луговое
|
Полевое
|
10:40
|
11:40
|
Ответ: 11:40
Примечание. В нашем случае задачу можно было бы решить и устно, но, поскольку ЕГЭ всё усложняется, то легко может быть задача уже на две пересадки. Использование дерева позволит избежать ошибок.
Задача 3.1.7. Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите ID дяди Корзун П. А.
|
ID
|
Фамилия_И.О.
|
Пол
|
|
ID_Родителя
|
ID_Ребенка
|
|
1072
|
Онищенко А. Б.
|
Ж
|
|
1027
|
1072
|
|
1028
|
Онищенко Б. Ф.
|
М
|
|
1027
|
1099
|
|
1099
|
Онищенко И. Б.
|
М
|
|
1028
|
1072
|
|
1178
|
Онищенко П. И.
|
М
|
|
1028
|
1099
|
|
1056
|
Онищенко Т. И.
|
М
|
|
1072
|
1040
|
|
1065
|
Корзун А. И.
|
Ж
|
|
1072
|
1202
|
|
1131
|
Корзун А. П.
|
М
|
|
1072
|
1217
|
|
1061
|
Корзун Л. А.
|
М
|
|
1099
|
1156
|
|
1217
|
Корзун П. А.
|
Ж
|
|
1099
|
1178
|
|
1202
|
Зельдович М. А.
|
М
|
|
1110
|
1156
|
|
1027
|
Лемешко Д. А.
|
Ж
|
|
1110
|
1178
|
|
1040
|
Лемешко В. А.
|
Ж
|
|
1131
|
1040
|
|
1046
|
Месяц К. Г.
|
М
|
|
1131
|
1202
|
|
1187
|
Лукина Р. Г.
|
Ж
|
|
1131
|
1217
|
|
1093
|
Фокс П. А.
|
Ж
|
|
1187
|
1061
|
|
1110
|
Друк Г. Р.
|
Ж
|
|
1187
|
1093
|
Во второй таблице задано отношение «родитель-ребенок». Зная его, сформулируйте понятие дядя через цепочку отношений «родитель-ребенок». Постройте дерево родства.
Ошибка. Неправильно будет искать дядю по левой таблице, ища однофамильца (дядя может быть со стороны матери, которая меняла фамилию, когда выходила замуж). Также для других родственных отношений можно не смотреть совпадения инициала в отчестве. Единственный путь строго решить задачу – это изучать отношения «родитель-ребенок» по правой таблице.
Дядя – это брат матери или отца. Отношения «брат» у нас нет. Братья имеют общих родителей. Поэтому, прежде чем искать брата, надо найти родителей родителей (то есть бабушек и дедушек).
Корзун П. А. имеет ID = 1217. По второй таблице найдем её родителей:
|
ID_Родителя
|
ID_Ребенка
|
|
1072
|
1217
|
|
1131
|
1217
|
Далее найдем бабушек и дедушек (родителей родителей). То есть ищем 1072 и 1131, которых взяли из левой колонки, уже в правой колонке:
|
ID_Родителя
|
ID_Ребенка
|
|
1027
|
1072
|
|
1028
|
1072
|
У 1131 родители неизвестны.
Посмотрим, кому приходятся родителями 1027 и 1028:
|
ID_Родителя
|
ID_Ребенка
|
|
1027
|
1072
|
|
1027
|
1099
|
|
1028
|
1072
|
|
1028
|
1099
|
Смотрим на левую таблицу и убеждаемся, что 1099 – дядя, а не тётя:
Ответ: 1099
Задача 3.1.8. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите количество человек, у которых есть брат с разницей не более чем в 5 лет.
|
|
Таблица 1
|
|
|
ID
|
Фамилия_И. О.
|
Пол
|
Год рождения
|
|
2053
|
Сухорук К.К.
|
М
|
1975
|
|
2065
|
Лопухова В.А.
|
Ж
|
1980
|
|
2086
|
Зарецкий А.А.
|
М
|
1972
|
|
097
|
Сухорук Е.К.
|
Ж
|
2007
|
|
2118
|
Ларина О.Д.
|
Ж
|
1996
|
|
2124
|
Сухорук И.К.
|
М
|
2001
|
|
2
35
|
Кольцова Т.Х.
|
Ж
|
1995
|
|
2156
|
Рац А.П.
|
М
|
1993
|
|
2181
|
Сухорук Т.Н.
|
М
|
2015
|
|
2203
|
Сухорук П.И.
|
Ж
|
2018
|
|
2052
|
Гнатюк О.А.
|
М
|
1952
|
|
|
Таблица 2
|
|
ID_Родителя
|
ID_Ребенка
|
|
2065
|
2097
|
|
2053
|
2118
|
|
2052
|
2065
|
|
2052
|
2086
|
|
2053
|
2135
|
|
2052
|
2053
|
|
2065
|
2124
|
|
2086
|
2156
|
|
2156
|
181
|
|
2156
|
2203
|
|
Постройте всё родословное древо. Разницу в возрасте считайте вычитанием годов рождения, пренебрегая месяцами, так как они неизвестны.
Начнем строить родословное древо, начиная с самого старого человека - Гнатюка О.А. Используем его ID = 2052 как ID_Родителя и по второй таблице найдем его детей:
Просмотрев колонку ID_Ребенка, убеждаемся, что жена Гнатюка О.А неизвестна (дети Гнатюка в колонке ID_Ребенка присутствуют только один раз).
Найдем теперь детей Гнатюка О.А в колонке ID_Родителя и выпишем из второй колонки их детей (то есть найдем внуков Гнатюка О.А):
Убедимся, что родословное древо странное – у людей нет мужей/жен. Аналогично найдем правнуков:
Отметим овалом тех, кто не единственный ребенок в семье и является мужчиной (то есть приходится братом к кому-нибудь).
Для поколения детей Гнатюка О.А рассмотрим разницу в возрасте, отметив годы рождения:
Разница в возрасте между троими детьми Гнатюка О.А не превышает 5 целых лет (пренебрежем количеством месяцев сверх целого года, так как точные даты неизвестны), следовательно, все трое относятся к искомому множеству.
Проверим следующие две семьи, в которых есть братья:
Пара внуков 2097 и 2124 не годится, так как разница в возрасте между ними 6 лет.
Правнучка 2203 подходит, так как разница в возрасте с её братом 3 года.
Ответ: 4.
