Экзаменационный билет №21

1.  Теория игр.

2.    Массивы. 

3.    Два игрока, Петя и Ваня играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого (выполняется условие Фано). Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из за-данных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Пример. Пусть заданы слова {МАК, МЫЛО, РАМА, РАК}. На первом ходу Петя может напи-сать букву М или Р. Пусть он написал букву М. В ответ Ваня может написать А или Ы. В первом случае получается МА, и Петя, дописав букву К, получает слово МАК из заданного набора и выиг-рывает. Во втором случае получается МЫ, Петя вынужден дописать Л и Ваня выиграет вторым ходом, дописав О и получив слово МЫЛО.

Задание 1.

а) Определите, у кого из игроков есть выигрышная стратегия для набора слов {ВАРЕНЬЕ, КОРОВА}. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

б) Определите, у кого из игроков есть выигрышная стратегия для набора слов {НУБНУБ…НУБ, PUMAPUMA…PUMA}. В первом слове 55 раз повторяется слово НУБ, а во втором – 32 раза повто-ряется слово PUMA. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 2

В наборе слов, приведённом в задании 1а, поменяйте местами две буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.

Задание 3

Дан набор слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА}. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии..

Преподаватель: ____________________                                             Ю.В. Терякова

(подпись)

______________________________________________________________________________