close

Вход

Забыли?

вход по аккаунту

?

ГИА Задание 11

код для вставкиСкачать
способы решения поставленной задачи
 Поиск путей в графе (задание 11)
2012
-
2013 уч.год
Задание 11.
Пример задания 11:
На рисунке –
схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К
. По
каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А
в город К
?
Что нужно знать:
•
если в город R
можно приехать только из городов X
, Y
, и Z
, то число различных путей из города A
в город R
равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть
где число путей из A в Х
число путей из А в Y
число путей из А в Z
•
число путей конечно, если в графе нет циклов –
замкнутых путей
Z
Y
X
R
N
N
N
N
X
N
Y
N
Z
N
1 вариант (подстановки):
•
Начнем считать количество путей с конца маршрута –
с города К
.
•
Обозначим N
X
количество различных путей из города А
в город X
•
Общее число путей обозначим через N
К
1.
В
K можно приехать из Е, Д, Ж или И
, поэтому
N
К
= N
Д
+ N
Е
+ N
Ж
+ N
И (1)
2.
В город Ж
можно приехать только из Е
и В
, поэтому
N
Ж
= N
Е
+ N
В (2)
3.
В город И
можно приехать только из Д
, поэтому N
И
= N
Д (3)
4.
Подставим (2)
и (3)
в (1)
:
N
К
= N
Д
+ N
Е
+ N
Д
+ N
Е
+ N
В
N
К
= N
В
+ 2N
Е
+ 2N
Д
1 вариант (подстановки):
N
К
= N
В
+ 2
N
Е
+ 2
N
Д (1)
9.
В город Д
можно приехать только из Б
и В
, поэтому
N
Д
= N
Б
+ N
В (4)
10.
в город Е
можно приехать только из Г
, поэтому N
Е
= N
Г
(5)
11.
Подставляем (4) и (5)
в (1):
N
К
= N
В
+ 2
N
Г
+ 2
(N
Б
+N
В
)
N
К
= N
В
+ 2
N
Г
+ 2
N
Б
+
2
N
В
N
К
= N
В
+ 2
N
Г
+ 2
N
Б
+
2
N
В
1 вариант (подстановки):
N
К
= N
В
+ 2
N
Е
+ 2
N
Д (1)
9.
В город Д
можно приехать только из Б
и В
, поэтому
N
Д
= N
Б
+ N
В (4)
10.
в город Е
можно приехать только из Г
, поэтому N
Е
= N
Г
(5)
11.
Подставляем (4) и (5)
в (1):
N
К
= N
В
+ 2
N
Г
+ 2
(N
Б
+N
В
)
N
К
= N
В
+ 2
N
Г
+ 2
N
Б
+
2
N
В
N
К
= 3
N
В
+ 2
N
Г
+ 2
N
Б
1 вариант (подстановки):
N
К
= 3
N
В
+ 2N
Г
+ 2N
Б
(1)
12.
По схеме видно, что N
Б
= N
Г
= 1 (6)
N
В
= 1 + N
Б
+ N
Г
= 3 (7)
13.
Подставляем
(6) и
(7) в
(1)
:
N
К
= 3*3 + 2*1 + 2*1=9+2+2=13
Ответ: 13 путей 1 вариант (подстановки):
2 вариант (графический):
1
1
2 вариант (графический):
1
1
1+1+1
(3)
2 вариант (графический):
(1)
(1)
(3)
(1+3)
2 вариант (графический):
(1)
(1)
(3)
(4)
2 вариант (графический):
(1)
(1)
(3)
(4)
(4)
2 вариант (графический):
(1)
(1)
(3)
(4)
(4)
(1)
2 вариант (графический):
(1)
(1)
(3)
(4)
(4)
(1)
(1+3)
2 вариант (графический):
(1)
(1)
(3)
(4)
(4)
(1)
(4)
(4+4+4+1)
2 вариант (графический):
(1)
(1)
(3)
(4)
(4)
(1)
(4)
(13)
•
Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть.
•
Определим количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной вершины А:
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
Г
А
1
Д
БВ
Е
Г
Ж
ВЕ
И
Д
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
Е
Г
Ж
ВЕ
И
Д
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
Е
Г
1
Ж
ВЕ
И
Д
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
4
Е
Г
1
Ж
ВЕ
И
Д
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
4
Е
Г
1
Ж
ВЕ
4
И
Д
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
4
Е
Г
1
Ж
ВЕ
4
И
Д
4
К
ИДЖЕ
3 вариант (по алфавиту):
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
4
Е
Г
1
Ж
ВЕ
4
И
Д
4
К
ИДЖЕ
13
Источники литературы
http://kpolyakov.narod.ru/download/B9.doc
Демонстрационный вариант ГИА 2012 года
1 способ.
1
1
1 способ.
1
1
3
1 способ.
1
1
1
3
1
1 способ.
1
1
1
3
1
1+1+1+1+3
1 способ.
Ответ: 7 путей
1
1
1
3
1
7
1 способ.
Ответ: 7 путей
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
Б
1
Е
Г
1
К
ДБВГЕ
7
2 способ.
Демонстрационный вариант ГИА 2013 года
1 способ.
1 способ.
1
1
1 способ.
1
1
3
1 способ.
1
1
3
4
4
1 способ.
1
1
3
4
4
4+4
1 способ.
1
1
3
4
4
8
Ответ: 8 путей
Ответ: 8 путей
вершина
откуда?
N
Б
А
1
В
АБГ
3
Г
А
1
Д
БВ
4
Е
ГВ
4
К
ДЕ
8
2 способ.
Тренировочная работа 19.10.11 г.
Вариант 1.
1
1
1
1
1
1
2
2
1
1
1
2
3
2
1
1
1
2
3
2
2+1+1+3
1
1
1
2
3
2
7
Ответ: 7 путей
Тренировочная работа 19.10.11 г.
Вариант 2.
1
1
1
1
2
2
1
1
2
3
2
1
1
2
3
2
5
2+3+5
1
1
2
3
2
5
10
Ответ: 10 путей
Диагностическая работа 16.11.11 г.
Вариант 1.
1
1
3
4
14
4
7
содержание
Ответ: 14 путей
Диагностическая работа 16.11.11 г.
Вариант 2.
содержание
Ответ: 13 путей
1
1
3
1+3=4
1
4
1+1+3+4+4=13
Тренировочная работа 01.02.12 г.
Вариант 1.
содержание
Ответ: 7 путей
1
2
3
3
1
1+1+2+3=7
Тренировочная работа 01.02.12 г.
Вариант 2.
содержание
Ответ: 6 путей
1
2
2
3
2
1+2+3=6
Диагностическая работа 20.03.12 г.
Вариант 1.
(1)
(1)
(2)
(2)
(1)
(2)
(2)
(3)
(1)
(2)
(2)
(3)
(6)
(1)
(2)
(2)
(3)
(6)
(9)
Ответ: 9 путей
содержание
Диагностическая работа 20.03.12 г.
Вариант 2.
(1)
(1)
(3)
(4)
(2)
(6)
содержание
Ответ: 6 путей
Тренировочная работа 19.10.12 г.
Вариант 1.
содержание
1
1
1
2
1+1+2=4
2+4=6
4+6=10
Ответ: 10 путей
Тренировочная работа 19.10.12 г.
Вариант 2.
Ответ: 9 путей
1
1
1
2
2
1+1+2+2=6
1+6+2=9
Диагностическая работа 21.11.12 г.
Вариант 1.
содержание
Ответ: 10 путей
1
1
2
1+2=3
1
1+2=3
3+3=6
1
1+3+6=10
Диагностическая работа 21.11.12 г.
Вариант 2.
Ответ: 12 путей
1
1
3
1
1
1+1+3=5
1+5=6
1
1+5+6=12
Тренировочная работа 31.01.13 г.
Вариант 1.
Ответ: 6 путей
1
1
2
2
2+2=4
2
2+4=6
Тренировочная работа 31.01.13 г.
Вариант 2.
Ответ: 10 путей
1
1
2
2
1+2=3
2+2+3=7
3+7=10
Документ
Категория
Методические пособия
Просмотров
89
Размер файла
1 801 Кб
Теги
задание, гиа
1/--страниц
Пожаловаться на содержимое документа