ТЕМА 15

"Представление и считывание данных в разных типах информационных моделей"

Пример 1

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

Решение

Общее количество путей до города Х равно сумме количества путей в каждый из тех городов, из которых есть дорога в Х. При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. Тогда из схемы можно вычеркнуть избыточные дороги. А если город должен лежать на пути, тогда для городов, в которые идут дороги из исходного, в суммах нужно брать только этот город.

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

Введем обозначение: N_Х – количество путей входящих в город Х, тогда:

N_Б = 1(N_Б - количество путей входящих в город Б)

N_Г = 1(N_Г - количество путей входящих в город Г)

N_В = N_А + N_Б + N_Г = 1 + 1 + 1 = 3 (N_В - количество путей входящих в город В и исходящих по каждому пути из него).

N_Д = 3 (N_Д - количество путей входящих в город Д)

N_Ж = 3 (N_Ж - количество путей входящих в город Ж)

N_Е = N_В + N_Д + N_Ж = 3 + 3 + 3 = 9 (N_Е - количество путей входящих в город Е)

N_К = N_Е + N_Д +N_Ж = 9 + 3 + 3 = 15 (N_К - количество путей входящих в город К)

Пример 2

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

Решение

Общее количество путей до города Х равно сумме количества путей в каждый из тех городов, из которых есть дорога в Х. При этом, если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. Тогда из схемы можно вычеркнуть избыточные дороги.

Используя такой способ можно подсчитать последовательно количество путей которые не проходят через город В:

N_Б = 1(N_Б - количество путей входящих в город Б)

N_Г = 1(N_Г - количество путей входящих в город Г)

N_Д = 1 (N_Д - количество путей входящих в город Д)

N_Ж = 1 (N_Ж - количество путей входящих в город Ж)

N_Е = N_Д + N_Г = 1 + 1 = 2 (N_Е - количество путей входящих в город Е)

N_И = N_Г + N_Е = 1 + 2 = 3 (N_И - количество путей входящих в город И)

N_К = N_Ж + N_Д + N_Е + N_И = 1 + 1 + 2 + 3 = 7 (N_К - количество путей входящих в город К)

Пример 3

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

Решение

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

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

Введем обозначение: N_Х – количество путей входящих в город Х, тогда:

N_В = 1 (N_В - количество путей входящих в город В)

N_Г = 2 (N_Г - количество путей входящих в город Г)

N_Б = N_А + N_Г = 1 + 2 = 3 (N_Б - количество путей входящих в город Б)

N_Д = N_Б + N_Г = 3 + 2 = 5 (N_Д - количество путей входящих в город Д)

N_Е = N_Д + N_Г = 5 + 2 = 7 (N_Е - количество путей входящих в город Е)

N_Ж = 7 (N_Ж - количество путей входящих в город Ж)

N_К = N_Д + N_Е + N_Ж = 5 + 7 + 7 = 19 (N_К - количество путей входящих в город К)

Пример 4

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

Решение

Общее количество путей до города Х равно сумме количества путей в каждый из тех городов, из которых есть дорога в Х. При этом, если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. Тогда из схемы можно вычеркнуть избыточные дороги.

Используя такой способ можно подсчитать последовательно количество путей которые не проходят через город Е:

N_В = 1 (N_В - количество путей входящих в город В)

N_Г = N_А + N_В = 1 + 1 = 2 (N_Г - количество путей входящих в город Г)

N_Б = N_А + N_Г = 1 + 2 = 3 (N_Б - количество путей входящих в город Б)

N_Д = 3 (N_Д - количество путей входящих в город Д)

N_Ж = N_Г + N_В = 2 + 1 = 3 (N_Ж - количество путей входящих в город Ж)

N_К = N_Ж + N_Д = 3 + 3 = 6 (N_К - количество путей входящих в город К)

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• ссылка на видеоурок по теме: смотреть

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу