upprevious

Up:6 Формулировки заданий
Previous:6.4 Геометрия
Next: Литература

6.5 Игры


1 $\downarrow$ Определить допустимость хода шахматной фигуры на "пустой" доске. Задано: положение фигуры до и после хода, название фигуры и ее цвет.

2. $\downarrow$ Проверить, является ли заданное подмножество клеток шахматной доски клеточным полем.

3. В заданной корректной позиции при игре в шашки определить допустимость хода белых (с учетом взятий).

4. Имеется $n$ костей из нескольких комплектов домино. Выстроить из них правильную последовательность максимальной длины.

5. Запрограммировать игру в "морской бой".

6. Задано число $n$. Подсчитать количество различных последовательностей "рыба", которые возможны в домино с очками от 0 до $n$.

7. Задана правильная последовательность костей домино. Подсчитать количество различных правильных ее продолжений, которые являются "рыбами".

8. При игре в крестики-нолики выигрывает тот, кто первым выстраивает пять крестиков (ноликов) подряд по горизонтали, вертикали или диагонали. Запрограммировать игру в крестики-нолики на прямоугольном клеточном поле.

9. В условиях предыдущего задания определить, является ли начальная конфигурация (т.е. пустое поле) выигрышной для первого игрока.

10. Определить, допустим ли указанный ход королем в заданной корректной шахматной позиции. Заметим, что если после вашего хода ваш король атакован, то ваш ход недопустим.

11. Решить задание 10 для ферзя.

12. Решить задание 10 для ладьи.

13. Решить задание 10 для слона.

14. Решить задание 10 для коня.

15. Решить задание 10 для пешки.

16. На прямоугольном клеточном поле размером $n$ на $n$ расставить $n$ ферзей так, чтобы они не били друг друга.

17. Решить предыдущее задание, заменив ферзей сверхферзями.

18. Для заданного клеточного поля найти все размещения наименьшего числа ферзей таким образом, чтобы они били все его свободные поля.

19. Решить задание 18 для сверхферзей.

20. Решить задание 18 для ладей.

21. Решить задание 18 для слонов.

22. Обойти прямоугольное клеточное поле конем, побывав в каждой клетке ровно один раз. Заданы размеры поля и начальное положение коня.

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

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

25. Решить задание 24 для слона.

26. Решить задание 24 для ферзя.

27. Решить задание 24 для короля.

28. $\downarrow$ Задано описание шахматной позиции в обычной шахматной нотации. Например, "белые: Кр g1, Л f1, пп f2, g2, h3; черные: Кр b8, К e5, С e6, Ф a2, пп a7, b7". По описанию позиции напечатать изображение этой позиции, содержащее поле, разбитое на клетки подходящего размера, внутри которых записано название фигуры и ее цвет (для занятых в позиции клеток).

29. Заданы целые n,k и квадратное клеточное поле размером 2n x 2n  . Назовем раскраску части клеток поля правильной, если справедливы следующие два свойства:

(1) четно количество закрашенных клеток на каждой горизонтали, вертикали и диагонали;

(2) раскраска является симметричной относительно вертикальной линии, разделяющей поле пополам. Построить $k$ таких правильных раскрасок, при которых закрашено ровно $n$ клеток.

30. Найти покрытие клеточного поля $A$ полями $B$, имеющими вид ленты из двух клеток. Например, лента из четырех клеток покрывается полями $B$ единственным способом, а поле

вообще нельзя покрыть полями $B$.

31. Решить предыдущее задание для случая, когда $B$ -- это лента из трех клеток.

32. Решить задание 30 для случая, когда $B$ -- это лента из четырех клеток.

33. Задано целое число $n$. Построить $n$ различных магических квадратов размером , составленных из костей одного комплекта домино. Кости располагать только горизонтально.

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

35. Проверить, можно ли заданную целочисленную матрицу составить из костей одного комплекта домино.

36. Заданы два числа $n$ и $k$. Построить $k$ различных латинских квадратов размером .

37. Два латинских квадрата называются ортогональными, если в результате наложения одного на другой получается такой квадрат (его элементы -- пары чисел), в котором каждое число из первого квадрата появляется ровно один раз в паре с каждым числом из второго квадрата. По заданному латинскому квадрату размером и целому $k$ построить $k$ различных ортогональных заданному латинских квадратов того же размера.

38. Задано квадратное клеточное поле размером и число $k$. Построить $k$ различных разрезов этого поля на две равные по форме части. Линия разреза должна быть неразрывной и проходить по границам клеток.

39. Имеется прямоугольный пирог, состоящий из клеток, причем нижняя левая клетка пирога отравлена. Каждый из двух соперников по очереди выбирает какую-нибудь клетку пирога и съедает ее вместе со всеми клетками, расположенными правее и выше выбранной. Проигрывает тот, кто съедает отравленную клетку. Определить, является ли начальная конфигурация выигрышной для первого игрока.

40. $\uparrow$ В игре на орграфе два игрока поочередно накрывают белыми (соответственно, черными) фишками вершины орграфа. Игрок при своем ходе может накрыть фишкой любую из свободных вершин, хотя бы один предшественник которой накрыт фишкой противника; первым ходом белые накрывают любую вершину. Проигрывает тот, кто при своем ходе не может выставить фишку в соответствии с правилами игры. Определить, является ли начальная конфигурация игры на заданном орграфе выигрышной для белых.

41. $\downarrow$ Задано прямоугольное клеточное поле и число $k$. Построить $k$ различных непрерывных разрезов этого поля на два клеточных поля равной площади.

42. Задан лабиринт, составленный из $n$ комнат, между которыми есть $m$ дверей. Среди них двери являются внутренними (они соединяют соседние комнаты) и две -- внешними: вход и выход в лабиринт. Найти кратчайший (по числу дверей) путь от входа в лабиринт к его выходу.

43. В условиях предыдущего задания некоторые комнаты объявлены опасными. Найти какой-нибудь путь в лабиринте от входа к выходу, не проходящий через опасные комнаты.

44. По заданному построить $k$ различных упорядоченных последовательностей костей из одного комплекта домино (т.е. кости в таких правильных последовательностях упорядочены по возрастанию количества очков). Например, последовательность

-- упорядоченная, а

-- нет.

45. Запрограммировать игру в ним для заданной начальной конфигурации.

46. Определить, является ли заданная начальная конфигурация игры в ним выигрышной для первого игрока.

47. $\downarrow$Таблица конфигурации при игре в ним получается выписыванием друг под другом двоичных представлений количеств фишек в каждом ряду с выравниванием разрядов по правому краю таблицы. Например,


 

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

48. Правила игры в тик-так отличаются от правил игры в ним лишь тем, что на каждом ходе можно брать только рядом стоящие фишки одного ряда. Запрограммировать игру в тик-так.

49. Дана последовательность, состоящая из четного число ячеек, каждая из которых может быть пустой или содержать один из символов $A$ или $B$. Конфигурация содержимого последовательности считается допустимой, если в ней ровно две пустые клетки и они соседние. Допустимое преобразование последовательности -- это совместное перемещение в пустые клетки содержимого двух любых соседних (между собой) непустых ячеек с сохранением порядка расположения перемещаемых символов. Для заданной допустимой начальной конфигурации проверить, есть ли последовательность допустимых преобразований, позволяющая достичь так называемой правильной конфигурации, в которой все символы $A$ расположены левее всех символов $B$.

50. В условиях предыдущего задания найти последовательность допустимых преобразований, достигающую правильную конфигурацию за минимальное число преобразований.

51. В условиях задания 49 найти множество всех конфигураций, которые можно достичь из начальной не более, чем за заданное число допустимых преобразований.

52. Заполнить матрицу размера 5 на 5 цифрами таким образом, чтобы цифры в строках и столбцах не повторялись, совпадали суммы цифр по столбцам и по строкам, а также были бы простыми все пятизначные числа, изображенные строками и столбцами матрицы.

53. Задана квадратная целочисленная матрица. Среди всех путей от левого верхнего угла матрицы к ее правому нижнему, составленных из переходов от клеток к их соседям в столбцах или строках, найти минимальный по сумме чисел в пройденных клетках.

54. Клеточное игровое поле имеет квадратную форму и состоит из девяти одинаковых клеток, на каждой из которых может быть размещена одна фишка. Всего участвует в игре восемь фишек. Пять фишек белого цвета, одна зеленая, одна черная и одна красная фишка. За один ход игры любая фишка может быть перемещена по горизонтали или вертикали на соседнюю клетку, если она пуста (без фишки). Задача программы состоит в том, чтобы по произвольным двум заданным расположениям фишек на поле и любому заданному целому числу $n$ определить, можно ли перейти из одного расположения к другому не более, чем за $n$ шагов.

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

56. Запрограммировать игру, в которой два участника по очереди кладут круглые фишки на прямоугольный стол. Проигрывает тот, кому некуда положить фишку.

57. Про каждую из заданных $n$керамических плиток известны цвета, в которые окрашены ее бока: верх, правая сторона, низ и левая сторона плитки. Определить, можно ли сложить из плиток квадрат заданного размера m x m правильным образом, т.е. чтобы совпадали цвета соприкасаюшихся сторон плиток.

58. В условиях предыдущего задания определить, можно ли, используя все плитки, сложить правильным образом какой-нибудь прямоугольник.

59. Задано множество из $n$ кубиков, грани которых окрашены в заданные $n$ цветов. Определить, можно ли кубики выстроить в один вертикальный столбик, чтобы каждый цвет появлялся ровно один раз на каждой из четырех сторон столбика.

60. Заданы логическая матрица $A$ размера и целое число $k$. Проверить, можно ли заменой на True не более $k$ элементов матрицы, привести ее к виду, в котором элементы True обладают свойством связности, т.е. от любого элемента True можно прийти к любому другому элементу True, двигаясь на каждом шаге от текущего элемента к одному из его соседей в матрице по горизонтали или по вертикали.

61. В условиях предыдущего задания выделить в матрице $A$ прямоугольник, состоящий из не менее $k$ элементов и обладающий свойством связности элементов True.

62. В условиях задания 60 найти покрытие всех True (и только True) элементов матрицы $A$ не более чем $k$ прямоугольниками.

63. В условиях задания 60 найти такую перестановку столбцов в матрице $A$, чтобы внутри любой строки не находилось более чем $k$ блоков из последовательно идущих True элементов.

64. Установить максимально возможное время, которое могут "убить" игроки, играя друг с другом в игру в города.

65. Проверить, может ли игра в города продолжиться более 20 минут, если игроки начнут игру с заданного города.

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

67. Установить, может ли при игре в города первый игрок так выбирать города при своем ходе, чтобы у противника на каждом ходе было не более одного продолжения.

68. По заданным положительным целым числам $n$ и $m$ найти минимальное количество -коней, которое требуется для контроля заданного ограниченного клеточного поля.

69. По заданным положительным целым числам $n$ и $m$ найти минимальное количество -коней, которое требуется для контроля бесконечной полосы заданной ширины.

70. По заданным положительным целым числам $n$ и $m$ найти минимальное количество -коней, которое требуется для контроля бесконечного во все стороны клеточного поля.

71. Расположение фигур на клеточном поле размером $n$ на $n$ описано последовательностью , в которой для любого $i$ элементы -- это коды $i$-й строки и $i$-го столбца соответственно, описывающие распределение фигур в строках и столбцах клеточного поля по следующему правилу. Если в строке (столбце) клеточного поля имеется $n$ групп, образованных из фигур, расположенных в соседних клетках, и разделенных между собой одной или несколькими незанятыми клетками, то кодом указанной строки (столбца) является последовательность чисел , в которой -- это количество фигур в -й по порядку группе, если рассматривать группы слева направо (сверху вниз). Требуется восстановить расположение фигур на клеточном поле по закодированной информации о распределении их в строках и столбцах.

72. Обработка каждой из $k$ деталей происходит в течение некоторого непрерывного отрезка времени. Расписанием работ во временном интервале от $n$ до $m$, где $n$ и $m$ - заданные целые числа, называется множество из $k$ пар целых чисел, описывающих моменты начала и окончания обработки каждой детали. Оно является $s$-правильным, если в любой момент времени не обрабатывается больше $s$ деталей. По заданным расписанию работ и целому числу $s$ требуется проверить, что заданное расписание является $s$-правильным, и перечислить все интервалы времени, когда нарушается $s$-правильность расписания.

73. В условиях предыдущего задания удалить из заданного расписания наименьшее число деталей так, чтобы получить $s$-правильное расписание.

74. В условиях задания 72 проверить, можно ли сделать заданное расписание $s$-правильным, если разрешено сдвигать время начало обработки любой детали.

75. В условиях задания 72 проверить, можно ли получить $s$-правильное расписание работ, если увеличить $m$ в два раза и разрешить сдвигать время начала обработки каждой второй детали.

76. Запрограммировать игру Сима. Игра разыгрывается на плоскости, на которой обозначены вершины правильного шестиугольника. Каждый из игроков при своем ходе соединяет отрезком две еще не соединенные вершины. Проигрывает тот, кто первым построит треугольник из своих собственных отрезков.

77. Запрограммировать игру Бергсона, в которой два участника по очереди берут спички из кучки. Каждый игрок при своем ходе берет по крайней мере одну и не более чем вдвое больше, чем взял предыдущий игрок. Выигрывает тот, кто берет последнюю спичку.

78. Запрограммировать игру Кейлеса, которую разыгрывают два участника с фишками, расположенными в один ряд. Каждый игрок на своем ходе забирает одну фишку, либо две соседние (не разделенные другими фишками). Выигрывает тот, кто берет последнюю фишку.

79. Решить предыдущее задание для случая нескольких исходных рядов фишек.

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

81. Решить предыдущее задание, если фишке разрешается ходить как по горизонтали (но только вперед), так и по вертикали (вверх и вниз), а каждый игрок располагает по две фишке в каждой строке.

82. Запрограммировать игру, в которой два игрока по очереди называют даты заданного года. Первый игрок сообщает какую-нибудь дату января. Каждый игрок на своем ходе называет более позднюю дату, увеличивая либо день месяца, либо сам месяц, но не то и другое сразу. Первый, кто доберется до 31 декабря, выигрывает. Программа должна проверять осмысленность предлагаемых дат.

83. Решить предыдущее задание, если учитывается еще и год, т.е. игра начинается с даты января 1 года и завершается 31 декабря 2001 года.

84. (Палиндром.) Из заданного множества слов сложить предложение, которое является палиндромом (т.е. совпадает со своим обращением) с точностью до пробелов.
П р и м е р ы:
А РОЗА УПАЛА НА ЛАПУ АЗОРА,
АРГЕНТИНА МАНИТ НЕГРА,
ЧИН ЗВАН МЕЧЕМ НАВЗНИЧ.

85. Решить предыдущее задание, если разрешается для построения полиндрома использовать не все слова.

86. (Анаграмма.) Из заданного множества слов сложить предложения, которые являются анаграммами (т.е. получаются друг из друга перестановками букв) с точностью до пробелов.

87. Решить предыдущее задание, если при построении предложений анаграмм можно использовать не все слова.

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

89. В условиях предыдущего задания разместить по белым клеткам буквы таким образом, чтобы образовать кроссворд из указанного множества слов.

90. Задана шахматная позиция, в которой у черных только король, а у белых король и пешка. Проверить, является ли она выигрышной для белых.

91. Прямоугольный лабиринт состоит из одинаковых квадратных комнат, некоторые из которых имеют двери в соседние. Определить, есть ли путь, соединяющий две указанные комнаты.

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

93. В условиях задания 91 подсчитать количество различных путей, соединяющих две указанные комнаты.

94. В условиях задания 91 определить, есть ли в лабиринте хотя бы один замкнутый маршрут, проходящий через заданное число комнат.

95. В условиях задания 91 найти все замкнутые маршруты, не проходящие через одну и ту же комнату дважды.

96. Запрограммировать игру "захват территории".

97. Для игры "захват территории" проверить, является ли начальная конфигурация выигрышной для первого игрока.

98. По заданной начальной конфигурации игры "захват территории" найти минимальное число шагов, через которые игра может завершиться.

99. Решить задание 97, если игрок при своем ходе может перекрасить свою область в любой из шести цветов, за исключением цвета своей области и цвета области противника.

100. Решить задание 98, если правила игры "захват территории" меняются следующим образом: при своем ходе игрок не может сохранить цвет своей области и не может окрасить ее в цвет области противника.
 

Up:6 Формулировки заданий
Previous:6.4 Геометрия
Next: Литература


© В.Н. Касьянов,Е.В.Касьянова, 2004