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

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

Примеры связанных графов, содержащих циклы I II III IV RU JS US

Примеры деревьев Диск:

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

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

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

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

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

Решение: Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры. 1,2 3,2 9,25,23,63,4 3,2 9,25,23,63,4 1,6 3,6 1,181,8 1,4 3,4 1,121,6

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

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