Информатика ЕГЭ — решения заданий ФИПИ с ответами

Дороги на графе и в таблице

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем буквенные вершины графа с номерами пунктов таблицы по структуре графа: по числу соединений и взаимному расположению дорог.
2. 2
   Вершине А соответствует пункт 6, а вершине Г — пункт 3.

Ещё 1 шаг — в полном решении

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схема дорог задаёт ориентированный граф: вершины — города, а направленные рёбра — дороги.
2. 2
   Для каждого города последовательно находим максимальную длину пути из А: при переходе по одной дороге к уже найденной длине прибавляем 1.

Ещё 1 шаг — в полном решении

Подсчёт путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных…

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

Ещё 1 шаг — в полном решении

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Рассмотрим маршрут A–B–D–E–F: все необходимые дороги существуют.$$2 + 4 + 3 + 1 = 10$$
2. 2
   Для сравнения, маршрут A–B–D–F имеет длину 11, маршрут A–B–C–D–E–F — 11, а прямой путь A–F — 38. Следовательно, найденный маршрут является кратчайшим.$$10 < 11 < 38$$

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Из пункта A в пункт F можно попасть через пункт E. Прямой дороги между A и F нет.
2. 2
   Рассмотрим маршрут A–D–E–F:$$3 + 4 + 3 = 10$$

Ещё 1 шаг — в полном решении

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Из пункта F можно попасть непосредственно только в пункт E, поэтому последний участок любого маршрута — E–F длиной 4.
2. 2
   К пункту E из A можно добраться по маршруту A–D–E.$$6 + 1 = 7$$

Ещё 2 шага — в полном решении

Протяжённость дороги Б—Д

На рисунке схема дорог $N$-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг…

1. 1
   Сравним структуру графа с таблицей. Число дорог, выходящих из каждой вершины графа, позволяет установить соответствие между буквенными обозначениями и номерами пунктов таблицы.
2. 2
   После сопоставления вершин найдём в таблице значение, соответствующее дороге между пунктами Б и Д.

Ещё 1 шаг — в полном решении

Числа в шестнадцатеричной системе

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $\mathrm{E7}_{16} < x < \mathrm{EF}_{16}$?

1. 1
   Переведём левую границу в десятичную систему счисления:$$\mathrm{E7}_{16}=14\cdot16+7=231$$
2. 2
   Переведём правую границу в десятичную систему счисления:$$\mathrm{EF}_{16}=14\cdot16+15=239$$

Ещё 1 шаг — в полном решении

Подсчёт путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных…

1. 1
   Из схемы дорог выписываются все ориентированные маршруты, которые начинаются в городе Е и заканчиваются в городе Е.
2. 2
   Из рассмотрения исключаются маршруты, содержащие город Е между началом и концом, а также маршруты, в которых какой-либо промежуточный город посещается более одного раза.

Ещё 1 шаг — в полном решении

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Из пункта A можно попасть только в пункт B по дороге длиной 2.$$A\to B: 2$$
2. 2
   Рассмотрим маршрут A–B–D–E–F.$$2 + 7 + 2 + 1 = 12$$

Ещё 1 шаг — в полном решении

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Рассмотрим прямой маршрут A–F.$$20$$
2. 2
   Рассмотрим маршрут A–B–E–F.$$9 + 5 + 4 = 18$$

Ещё 2 шага — в полном решении

Длина дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   По схеме графа сопоставляем буквенные обозначения вершин с номерами пунктов в таблице. Для этого сравниваем количество дорог, соединяющих каждую вершину, и взаимное расположение соседних вершин.
2. 2
   После установления соответствия находим в таблице ячейку, соответствующую дороге между пунктами Б и В.

Ещё 1 шаг — в полном решении

Протяжённости дорог района

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Представим таблицу как матрицу смежности взвешенного графа: ненулевое значение в строке и столбце означает наличие дороги, а само значение — её протяжённость.
2. 2
   Сравниваем степени вершин на рисунке со степенями пронумерованных пунктов в таблице и восстанавливаем соответствие между буквенными обозначениями и номерами пунктов.

Ещё 2 шага — в полном решении

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Из пункта A в пункт F можно попасть напрямую или через промежуточные пункты.
2. 2
   Длина прямого маршрута A–F равна 36. Маршрут A–D–F имеет длину 24.$$36;\quad 4 + 20 = 24$$

Ещё 1 шаг — в полном решении

Сопоставление графа и таблицы

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем вершины графа с номерами пунктов таблицы по структуре дорог: степени вершин и наборы значений в строках таблицы должны совпадать.
2. 2
   После сопоставления определяем длины дорог между пунктами F и G, а также B и C: 21 км и 2 км соответственно.$$21 + 2 = 23$$

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину…

1. 1
   Из пункта A можно попасть в B по дороге длиной 2 или сразу в F по дороге длиной 36.
2. 2
   Путь A–B–D–E–F имеет длину $2 + 4 + 3 + 3 = 12$.

Ещё 2 шага — в полном решении

Длина дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Таблицу и граф нужно сопоставить независимо от номеров: номера пунктов в таблице не соответствуют буквенным обозначениям вершин графа.
2. 2
   Сравниваем для вершин графа количество дорог и значения их протяжённостей с данными таблицы. По совпадению структуры устанавливаем соответствие вершин графа номерам пунктов.

Ещё 1 шаг — в полном решении

Протяжённость дороги между пунктами

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Для каждой вершины графа подсчитываем количество выходящих из неё дорог и сравниваем с количеством заполненных ячеек соответствующей строки таблицы.
2. 2
   По степеням вершин однозначно устанавливаем соответствие между буквенными обозначениями на графе и номерами пунктов в таблице.

Ещё 1 шаг — в полном решении

Протяжённость дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем буквенные вершины графа с номерами пунктов таблицы по числу дорог и их взаимному расположению.
2. 2
   Пункты А и Г соответствуют пунктам 1 и 6 таблицы.

Ещё 1 шаг — в полном решении

Длина дороги между пунктами

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Для каждой вершины графа подсчитываем количество соединённых с ней дорог и сопоставляем полученную структуру с заполненными ячейками таблицы.
2. 2
   По степени вершин и их соседям однозначно восстанавливаем соответствие между буквенными обозначениями на графе и пунктами П1–П7.

Ещё 1 шаг — в полном решении