Деревья и Графы. Поиск путей и решений

1.

Деревья и Графы.
Поиск путей и
решений.

2.

Путешественник пришел в 08:00 на автостанцию поселка ЧЕРНОЕ
и увидел следующее расписание автобусов:
Отправление из
Прибытие в
Время отправления Время прибытия
Светлое
Черное
06:15
08:55
Красное
Лазарево
07:15
09:45
Черное
Красное
07:30
11:40
Черное
Лазарево
08:25
10:45
Красное
Светлое
09:05
10:25
Черное
Светлое
09:10
11:50
Лазарево
Красное
10:30
13:00
Лазарево
Черное
11:05
13:45
Светлое
Красное
12:10
13:25
Красное
Черное
13:10
17:25
Определите самое раннее время, когда путешественник сможет
оказаться в пункте КРАСНОЕ согласно этому расписанию.
1) 11:40
2) 13:00 3)13:10
4) 13:25

3.

ЧЕРНОЕ 8:00 → Красное
Черное (8:00)
Кр (7:30)
Кр(10:30)
Л (8:25)
(10:45)
Ч (11:05)
(13:45)
Ответ:
Св (9:10)
(11:50)
Кр (12:10)
(13:25)
4) 13:25
Из
В
Время
отпр.
Время
приб.
Св Ч
06:15 08:55
Кр Л
07:15 09:45
Ч
Кр 07:30 11:40
Ч
Л
08:25 10:45
Кр Св
09:05 10:25
Ч
Св
09:10 11:50
Л
Кр 10:30 13:00
Л
Ч
11:05 13:45
Св Кр 12:10 13:25
Кр Ч
13:10 17:25

4.

Между населёнными пунктами A, B, C, D, E, F, Z построены
дороги, протяжённость которых приведена в таблице.
(Отсутствие числа в таблице означает, что прямой дороги между
пунктами нет.)
Определите длину кратчайшего пути между пунктами A и Z
(при условии, что передвигаться можно только по построенным
дорогам).
1) 28
2) 38
3) 41
4) 43
A
A
B
C
D
E
F
Z
4
6
B
4
C
6
1
1
D
F
15
15
43
E
32
4
6
10
4
6
8
2
Z
43
32
10
8
2

5.

A
A
B
C
D
E
F
Z
B
4
4
6
C
6
1
D
1
4
А
Х
4
6
10
32
B
Х
4
C
Х
1
4
6
8
2
6
Х5
15
6
32
10
43
28 30
Х 37
Х 43
Х Z
F
Z
43
15
15
43
E
8
2
6
32
10
8
2
D 20
Х
4
E 24
Х
F 26 Ответ: 1) 28
Х

6.

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

7.

Вариант 1.
Е
Б
В
Д
+2
Ж
Д
И
→ К +1
→К
А В
Г
К
+3
В
Е
+3
+2
+3
+2
+3
+2
+3
+3
+2
=
13

8.

Вариант 2.
Б (1)
В (3)
Д (1+3=4)
И (4)
Ж (3+1=4)
К (4+4+4+1=13)
Г (1)
Е
Е (1)

9.

Самостоятельно.
Ответ: 14
A→З

10.

У исполнителя Кузнечик две команды:
1. прибавь 3,
2. вычти 2.
Первая из них увеличивает число на экране
на 3, вторая – уменьшает его на 2
(отрицательные числа допускаются).
Программа для Кузнечика – это
последовательность команд. Сколько
различных чисел можно получить из числа
1 с помощью программы, которая содержит
ровно 5 команд?

11.

1. прибавь 3, 2. вычти 2. (из 1 за пять команд)
+3
1 ШАГ
2 ШАГ
+3
+3
-2
-2
+3
-2
-2
3 ШАГ
4 ШАГ
5 ШАГ
Ответ: 16 11 6 1 -4 -9 (ВСЕГО 6 РЕШЕНИЙ)

12.

+3
+3
-2
-2
+3
-2
2
5
3
8
11
0
6
-2
1
-4

13.

1 +3 +3 +3 +3 +3 = 16
1 + 3 + 3 + 3 + 3 – 2 = 11
1 + 3 + 3 + 3 – 2 + 3 = 11
1 + 3 + 3 – 2 + 3 + 3 = 11
1 + 3 – 2 + 3 + 3 + 3 = 11
1 – 2 + 3 + 3 + 3 + 3 = 11
1+3+3+3–2–2=6
1+3+3–2–2–2=1
1 + 3 – 2 – 2 – 2 – 2 = -4
1 – 2 – 2 – 2 – 2 – 2 = -9

14.

У исполнителя Утроитель две команды, которым
присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1,
вторая – утраивает его.
Программа для Утроителя – это последовательность
команд.
Сколько есть программ, которые число 1
преобразуют в число 29?
Ответ обоснуйте.

15.

1. прибавь 1,
2. умножь на 3.
1 29
Количество
программ
Очередное
число
Возможные
следствия
1
2
2 3
3 6
3
4
5
4 9
5 12
6 15

16.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
8, 21
9, 24
10, 27
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

17.

Количество
программ
1 (всегда)
1
1+1 = 2
2
2
1+2 = 3
3
Очередное
число
1
2
3
·
·
Возможные
следствия
2
3
3
6
4
9
4
5 12
5
6 15
6
7 18
7
8 21

18.

Кол-во
Число
Следствия
1
1
2
2
2
3
3
3
5
5
5
7
7
7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 3
3 6
4 9
5 12
6 15
7 18
8 21
9 24
10 27
11
12
13
14
15
9
9
9
12
12
12
15
15
15
18
18
18
23
23
23(ответ)
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
16
17
18
19
20
21
22
23
24
25
26
27
28
29

19.

У исполнителя Калькулятор три команды,
которым присвоены номера:
1. прибавь 1
2. прибавь 2
3. умножь на 4
Сколько есть программ, которые число 1
преобразуют в число 13? Ответ обоснуйте.

20.

Количество
программ
Очередное
число
1
1
2
4
6
10
16
1
2
3
4
2
3
4
8
3
4
5
12
4
5
6
5
6
7
6
7
8
7
8
9
+1
+2 *4

21.

Количество
программ
Очередное
число
27
43
70
113
185
298
8
+1
+2
9 10
9
10
10
11 12
11
12
12
13
13
11
13
*4

22.

(Построение графа)
1. прибавь 1,
2. умножь на 3.
1 29

23.

24.

25.

26.

N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы