Тренировочные задания для подготовки к гиа

Тренировочные задания для подготовки
к ГИА по ИНФОРМАТИКЕ и ИКТ

Решение задания № 11

Задание:

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

Рассмотрим два примера.

1 пример с подробным объяснением.
2 пример с кратким решением. Можно попробовать самим решить и проверить.

ПРИМЕР № 1. Сколько существует различных путей из города А в город К?

13 SHAPE \* MERGEFORMAT 1415

Решение: Оформляем в виде таблицы.


Вершина
Откуда
Сколько путей

Б
A
1

В
АБГ
1+1+2=4

Г
АД
1+1=2

Д
А
1

Е
Б
1

Ж
В
4

З
ГЖ
2+4=6

И
Д
1

К
ЕЖЗИ
1+4+6+1=12


1 столбец – название вершины, в которую приходим из исходной вершины (конец вектора). Можно писать в алфавитном порядке.

2 столбец – название вершин, откуда приходим в данную вершину (начало вектора).

Пример:
а) В вершину Б приходим только из вершины А (Вектор АБ);
б) В вершину В приходим из 3-х вершин А, Б, Г (Вектор АВ, БВ, ГВ);
в) В вершину Г из 2-х вершин А, Д (Вектор АГ, ДГ);
г) В вершину Д приходим только из вершины А (Вектор АД);
д) В вершину Е приходим только из вершины Б (Вектор БЕ);
е) В вершину Ж приходим из Вершины В (Вектор ВЖ);
ж) В вершину З приходим из Вершин Г и Ж (Вектор ГЗ и ЖЗ);
з) В вершину И приходим из вершины Д (Вектор ДИ);
и) В вершину К приходим из вершин Е, Ж, З, И (Вектор ЕК, ЖК, ЗК, ИК).

И так продолжаем заполнять таблицу до последней вершины. В нашем примере – до вершины К.

3 столбец – записываем количество путей до выбранной вершины.

Пример:
а) До вершины Б – 1 путь (Только из вершины А)
б) До вершины Д – 1 путь (Только из вершины А)
в) До вершины Г – 2 пути (Из вершины А и вершины Д; значит 1+1= 2)
г) До вершины В – 3 пути ( Из вершины А, Б и Г; значит 1+1+2= 4 пути (т.к до вершины Г мы нашли 2 пути)
д) До вершины Е – 1 путь ( Из вершины Б; значит 1 путь (т.к. этот путь уже посчитан)
е) До вершины Ж – 1 путь ( Из вершины В; значит 4 пути (т.к. этот путь уже посчитан)
ж) До вершины З – 2 пути (Из вершин Г и Ж; значит 2+4=6 путей, т.к в вершину Г – 2 пути, а в вершину Ж – 4 пути)
з) До вершины И – 1 путь (Из вершины Д; значит 1 путь)
и) До вершины К – 4 пути (Из вершины Е, Ж, З, И; значит 1+4+6+1=12 путей)

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

Так в нашем примере заполняем: 1,4,5 строчки 3-го столбика, а потом 3, 2 строчки, затем 6, 7, 8 и 9 строчки.
В результате заполнения таблицы в последней строке получаем ответ на поставленный вопрос.

Ответ: 12 путей.

ПРИМЕР № 2. Сколько существует различных путей из города А в город К?

13 SHAPE \* MERGEFORMAT 1415

Решение: Оформляем в виде таблицы.

Вершина
Откуда
Сколько путей

Б
А
1

В
АБГ
1+1+1=3

Г
А
1

Д
БВ
1+3=4

Е
Г
1

Ж
ВЕ
3+1=4

И
Д
4

К
ИДЖЕ
4+4+4+1=13


Ответ: 13 путей.






















ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ.

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



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



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




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

15

Приложенные файлы


Добавить комментарий