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

Задание:

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

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

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

1 пример с подробным объяснением.

2 пример с кратким решением. Можно попробовать самим решить и проверить.

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

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

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 путей.

Задания для самостоятельного решения.

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

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

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

к ГИА по ИНФОРМАТИКЕ и ИКТ

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

Задание:

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

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

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

1 пример с подробным объяснением.

2 пример с кратким решением. Можно попробовать самим решить и проверить.

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

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

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 путей.

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

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

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

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

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