Задание 22. ЕГЭ-2014 - Задание B9: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

1. Задание#T15836

На рисунке – схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать ответ

Это задание решали 271 раз. С ним справились 7% пользователей.

2. Задание#T15793

На рисунке – схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать ответ

Это задание решали 10 раз. С ним справились 40% пользователей.

3. Задание#T15765

На рисунке – схема дорог, связывающих города По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать ответ

Это задание решали 90 раз. С ним справились 43% пользователей.

4. Задание#T15522

На рисунке – схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать разбор и ответ

Решение основывается на следующем правиле.

Правило сложения. Пусть дан ориентированный граф, не содержащий циклов, и из вершины этого графа выходит ребра

которые ведут соответственно в вершины

и Пусть далее из вершины в вершину ведет

путей, из вершины в вершину ведет

путей. Пусть – количество путей из вершины в вершину . Тогда

Это правило, естественно, может быть переформулировано для любого количества ребер, выходящих из данной вершины.

Имея в виду это правило, построим такую таблицу:

Вершина

Куда выход

–

К-во путей

Во второй строке перечислены вершины, в третьей для каждой вершины указано, куда ведут ребра, выходящие из этой вершины. В четвертой строке будем записывать количество путей из каждой вершины в вершину

эти количества будем вычислять, пользуясь правилом сложения.

Из самой вершины есть ровно один путь в себя – это «пустой путь».

Порядок обработки вершин определяется следующим правилом: к моменту обработки вершины должно быть известно количество путей для всех вершин, куда из данной вершины ведут ребра. Порядок, в котором вершины указаны в таблице, этому правилу соответствует.

Заполняя таблицу слева направо, пользуясь правилом сложения, получим:

Вершина

Куда выход

–

К-во путей

Ответ: 49

Это задание взято из Яндекс.ЕГЭ

Это задание решали 73 раза. С ним справились 7% пользователей.

5. Задание#T15501

На рисунке – схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать разбор и ответ

Решение основывается на следующем правиле.

Правило сложения. Пусть дан ориентированный граф, не содержащий циклов, и из вершины этого графа выходит ребра

которые ведут соответственно в вершины и Пусть далее из вершины в вершину ведет

путей, из вершины в вершину ведет

путей. Пусть – количество путей из вершины в вершину Тогда

Имея в виду это правило, построим такую таблицу:


Вершина
Куда выход	—
К-во путей

эти количества будем вычислять, пользуясь правилом сложения. Из самой вершины есть ровно один путь в себя – это «пустой путь».


Вершина
Куда выход	—
К-во путей

Ответ: 15

Это задание взято из Яндекс.ЕГЭ

Это задание решали 12 раз. С ним справились 58% пользователей.

6. Задание#T15481

На рисунке – схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать ответ

Это задание решали 14 раз. С ним справились 50% пользователей.

7. Задание#T13818

На рисунке — схема дорог, связывающих города

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города в город

Показать разбор и ответ

Пусть — количество путей, ведущих из в

— количество путей, ведущих из в

Тогда

Очевидно,

Подсчет количества

путей из в основывается на следующем правиле.

Правило сложения.

Пусть дан ориентированный граф, не содержащий циклов, и из вершины этого графа выходит ребра

которые ведут соответственно в вершины и Пусть далее из вершины в вершину ведет

путей, из вершины в вершину ведет

путей. Пусть — количество путей из вершины в вершину Тогда

Имея в виду это правило, построим такую таблицу:


Вершина
Куда выход
К-во путей

эти количества будем вычислять, пользуясь правилом сложения. Из самой вершины есть ровно один путь в себя — это «пустой путь».

Заполняя таблицу слева направо, пользуясь правилом сложения, получим:


Вершина
Куда выход
К-во путей

Таким образом,

По формуле

Ответ: 48

Это задание решали 81 раз. С ним справились 47% пользователей.

0 баллов сегодня

дней без пропуска

сб

вс

пн

вт

ср

чт

пт