'

Виды информационных моделей: деревья, организационная диаграмма

Понравилась презентация – покажи это...





Слайд 0

Виды информационных моделей: деревья, организационная диаграмма Урок 22


Слайд 1

Деревом – называется связный граф, не содержащий циклов. Графом – называется рисунок, состоящий из нескольких точек (вершин графа) и ребер – отрезков или дуг, соединяющих некоторые вершины.


Слайд 2

Примеры связанных графов, содержащих циклы


Слайд 3

Примеры деревьев


Слайд 4

Применение деревьев, не ограничивается генеалогией К примеру, рассмотрим арифметическое выражение 2*2+11/2 . Каждой операции соответствует два операнда, а результат выполнения операции будет использован в качестве операнда в следующем вычислении или окажется окончательным – равным значению выражения.


Слайд 5

Что общего? Все деревья имеют вершину, ветви. Каждое ветвь дерева является законченным вариантом решения, а всё дерево описывает множество вариантов.


Слайд 6

Рассмотрим задачу:


Слайд 7

Игра Баше Из N мелких предметов (камешков, пуговиц, спичек и т.п.), играющие поочередно берут не менее одной и не более K штук. Выигрывает тот, кто сумеет взять последний предмет.


Слайд 8

Задача: Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй - 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


Слайд 9

Решение: Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры.


Слайд 10

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. Задание: в программе «Живая Родословная» создать дерево для решения следующей задачи:


Слайд 11

Домашнее задание: Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трёх точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выиграет при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


×

HTML:





Ссылка: