- таблица как структура организации данных
- знакомство с теорией игр
- уметь представлять данные в виде таблицы
- знать, что такое игра, выигрышный (проигрышный) ход, стратегия
- уметь определить выигрышную стратегию в игре, представить игру в виде дерева или таблицы
- Что такое модель?
- Приведите примеры организации данных в виде графа.
- Какие задачи помогают решать графы и деревья?
- Какая связь между графом и таблицей?
Таблица как структура организации данных
Мы уже познакомились с организацией данных в виде графа и дерева. Ещё одной наглядной структурой представления данных является таблица.
Таблица состоит из строк и столбцов, на пересечении которых находятся ячейки. Табличная форма является основой решения множества задач.
Таблица, в которой содержится информация о свойствах отдельных объектов, относящихся к одному классу, называется «объект-свойство».
Таблица, в которой содержится информация о некотором одном свойстве пар объектов, называется «объект-объект».
Таблица, в которой отражается наличие или отсутствие связей между отдельными элементами некоторой системы, называются двоичными матрицами.
Любую структуру данных можно свести к табличной форме. Поэтому табличный способ представления данных является самым универсальным.
Пример 1
Рис. 1. Пример 1
Решение
Для представления графа в виде матрицы смежности необходимо сопоставить данные таблицы с вершинами графа. У нас 5 вершин, значит, в таблице будет 6 строк и 6 столбцов. Далее при наличии ребра между вершинами графа на пересечении названий этих вершин пишем 1. Получаем следующую таблицу.
Таблица 1. Пример 1 (решение)
|
|
А
|
В
|
С
|
D
|
E
|
|
A
|
|
1
|
|
|
|
|
B
|
1
|
|
1
|
1
|
1
|
|
C
|
|
1
|
|
1
|
|
|
D
|
|
1
|
1
|
|
1
|
|
E
|
|
1
|
|
1
|
|
Знакомство с теорией игр
Теория игр — это математический метод для изучения оптимальных стратегий в играх.
Игра — это процесс, в котором принимают участие две стороны, ведущие борьбу за свои интересы.
Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как будет играть противник.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Выигрышная стратегия может быть только у одного игрока.
В теории игр принято описывать стратегии игроков, т. е. рассматривать все ходы, которые игрок может сделать в любой ситуации при различной игре противника. Игра выступает как математическая модель некоторой ситуации, в которой участники ведут борьбу за свои интересы.
В игре всегда есть правила:
- игроков должно быть больше одного;
- интересы игроков не должны совпадать;
- результат каждого игрока зависит от поведения других игроков;
- правила заранее известны всем игрокам.
Игру удобно представлять как в виде дерева ходов, так и с помощью таблицы.
Пример 2
Два игрока, Денис и Андрей, играют в игру. Перед ними лежит куча конфет. Дети ходят по очереди. Первый ход делает Денис. За один ход он может выполнить одно из следующих действий:
- добавить в кучу одну конфету;
- увеличить количество конфет в куче в 2 раза.
У каждого игрока есть неограниченное количество конфет. Игра завершается, когда количество конфет в куче станет больше 35. Победителем считается игрок, который сделал последний ход.
Пусть в начальный момент в куче X конфет, 1 ≤ X ≤ 35.
- Найдём, при каком X Денис может выиграть первым ходом.
- Найдём, при каком X Денис имеет выигрышную стратегию, при чём он не может выиграть первым ходом, но может выиграть вторым ходом, независимо от того, как будет ходить Андрей.
Решение
- Чтобы выиграть первым ходом, Денису необходимо получить в куче X = 36. У Дениса есть два хода: прибавь один (+1) и умножь на два (∗2). Поэтому получить нужный результат он может из числа 35 (ходом прибавь один) и 18 (ходом умножь на 2). При этом выигрышным будет любое количество конфет Х ≥ 18 (ход умножь на 2). Т. е. Денис может выиграть, если X = 18, 19 … 35 — это его выигрышные позиции. Для выигрыша ему достаточно увеличить количество конфет в 2 раза. При меньших значениях за один ход нельзя получить нужное количество конфет в куче.
- При X = 17 после первого хода Дениса выигрывает Андрей любым ходом. Это проигрышная позиция для Дениса. Поэтому Денису нужно перевести в неё Андрея.
Таблица 2. Пример 2 (2)
|
Денис
|
|
Андрей
|
Денис
|
|
16(+1)
|
17
|
18(+1)
|
36(*2)
|
|
35(*2)
|
36(+1)
|
Единственный способ это сделать — увеличить на 1 кучу из 16 камней. Поэтому ответ будет Х = 16.
Упражнение 1
Маша и Даша играют в игру. У них есть 8 конфет. За один ход игрок может взять 1 или 2 конфеты из кучи. Выигрывает тот, кто своим ходом забирает последнюю конфету. Постройте дерево игры для этой задачи.
Упражнение 2
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 69. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 69 или больше камней. В начальный момент в первой куче было 7 камней, во второй куче — S камней, 1 ≤ S ≤ 59. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
Вопрос 2. Укажите минимальное значение S, при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Итоги
- Теория игр позволяет моделировать решение множества задач из экономики, политологии, искусственного интеллекта и др. областей, где нужно учитывать поведение человека в различных ситуациях.
- Игра — это процесс, в котором принимают участие две стороны, ведущие борьбу за свои интересы.
- Игра может быть представлена в виде дерева или таблицы.
- Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.
Контрольные вопросы
- Как вы думаете, что является более наглядной формой представления данных — граф или таблица?
- Почему для компьютерной обработки данных предпочтительно представлять её в форме таблицы?
- Что такое игра?
- Что такое выигрышная стратегия?
Упражнение 1
|
8 конфет
|
1 ход 1 игрок
|
2 ход 2 игрок
|
3 ход 1 игрок
|
4 ход 2 игрок
|
5 ход 1 игрок
|
|
7
|
6
|
5
|
4
|
3
|
|
|
2
|
|||||
|
3
|
2
|
||||
|
1
|
|||||
|
4
|
3
|
2
|
|||
|
1
|
|||||
|
2
|
1
|
||||
|
выиграл
|
|||||
|
5
|
4
|
3
|
2
|
||
|
1
|
|||||
|
2
|
1
|
||||
|
выиграл
|
|||||
|
3
|
2
|
1
|
|||
|
выиграл
|
|||||
|
1
|
выиграл
|
||||
|
6
|
5
|
4
|
3
|
2
|
|
|
2
|
выиграл
|
||||
|
3
|
2
|
выиграл
|
|||
|
1
|
|||||
|
4
|
3
|
2
|
выиграл
|
||
|
1
|
|||||
|
2
|
1
|
|
|||
|
выиграл
|
|
Упражнение 2
- 16
- 30
