- Главная
- Разное
- Образование
- Спорт
- Естествознание
- Природоведение
- Религиоведение
- Французский язык
- Черчение
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, фоны, картинки для презентаций
- Экология
- Экономика
Презентация, доклад по информатике на тему Графы. Поиск путей
Содержание
- 1. Презентация по информатике на тему Графы. Поиск путей
- 2. Задача На рисунке – схема дорог, связывающих
- 3. Решение:
- 4. начнем считать количество путей с конца маршрута
- 5. N = NЕ + NЖ + NД + NИ
- 6. N = NЕ + NЖ + NД + NИNЕ = NГ =1
- 7. N = NЕ + NЖ + NД
- 8. N = NЕ + NЖ + NД
- 9. N = NЕ + NЖ + NД
- 10. N = NЕ + NЖ + NД
- 11. N = NЕ + NЖ + NД
- 12. N = NЕ + NЖ + NД
- 13. N = NЕ + NЖ + NД
- 14. N = NЕ + NЖ + NД
- 15. N = NЕ + NЖ + NД
- 16. ЗадачаНа рисунке – схема дорог, связывающих города
- 17. Решение:
- 18. К = Е + Ж + З + И
- 19. К = Е + Ж + З + ИЕ = Б = 1
- 20. К = Е + Ж + З
- 21. К = Е + Ж + З
- 22. К = Е + Ж + З
- 23. К = Е + Ж + З
- 24. К = Е + Ж + З
- 25. К = Е + Ж + З
- 26. К = Е + Ж + З
- 27. К = Е + Ж + З
- 28. Задание для самостоятельной работы:№ 1. На рисунке
- 29. Спасибо за урок!
- 30. Ответы:№ 1 Ответ: 8 № 2 Ответ: 24
Задача На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город
Слайд 2Задача
На рисунке – схема дорог, связывающих города А, Б, В,
Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Слайд 4начнем считать количество путей с конца маршрута – от города К
общее
число путей обозначим через N
N = NЕ + NЖ + NД + NИ
N = NЕ + NЖ + NД + NИ
Слайд 10N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
Слайд 11N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД
Слайд 12N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Слайд 13N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
Слайд 14N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
Слайд 15N = NЕ + NЖ + NД + NИ
NЕ = NГ
=1
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
Ответ: 13
NЖ = NВ + NЕ
NВ = 3 ? NЖ = NВ + NЕ = 3 + 1 = 4
NД = NБ + NВ NБ = 1 ? NД = NБ + NВ = 1 + 3 = 4
NИ =NД ? NИ = 4
Вывод: N = NЕ + NЖ + NД + NИ
N = 1 + 4 + 4 + 4 = 13
Ответ: 13
Слайд 16Задача
На рисунке – схема дорог, связывающих города А, Б, В, Г,
Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Слайд 23К = Е + Ж + З + И
Е = Б
= 1
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = Б + А + Г = 1 + 1 + 2 = 4
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = Б + А + Г = 1 + 1 + 2 = 4
Слайд 24К = Е + Ж + З + И
Е = Б
= 1
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
Слайд 25К = Е + Ж + З + И
Е = Б
= 1
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
Слайд 26К = Е + Ж + З + И
Е = Б
= 1
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
К = Е + Ж + З + И = 1 + 4 + 6 + 1 = 12
Ж = В = Б + А + Г
Г = А + Д
А = 1 Д = 1 ? Г = А + Д = 1 + 1 = 2
? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
К = Е + Ж + З + И = 1 + 4 + 6 + 1 = 12
Слайд 27К = Е + Ж + З + И
Е = Б
= 1
Ж = В = Б + А + Г
Г = А + Д = 1 + 1 = 2
А = 1 ? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
К = Е + Ж + З + И = 1 + 4 + 6 + 1 = 12
Ответ: 12
Ж = В = Б + А + Г
Г = А + Д = 1 + 1 = 2
А = 1 ? Ж = 1 + 1 + 2 = 4
З = Г + Ж = 2 + 4 = 6
И = Д = 1
К = Е + Ж + З + И = 1 + 4 + 6 + 1 = 12
Ответ: 12
Слайд 28Задание для самостоятельной работы:
№ 1. На рисунке – схема дорог, связывающих
города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?
№ 2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
№ 2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
