Тесты и результаты. [885] Первый игрок сообщает какую-нибудь дату января

1) 1, 12, 8, 3, 11. 10. 2) 2, 6, 14, 5, 4, 7, 30. 20.

[885] Первый игрок сообщает какую-нибудь дату января. Каж­дый игрок в очередном ходе называет более позднюю дату, увели­чивая либо календарную дату в месяце, либо месяц, но не то и дру­гое сразу. Выигрывает тот, кто первым доберется до 31 декабря. Осуществите реализацию вариантов " игрок -игрок" и " ЭВМ -игрок". Найдите оптимальную стратегию игры для ЭВМ.

Второй уровень

[886] На доске из 3*3 клеток в угловых клетках стоит по одному коню: вверху -два белых, внизу - два черных. Составьте программу обмена местами всех коней. Продемонстрируйте на экране ход игры.

[887] На шахматной доске стоят две фигуры с координатами (х1; у1), (х2; у2). Стоит также конь другого цвета (х3; у3). Перемещая коня, нужно найти такое его расположение, в котором он бьет обе фигуры. Укажите маршрут коня или установите, что такой позиции не существует.

[888] На шахматной доске стоит ферзь F(x1; y1), ладья L(х2; у2) и конь К(х3; у3). В исходной позиции конь может находиться под бо­ем хотя бы одной из этих фигур. Укажите маршрут коня в новую позицию, из которой он может бить и ферзя, и ладью. При этом нельзя проходить через поля, находящиеся под боем хотя бы одной из фигур, и нельзя никакое поле проходить дважды.

[889] Бумажная полоска разбита на n клеток. Двое играющих по очереди выбирают и зачеркивают k (k< n) пустых смежных клеток. Выигрывает сделавший последний ход. Напишите программу, отражающую и контролирующую ход игры двух игроков.

[890] " Игра Баше". Имеется k камней. Двое играющих берут эти камни по очереди, причем за один ход можно взять от одного до трех камней. Проигрывает игрок, взявший последний камень. При­думайте оптимальную стратегию для второго игрока, если за него играет ЭВМ.

[891] Задумано число от 1 до 100. Составьте программу, которая бы угадывала число за наименьшее число вопросов, если все ответы будут правдивыми, кроме одного ответа, являющегося ложным. Задаются вопросы типа: " Принадлежит ли некоторое число такому-то множеству? " Возможны только ответы типа: " Да", " Нет".

Третий уровень

[892] Определите, является ли допустимым ход шахматной фигу­ры на пустой доске, если заданы положение фигуры до и после хо­да, название фигуры и ее цвет.

[893] Даны два коня на шахматной доске К1(х1; у1), К2(х2; у2). Оба последовательно совершают ходы. Определите маршрут каж­дого коня, если конь не может в маршруте дважды проходить одно и то же поле, так, чтобы через k ходов они заняли такое положение, при котором оба коня будут взаимно бить друг друга. Покажите оба маршрута на шахматной доске. На одно и то же поле одновременно оба коня попадать не могут.

[894] На шахматной доске даны три разноцветных ферзя. Они бьют друг друга, если один стоит в поле «влияния» второго. Нали­чие третьего ферзя между двумя другими ферзями не препятствует возможности " бить". Определите, какие из ферзей бьют друг друга, если первая координата -символьная, вторая - натуральная.

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

[896] Найдите такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одно­гоиз них.

[897] Составьте программу оптимальной игры компьютера в крестики-нолики.

[898] Даны четыре слова. Напишите программу, проверяющую, можно ли из данных слов составить кроссворд при условии, что ка­ждое слово пересекается с двумя другими и располагается сверху вниз или слева направо. Сетка не обязательно симметрична. Резуль­тат выведите в виде кроссворда.

[899] " Робот в крепости". Робот находится в крепости, имею­щей форму лабиринта. У робота есть пять красок разных цветов. Он может закрасить клетку, на которой стоит, цветом k, где k=1, 2, 3, 4, 5, однако, нельзя закрашивать одну и ту же клетку дважды. Кре­пость - лабиринт задается двумерным массивом, записанным в файл. Ограничивающие стены и перегородки обозначаются семер­ками, все проходы - нулями, а единственный выход - восьмеркой. Помогите роботу выйти из лабиринта.

[900] Игра " Жизнь". Моделируется жизнь колонии живых кле­ток, которые выживают, размножаются, умирают по следующим за­конам: а) клетка выживает в том и только том случае, если она име­ет двух или трех соседей из 8 возможных; б) если у клетки только один сосед или ни одного, то она умирает в изоляции; в) если клет­ка имеет четырех или более соседей, то она погибает от перенасе­ления; г) в любой пустой позиции, у которой ровно три соседа в следующем положении появляется новая клетка. Размер поля 30*30. Начальное размещение дается играющим. Указывается количество поколений.

О Л И М П И А Д Н Ы Е З А Д А Ч И.

Первый уровень

[901] Календарь. Заданы три числа а, b, с, которые обозначают число, месяц и год. Найдите номер n этого дня с начала года. Учти­те, что високосные годы - это те, у которых номер делится на четы­ре. за исключением тех, номера которых делятся на сто, но не де­лятся на четыреста.

[902] Заданы три числа а, b, с, которые обозначают число, месяц и год. Найдите аналогичные три числа для каждого из следующих трех дней.

[903] Составьте алгоритм и блок - схему заполнения таблицы числа дней для всех лет от первого до двухтысячного года.

[904] Составьте программу, которая определяла бы временной интервал между датами. Найдите с ее помощью, сколько дней про­шло со дня первого полета человека в космос до сегодняшнего дня. Определите, сколько дней вы прожили со дня рождения до сего­дняшнего дня.

[905] Напечатайте все делители данного числа.

[906] Имеется квадрат, состоящий из 16 одинаковых маленьких квадратиков. Каждый маленький квадратик имеет двойную расцвет­ку и разделен диагональю. Верхняя часть квадратиков красная, нижняя - синяя. Квадратики можно поворачивать на 90, 180, 270, 360 градусов в плоскости большого квадрата. Напишите программу, ко­торая, имея произвольное исходное положение маленьких квадра­тиков внутри большого, укажет, как за минимальное количество по­воротов преобразовать большой квадрат в заданное положение.

[907] Несколько точек на плоскости, не лежащие на одной пря­мой, заданы своими координатами. Составьте алгоритм нахождения трех точек из числа заданных таких, что треугольник с вершинами в этих точках не содержит ни одной точки из оставшихся.

[908] Послание от внеземной цивилизации представляет собой набор из k символов, каждый из которых является нулем или еди­ницей. Число k является произведением двух простых чисел, и уче­ные предполагают, что эта строка - закодированная прямоугольная «картинка», размеры которой - множители числа k. Составьте про­грамму, которая произведет перекодировку послания и напечатает картинки, заменяя каждый нуль пробелом, а единицу - звездочкой

Тест. k=55. Послание: 1010001011110100100101111010001010010010010100100010111.

[909] На плоскости расположены 10 точек, заданные своими ко­ординатами. Найдите на оси абсцисс точку, наибольшее из расстоя­ний от которой до выбранных точек было бы минимальным.

[910] Для данного n вычислите сумму: 1+1/2+1/3+...+1/n. Ре­зультат выразите в виде несократимой дроби p/q.

Тесты и результаты. 1) n=4. 25/12. 2) n=5. 137/60. 3) n= 6. 147/60. 4) n=7. 1059/420.

[911] Дан массив А(50). Каждый элемент массива A(i) с номе­рами 1,..., 49 замените на среднее арифметическое трех элементов A(i-l), A(i), A(i+1). Дополнительный массив заводить нельзя.

[912] Найдите последовательные суммы цифр любого нату­рального числа. Пример: 85987; 37; 10; 1.

[913] В данном двумерном массиве замените нулями элемен­ты, стоящие в строках или колонках, где имеются нули. Все осталь­ные элементы удвойте. Дополнительный двумерный массив заво­дить нельзя, одномерный - можно.

[914] Дано натуральное число k, не превышающее миллион. Напечатайте фразу " k ворон'' русскими словами.