22. Вот список некоторых легко программируемых игр:

а) Тик-так-тоу (крестики и е) Кости. нолики)1*, ж) Игровые автоматы.

б) Блэк-джек2). з) Рулетка.

в) Ханойская башня3). и) Китайская игра в карты фэн-тэн4).

г) Угадывание слова путем к) Магические квадраты, постепенного добавления л) Бросание кубика с продвижением по одной букве ("балда"). фишек.

д) Ним. м) Калах.

Можно составить программу игры так, чтобы человек вел ее с машиной или машины играли между собой. Интересно запрограммировать для одной играющей стороны какую-нибудь сложную стратегию, а для другой — совершенно иную стратегию или вообще случайные ходы. Выдавая ходы на печать, часто можно наблюдать при этом довольно интересную игру. Вопросы теории игр с вычислительными машинами обсуждаются в книге Д. Спенсера5).

23. В урне находятся 10 черных шаров и 5 красных. Шары вытаскивают по одному и затем кладут обратно. При этом в урну каждый раз добавляется шар того же цвета, что и вынутый. Напишите программу для моделирования 100 извлечений шаров из урны.

24. Миссионеры и людоеды. На одной стороне реки находятся три миссионера, три людоеда и одна лодка, которая вмещает не более двух человек. Если в какой-то момент времени на любом берегу число людоедов превысит количество миссионеров, последние будут съедены. Напишите программу, которая определяла бы стратегию перевозки через реку всех миссионеров и людоедов, обеспечивающую сохранение жизни миссионерам.

25. Шахматные задачи.

а) Пять ферзей. Пять ферзей можно расположить на шахматной доске таким образом, что каждое поле будет находиться под ударом по крайней мере одного ферзя. Напишите программу, определяющую такую расстановку.

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

в) Восемь слонов. Напишите программу, аналогичную предыдущей, но для случая восьми слонов.

26. Кроссворды. Хорошим считается такой кроссворд, который посвящен определенной теме и имеет минимум неиспользуемого пространства. Напишите программу, которая составляет кроссворд, исходя из заданного списка слов.

27. Любителям шахмат. Напишите программу, реализующую передвижение коня по всем 64 клеткам доски так, чтобы он сходил на каждое поле по одному

*" 3) Подробное описание игр этого класса можно найти в книге Бенерджи Р., Теория решения задач. —М.: Мир, 1972.—Прим. перев.

2" 4) Описания этих игр в литературе по теории игр не встречаются. — Прим. перев.

5) Spencer D., Game Playing with Computers, Hayden Book Company, Rochelle Park, N. J., 1976.

разу, или так, чтобы он прошел максимальное расстояние, не пересекая собственных путей. Эти задачи называют "путешествием коня".

28. Представьте, что вы ректор учебного заведения и должны направить каждому студенту персональное письмо. Вам необходимо знать для этого фамилию студента, адрес, группу, в которой он обучается, и его специализацию. Напишите программу, которая считывает указанные данные о студентах и составляет приветственные письма с поздравлениями по случаю начала нового учебного года.

29. Случайные числа. Один простой способ проверки случайности числовых последовательностей состоит в подсчете частоты появления в них каждой цифры. Если последовательность случайна, то вероятность появления каждой из цифр одинакова и равна 0,1. Напишите программу, считывающую 100 случайных цифр и печатающую относительную долю появления каждой из них в общей последовательности.

30. Напишите простую программу, подбирающую брачные пары.

31. Напишите программу, имитирующую 1000 бросаний пары игральных костей и подсчитывающую количество различных выпадающих комбинаций. Сравните результаты работы программы с теоретическими частотами.

32. Напишите программу для вычисления шансов получить определенный расклад при игре в покер.

33. Напишите программу, имитирующую раздачу карт при игре в покер. Промоделируйте 1000 раздач и накопите статистические данные по числу случаев, в которых на одной руке оказывались две, три, четыре и т. д. карт одной масти. Сравните полученные машинные результаты с таблицей теоретических частот возможных раскладов.

34. Любителям бриджа. Напишите программу, имитирующую раздачу карт при игре в бридж и объявляющую масть.

35. Экологическая игра. В журнале Scientific American за февраль 1971 г. описана следующая интересная модель.

Клетка квадрата заполняется на шаге t в случае а) если на шаге /—1 она была пустой, но были заполнены три соседние клетки или б) если на шаге t—1 она была заполнена и были заполнены две или три соседние клетки.

Во всех остальных случаях клетка остается незаполненной или становится пустой. Каждая клетка имеет восемь соседних, как показано на рисунке:

Здесь клетка У граничит с восемью соседними клетками X, а вся структура представляет собой уменьшенную модель шахматной доски. Важно при каждом просмотре наиболее эффективным способом определять пространственное положение занятых и свободных клеток. Напишите программу для моделирования поля размером 15X15 при условии, что в исходной позиции заняты клетки с координатами (3, 8), (4, 7), (5, 7), (5, 8), (5, 9), (10, 7), (10, 8), (10, 9), (11, 7), (12, 8), .(3,2),(4, 3), (5, 1), (5, 2), (5, 3), (9, 1), (9,2), (9, 3), (10, 3), (11,2). Промоделируйте 5 шагов.

36. Задача об инфекции стригущего лишая. Промоделируйте процесс распространения инфекции стригущего лишая по участку кожи размером 11X11 клеток. Предполагается, что исходной зараженной клеткой кожи является центральная. В каждый интервал времени пораженная инфекцией клетка может с вероятностью 0,5 заразить любую из соседних здоровых клеток. По прошествии шести единиц времени зараженная клетка становится невосприимчивой к инфекции, возникший иммунитет действует в течение последующих четырех единиц времени, а* затем клетка оказывается здоровой. В ходе моделирования описанного процесса обеспечьте выдачу на печать текущего состояния моделируемого участка кожи в каждом интервале времени, отмечая зараженные, невосприимчивые к инфекции и здоровые клетки.