34. Для грифов, изображенных на рисунках, заполните таблицу.
35. Приведите пример системы, модель которой можно представить в форме грифа. Изобразите соответствующий гриф.
36. Каждый из десяти населенных пунктов соединен автодорогами с девятью другими (без проезда через промежуточные пункты). При этом атобусное сообщение существует только между следующими населенными пунктами: Нахабино и Аникеевка, Прудок и Спас, Ермолино и Любань, Бужарово и Марушкино, Нахабино и Любань, Аникеевка и Ермолино, Спас и Бужарово, Дарна и Кашино, Дарна и Спас, Кашино и Марушкино.
Постройте граф по этому описанию.
Ответьте на вопросы.
1) Сколько всего существует автодорог между населенными пунктами?
45.
2) Можно ли с помощью автобусного сообщения попасть из Бужарово в Дарну?
Да.
3) Можно ли с помощью атобусного сообщения попасть из Нахабино в Прудок?
Нет.
4) С каким наименьшим количеством пересадок можно доехать из Марушкино в Прудок?
2.
5) Какой маршрут можно открыть, чтобы автобусное сообщение существовало между всеми десятью населенными пунктами?
Аникеевка - Спас.
6) Какая дополнительная информация необходима для того, чтобы наладить автобусное сообщение между всеми населенными пунктами с наименьшими затратами?
Стоимость проезда между городами, соединенными автобусным сообщением.
37. Сколько трехзначных чисел можно записать с помощью цифр 0, 1, 2 и 3 при условии, что в записи числа не должно быть одинаковых цифр? Выпишите все такие числа.
Для решения задачи постройте и проанализируйте дерево.
38. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке может стоять одна из бусин A, C, D. На втором - любая бусина с согласной, если первая бусина - с гласной, и любая бусина с гласной, если первая - с согласной. На третьем месте - одна из бусин C, D, Е, не стоящая в цепочке на первом или втором месте. Сколько цепочек можно создать по этому правилу?
Для решения задачи постройте и проанализируйте дерево.
39. На схеме изображены дороги с четырьмя населенными пунктами А, Б, В, Г и указана протяженность этих дорог.
Передвигаться можно только по указанным на схеме дорогам. Определите кратчайшее расстояние между наиболее удаленными друг от друга пунктами. Для решения задачи заполните таблицу.
40. На схеме изображены дороги между насуленными пунктами А, Б, В, Г и указана протяженность этих дорог.
Известно, что кратчайшее расстояние между наиболее удаленными друг от друга пунктами составляет 7. Определите, при каком х это возможно. Для решения задачи заполните таблицу.
41. Шесть торговых точек А, Б, В, Г, Д, Е соединены дорогами с односторонним движением (направление движения указано стрелками, протяженность дорог в км - числами).
Необходимо перевезти груз из точки А в точку Е.
Ответьте на вопросы.
1) Сколько существует различных вариантов маршрута?
Четыре
2) Какой маршрут самый короткий?
АБВЕ
3) Какой маршрут следует выбрать, чтобы по пути посетить все торговые точки?
АБГДВЕ
Для решения задачи постройте и проанализируйте дерево.
42. На соревнованиях по спортивному ориентированию участник должен пробежать от старта до финиша, набрав максимально возможное количество баллов (их число за преодоления того или иного участка указано на рисунке). Определите это количество.
Для решения задачи постройте и проанализируйте дерево.
43. Рассмотрите рисунок. Кружками обозначены вершины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса - длины пути. Рядом с каждой вершиной указана метка - длина кратчайшего пути в эту вершину из вершины А: для вершины А - это 0, для всех других вершин она пока неизвестна и обозначена знаком ∞ ("бесконечность").
Найдите кратчайшее расстояние от верншины А до всех остальных вершин графа, действую в соответствии с приведенным ниже алгоритмом Дейкстры.
1. Обведите вершину А, имеющую минимальную метку (0).
Укажите ее соседей - вершины, в которые идут ребра из вершины А: СРВ.
2. Установите очередность соседних с А вершин (по возрастанию длины пути между А и соседней вершиной):
1) первой по очереди идет вершина В, потому что длина пути между А и В является минимальной;
2) второй по очереди идет вершина D;
3) третьей по очереди идет вершина С.
3. В порядке установленной выше очередности измените метки для соседних с А вершин: вычислите сумму метки вершины А (обведенной вершины) и длины ребра, идущего из нее в очередную соседнюю вершину; если полученная сумма меньше текущей метки очередной вершины, то эту сумму запишите в качестве метки очередной вершины.
После просмотра всех соседей вершины А вычеркните ее из графа.
4. Повторите действия 1-3 для оставшихся вершин, каждый раз выбирая из них вершину, имеющую минимальную метку.
44. У исполнителя Вычислитель есть две команды, которым присвоены номера:
1 - прибавить 1;
2 - умножить на 2.
Сколько существует различных программ, позволяющих преобразовать число 1 в число 10?
Для решения задачи постройте и проанализируйте дерево.
45. У исполнителя Вычислитель есть две команды, которым присвоены номера:
1 - прибавить 4;
2 - вычесть 3.
Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из четырех команд?
46. Да игрока играют в следующую игру. Перед ними лежит кучка из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает в безошибочой игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте, построив дерево игры.
35. Приведите пример системы, модель которой можно представить в форме грифа. Изобразите соответствующий гриф.
36. Каждый из десяти населенных пунктов соединен автодорогами с девятью другими (без проезда через промежуточные пункты). При этом атобусное сообщение существует только между следующими населенными пунктами: Нахабино и Аникеевка, Прудок и Спас, Ермолино и Любань, Бужарово и Марушкино, Нахабино и Любань, Аникеевка и Ермолино, Спас и Бужарово, Дарна и Кашино, Дарна и Спас, Кашино и Марушкино.
Постройте граф по этому описанию.
Ответьте на вопросы.
1) Сколько всего существует автодорог между населенными пунктами?
45.
2) Можно ли с помощью автобусного сообщения попасть из Бужарово в Дарну?
Да.
3) Можно ли с помощью атобусного сообщения попасть из Нахабино в Прудок?
Нет.
4) С каким наименьшим количеством пересадок можно доехать из Марушкино в Прудок?
2.
5) Какой маршрут можно открыть, чтобы автобусное сообщение существовало между всеми десятью населенными пунктами?
Аникеевка - Спас.
6) Какая дополнительная информация необходима для того, чтобы наладить автобусное сообщение между всеми населенными пунктами с наименьшими затратами?
Стоимость проезда между городами, соединенными автобусным сообщением.
37. Сколько трехзначных чисел можно записать с помощью цифр 0, 1, 2 и 3 при условии, что в записи числа не должно быть одинаковых цифр? Выпишите все такие числа.
Для решения задачи постройте и проанализируйте дерево.
38. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке может стоять одна из бусин A, C, D. На втором - любая бусина с согласной, если первая бусина - с гласной, и любая бусина с гласной, если первая - с согласной. На третьем месте - одна из бусин C, D, Е, не стоящая в цепочке на первом или втором месте. Сколько цепочек можно создать по этому правилу?
Для решения задачи постройте и проанализируйте дерево.
39. На схеме изображены дороги с четырьмя населенными пунктами А, Б, В, Г и указана протяженность этих дорог.
Передвигаться можно только по указанным на схеме дорогам. Определите кратчайшее расстояние между наиболее удаленными друг от друга пунктами. Для решения задачи заполните таблицу.
40. На схеме изображены дороги между насуленными пунктами А, Б, В, Г и указана протяженность этих дорог.
Известно, что кратчайшее расстояние между наиболее удаленными друг от друга пунктами составляет 7. Определите, при каком х это возможно. Для решения задачи заполните таблицу.
41. Шесть торговых точек А, Б, В, Г, Д, Е соединены дорогами с односторонним движением (направление движения указано стрелками, протяженность дорог в км - числами).
Необходимо перевезти груз из точки А в точку Е.
Ответьте на вопросы.
1) Сколько существует различных вариантов маршрута?
Четыре
2) Какой маршрут самый короткий?
АБВЕ
3) Какой маршрут следует выбрать, чтобы по пути посетить все торговые точки?
АБГДВЕ
Для решения задачи постройте и проанализируйте дерево.
42. На соревнованиях по спортивному ориентированию участник должен пробежать от старта до финиша, набрав максимально возможное количество баллов (их число за преодоления того или иного участка указано на рисунке). Определите это количество.
Для решения задачи постройте и проанализируйте дерево.
43. Рассмотрите рисунок. Кружками обозначены вершины графа; в кружки вписаны имена вершин. Вершины соединены линиями (ребрами графа); над ребрами обозначены их веса - длины пути. Рядом с каждой вершиной указана метка - длина кратчайшего пути в эту вершину из вершины А: для вершины А - это 0, для всех других вершин она пока неизвестна и обозначена знаком ∞ ("бесконечность").
Найдите кратчайшее расстояние от верншины А до всех остальных вершин графа, действую в соответствии с приведенным ниже алгоритмом Дейкстры.
1. Обведите вершину А, имеющую минимальную метку (0).
Укажите ее соседей - вершины, в которые идут ребра из вершины А: СРВ.
2. Установите очередность соседних с А вершин (по возрастанию длины пути между А и соседней вершиной):
1) первой по очереди идет вершина В, потому что длина пути между А и В является минимальной;
2) второй по очереди идет вершина D;
3) третьей по очереди идет вершина С.
3. В порядке установленной выше очередности измените метки для соседних с А вершин: вычислите сумму метки вершины А (обведенной вершины) и длины ребра, идущего из нее в очередную соседнюю вершину; если полученная сумма меньше текущей метки очередной вершины, то эту сумму запишите в качестве метки очередной вершины.
После просмотра всех соседей вершины А вычеркните ее из графа.
4. Повторите действия 1-3 для оставшихся вершин, каждый раз выбирая из них вершину, имеющую минимальную метку.
44. У исполнителя Вычислитель есть две команды, которым присвоены номера:
1 - прибавить 1;
2 - умножить на 2.
Сколько существует различных программ, позволяющих преобразовать число 1 в число 10?
Для решения задачи постройте и проанализируйте дерево.
45. У исполнителя Вычислитель есть две команды, которым присвоены номера:
1 - прибавить 4;
2 - вычесть 3.
Сколько разных чисел будет получено, если исполнитель выполнит все возможные программы, состоящие из четырех команд?
46. Да игрока играют в следующую игру. Перед ними лежит кучка из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает в безошибочой игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте, построив дерево игры.