ege-inf.ru / Подготовка к ЕГЭ по информатике 2018

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант №1702

Добавлен 25 мая 2017 в 0:12. Изменён 09 июня 2018 в 20:09. Скачать PDF

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Задание

Схема дорог, связывающая \(n\) городов, имеет следующую структуру: из любого города \(v_{i}\) с номером \(1\leq i<n\) существует дорога в любой город \(v_{j}\), имеющий номер \(i<j\leq n\). По каждой дороге можно двигаться только в одном направлении — из города \(v_{i}\) в город \(v_{j}\) (на схеме показано стрелкой).

Пример такой схемы при \(n=6\) представлен на рисунке.

Сколько существует различных путей из города \(v_{1}\) в город \(v_{n}\), если \(n=10\)?

Схема дорог
Рис. 1. Схема дорог при \(n=6\)

Решение

По индукции можно вывести формулу \(m=2^{n-2}\).

Подробнее...

Ответ

256

Подробнее...