С3. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (0, –4). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трех точек: или в точку с координатами (x+4, y), или в точку с координатами (x, y+4), или в точку с координатами (x+4, y+4). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0,0) больше 12 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
С4. На вход программе подается последовательность символов, среди которых встречаются и цифры. Ввод символов заканчивается точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая составит из тех цифр, которые встречаются во входных данных, максимальное число. При составлении итогового числа каждая цифра может быть использована только один раз. Если во входных данных цифры не встречаются, то следует вывести “–1”. Например, пусть на вход подаются следующие символы:
14ф73п439.
В данном случае программа должна вывести
97431
Ответы.
Часть 1
| Задание | Вариант | Задание | Вариант | ||
| № 1 | № 2 | № 1 | № 2 | ||
| А1 | 4 | 4 | А10 | 2 | 3 |
| А2 | 2 | 4 | А11 | 2 | 4 |
| А3 | 1 | 1 | А12 | 3 | 2 |
| А4 | 4 | 4 | А13 | 3 | 1 |
| А5 | 1 | 3 | А14 | 4 | 3 |
| А6 | 1 | 3 | А15 | 2 | 2 |
| А7 | 3 | 3 | А16 | 4 | 3 |
| А8 | 1 | 3 | А17 | 2 | 4 |
| А9 | 2 | 1 | А18 | 4 | 1 |
Часть 2
| Задание | Вариант | |
| № 1 | № 2 | |
| В1 | 243 | 64 |
| В2 | 67 | –66 |
| В3 | 2,11,22 | 7,15,23 |
| В4 | 7 | 8 |
| В5 | 1212 | 324 |
| В6 | СМК | СКМ |
| В7 | 1875 | 16 |
| В8 | 134 | 127 |
| В9 | БАГВ | ВГБА |
| В10 | 4132 | 1423 |
Часть 3. Вариант 1
С1. Элементы ответа:
1) Пример: x = –4, y = –0,5
В качестве примера может быть указана любая пара (x, y), для которой истинно условие:
y<–1 или y>sin x или (y>=–1 и y<=sin x и x< –π/2)
2) Хотя в формулировке задания приведены два пункта, на самом деле в задаче требовалось выполнить три действия – указать пример входных данных, при которых программа работает неверно, и исправить две ошибки:
а) неправильное использование условного оператора, в результате чего при невыполнении первого или второго условия программа не выдавала ничего (отсутствуют случаи ELSE).
б) приведенным трем ограничениям удовлетворяют также те точки плоскости, у которых (y >= –1 и y <= sin x и x < –π/2).
Ниже мы приводим полный текст программы на Паскале, в которой фрагмент доработки выделен жирным шрифтом.
program ex_c1;
var x,y: real;
begin
readln(x,y);
if (y >= –1) and (y <= sin(x)) and (y >= x – 1) and (x >= –3.14/2)
then write('принадлежит')
else write('не принадлежит')
end.
Могут быть и другие способы доработки.
Решение для варианта 2 полностью аналогично варианту 1.
С2. Приведем алгоритм решения задачи на русском языке.
Введем целочисленную переменную Diff с первоначальным значением, равным разности второго и первого элементов, в которую будем заносить разности значений элементов. Введем также переменную MinDiff для записи результата вычислений. Установим первоначальное значение MinDiff равным Diff. В цикле от третьего элемента до конца массива вычисляем разность текущего элемента и предыдущего и заносим его в переменную Diff. Далее сравниваем значения Diff и MinDiff. В случае, если текущая разность меньше, заносим значение текущей разности в переменную MinDiff. По окончании цикла выводим значение переменной MinDiff.
Ниже приведена программа на Паскале, реализующая описанный алгоритм, использующий однократный проход по массиву. При этом количество элементов в массиве описано в разделе констант, что позволяет легко модифицировать данную программу для решения данной задачи для массива любой длины.
program ex_c2;
const N = 30;
var a:array[1..N] of integer;
Diff, MinDiff, i: integer;
begin
Diff := a[2] – a[1];
MinDiff := Diff;
for i := 3 to N do
begin
Diff := a[i] – a[i –1];
if MinDiff > Diff then MinDiff := Diff
end;
writeln(MinDiff);
end.
Решение для варианта 2 в целом аналогично варианту 1. Особенностью второго варианта является необходимость предусмотреть в алгоритме проверку присутствия в массиве положительного элемента, и в случае отсутствия таковых требуется выдать соответствующее сообщение.
С3. Вариант 1.
Выигрывает второй игрок.[5] Приведем два способа решения
1 способ. Построение неполного дерева игры.
При таком способе рассматриваются все возможные варианты позиций, которые могут получиться после выполнения очередного хода. Позиции при этом играют роль вершин графа, а возможность перехода от одной позиции к другой обозначается ребром, соединяющим эти позиции. Можно изображать получающееся дерево стандартным образом, а можно оформить его в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры. При этом некоторые ветви могут не рассматриваться, если они уже были рассмотрены ранее (тогда-то и получается неполное дерево игры), но надо точно обосновывать, что отсечение ветвей не приводит к потере нерассмотренных вариантов.
Приведем неполное дерево вариантов для данной игры.
| 1 ход | 2 ход | 3 ход | 4 ход | |
| Стартовая позиция | I-й игрок (все варианты хода) | II-й игрок (выигрышный ход) | I-й игрок (все варианты хода) | II-й игрок (выигрышный ход, один из вариантов) |
| 1, 0 | 1, 4 | 4, 4 | 4, 8 | 4, 12 |
| 4, 7 | 4 ,11 | |||
| 7, 4 | 10 ,4 | |||
| 1, 3 | 4, 3 | 4, 7 | 4 ,11 | |
| 4, 6 | 4 ,10 | |||
| 7 ,3 | 10 ,3 | |||
| 4, 0 | 4, 4 или 4, 3 | Уже рассмотрено | ||
Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
Этот вывод должен быть обязательно сформулирован. Без него решение считается неполным.
2 способ. Построение таблицы выигрышных и проигрышных позиций.
Скажем сначала несколько слов об этом способе, поскольку он практически отсутствует в учебной литературе
Совокупность всех незаключительных позиций игры разбивается на два множества: множество выигрышных позиций и множество проигрышных позиций. Обозначим множество выигрышных позиций буквой V, а множество проигрышных позиций буквой Р. Чем характеризуются эти множества? Это можно описать совершенно формально. Позиция х является выигрышной (т.е. х ÎV), если существует ход (т.е. ребро графа), ведущий из х в заключительную позицию или позицию из множества Р. В свою очередь, позиция х является проигрышной (т.е. х ÎР), если любой ход из этой позиции ведет в позицию из множества V. Это позволяет расставить знаки + и – по следующему правилу: знаком – отмечаются все заключительные и проигрышные позиции, а знаком + отмечаются все выигрышные. Фактически это некий алгоритм: сначала знак – выставляется для всех заключительных позиций, затем выставляется знак + для каждой позиции, в которой есть ход, ведущий в позицию, помеченную знаком –, затем выставляется знак – для каждой позиции, у которой все ходы ведут в позиции, помеченные знаком +, и т.д.