Простые задачи графы и деревья
Задача 3.1.1. На рисунке приведен граф (множество вершин, соединенных ребрами). Сколько существует путей из вершины А в K?
Задача 3.1.1А. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Задача 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 (при условии, что передвигаться можно только по построенным дорогам).
Задача 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 | | |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Д в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Задача 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 | | | |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.
Задача 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 | | | |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите кратчайший путь из пункта А в пункт К. В ответе перечислите все населённые пункты, через которые проходит путь. Например, путь из Г в Д через Е и К записывается как ГЕКД.
Задача 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 |
Определите самое раннее время, когда путешественник сможет оказаться в пункте ПОЛЕВОЕ согласно этому расписанию.
Задача 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 |
Задача 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 | |
Количество программ и чисел
Задача 3.2.1. Исполнитель может выполнять только две команды, которым присвоены номера:
Прибавь 1
Возведи во вторую степень
Напишите самую короткую программу, которая из числа 1 получает 37. Если таких программ несколько, напишите любую из них.
Задача 3.2.2. У исполнителя «Троечник» две команды, которым присвоены номера:
1. прибавь 3,
2. умножь на 3.
Первая из этих команд увеличивает число на экране на 3, вторая умножает его на 3. Программа - это последовательность номеров команд. Например, 121 - это программа прибавь 3, умножь на 3, прибавь 3. Эта программа преобразует число 1 в число 15.
Запишите программу, которая преобразует число 6 в число 69 и содержит не более 5 команд. Если таких программ более одной, то запишите любую из них.
Задача 3.2.3. Исполнитель может выполнять только две команды, которым присвоены номера:
Прибавь 1
Умножь на 2
Сколько есть программ, которые число 1 преобразуют в число 21?
Задача 3.2.4. Исполнитель может выполнять только две команды, которым присвоены номера:
Прибавь 1
Прибавь 2
Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?
Задача 3.2.5. Исполнитель может выполнять только две команды:
Прибавь 3
Вычти 2
Если в ходе вычислений появляется отрицательное число, то оно не выводится. Сколько различных чисел можно получить из числа 2 с помощью программ, которые содержат ровно 18 команд?
Задача 3.2.6. У исполнителя Калькулятор две команды:
1. умножь на 15,
2. подели на 2.
Первая из них увеличивает число на экране в 15 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4096 с помощью программы, которая содержит ровно 12 команд?
Задача 3.2.7. У исполнителя Калькулятор две команды:
1. прибавь 2
2. прибавь 3.
Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?
Задача 3.2.8. Исполнитель может выполнять только три команды:
Прибавь 2
Прибавь 4
Прибавь 5
Сколько есть программ, которые число 31 преобразуют в число 51?
Задача 3.2.9. Исполнитель Фибо преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.
Программа для исполнителя Фибо — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 20, и при этом траектория вычислений содержит число 9 и не содержит числа 15?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.