Решения и ответы на практические задания №9
Проверь свои результаты
  • Решение.
    Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

    С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
    А = 1;
    Б = А = 1;
    В = А + Б = 1 + 1 = 2;
    Д = А = 1;
    Г = А + Д = 1 + 1 = 2;
    Е = Б + В = 1 + 2 = 3;
    Ж = Д + Г = 1 + 2 = 3;
    З = В + Г + Е + Ж = 2 + 2 + 3 + 3 = 10;
    И = Е = 3;
    К = Ж = 3;
    Л = Е + Ж + З + И + К = 3 + 3 + 10 + 3 + 3 = 22.
     Ответ: 22.
  • Решение.
    Количество путей из города А в город П, проходящих через город М, равно произведению количества путей из города А в город М и количества путей из города М в город П.

    Найдем количество путей из города А в город М:
    А = 1.
    Б = А = 1.
    Г = А + Б = 2.
    Д = А = 1.
    В = Б + Г = 3.
    Е = Г + Д = 3.
    Ж = В + Г + Е = 8.
    К = Ж + В = 11.
    Н = Д + Ж = 9.
    М = Ж + Н = 17.
    Найдем количество путей из города М в город П (при этом М - исходный пункт):
    М = 1.
    Л = М = 1.
    П = Л + М = 2.
    Тогда количество путей из города А в город П, проходящих через город М, равно 17 · 2 = 34.
     Ответ: 34
  • Решение.
    Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчете сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

    С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
    А = 1.
    Б = А = 1.
    В = А + Б = 2.
    Г = А = 1 (В не учитываем, поскольку путь не должен проходить через город В).
    Д = Б = 1 (В не учитываем, поскольку путь не должен проходить через город В).
    Е = Г + Д = 2 (В не учитываем, поскольку путь не должен проходить через город В).
    Ж = Д = 1.
    И = Г = 1.
    К = Д + Ж + И + Е = 5.
     Примечание. Необходимо найти количество различных путей из города А в город К, не проходящих через город В.
     Ответ: 5
  • Решение.
    Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

    С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
    А = 1;
    B = A = 1;
    C = A = 1;
    E = A + B = 2;
    D = A + C = 2;
    G = C + D = 3;
    F = D + E + G = 7;
    H = G + F = 10.
     Ответ: 10
  • Решение.
    Количество путей до города X = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

    С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
    А = 1;
    Б = А = 1;
    В = А + Б = 1 + 1 = 2;
    Д = А = 1;
    Г = А + В = 1 + 2 = 3;
    Е = Б + В = 1 + 2 = 3;
    Ж = Г + Д = 3 + 1 = 4;
    З = В + Г + Е + Ж = 2 + 3 + 3 + 4 = 12;
    И = Е = 3;
    К = Ж = 4;
    Л = Е + Ж + З + И + К = 3 + 4 + 12 + 3 + 4 = 26.
     Ответ: 26
Вернуться к заданиям
Made on
Tilda