Примеры олимпиадных задач

Определение алгоритма

Например, рассмотрим следующий пример:

Для построения на алфавитно-цифровом дисплее прямой линии написана следующая программа:

For X:=X1 to X2 do

Begin

Y:=Y1+(Y2-Y1)*(X-X1)/(X2-X1)

Gotoxy(x,y);

Write(‘█’)

End;

Y=[Y1+(Y2-Y1)*(X-X1)/(X2-X1)]

Эта прямая (X1,Y1,X2,Y2) представляется такой ступенчатой функцией. Но если соотношение между координатами —

< 1, то у этой прямой получится следующий вид

т.е. проводник размыкается из-за того, что между ступенями расстояние больше 1.

При построении прямой такого вида нужно строить вертикальные линии следующего вида

Здесь строится прямая при фиксированном X:
от Y=[Y1+(Y2-Y1)*(X-X1)/(X2-X1)]
до Y=[Y1+(Y2-Y1)*(X-X1+1)/(X2-X1)]

Но при X1=X2, т.е. при вертикальной линии, эта прямая не может быть представлена такими линиями, поэтому нужно строить в этом сечении X=X1=X2 прямую от Y1 до Y2.

А при Y1=Y2, линию Y=Y1.

Здесь для построения сечения можно предложить следующий фрагмент программы

. . .

Var x1,x2,y1,y2: integer; …

{две координаты прямой, которую нужно изобразить на экране}

procedure harefxy(x,y:integer);

begin Gotoxy(x,y); Write(‘█’) end; …

Begin

Write('Введите через пробел координаты концов прямой:');

Read(x1,x2,y1,y2);{предполагается, что данные корректно вводятся, т.е. 0<x1,x2<81 и 0<y1,y2<25}

If Y1=Y2 Then {горизонталь}

If X1<X2 then

For X:=X1 to X2 do harefxy(x,y1)

else

For X:=X2 to X1 do harefxy(x,y1)

else

If X1=X2 Then {вертикаль}

If Y1<Y2 then

For Y:=Y1 to Y2 do harefxy(x1,y)

else

For Y:=Y2 to Y1 do harefxy(x1,y)

else

begin

If x1>x2 then

Begin

x1+=x2;x2:=x1-x2;x1:=x1-x2;

y1+=y2;y2:=y1-y2;y1:=y1-y2

end;

If abs((X1-X2)/(Y1-Y2))>=1 Then

for x:=x1 to x2 do

harefxy( x< y1+(y2-y1)*(x-x1) div (x2-x1))

Else

if y1<y2 then

for y:=y1 to y2 do

harefxy(x1+(x2-x1)*(y-y1) div (y2-y1),y)

End

...

end.

Игровые программы

На олимпиадах часто используются задачи связаннные с играми. Рассмотрим серию игр, в которых по очереди берутся спички или камни из кучи

Игра N1.

Правила игры:

— играют два игрока,

— задано 3 спички,

— игроки по очереди берут не более 3-х спичек,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

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

Игра N2.

Правила игры:

— играют два игрока,

— задано 4 спички,

— игроки по очереди берут не более 3-х спичек,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

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

Игра N3.

Правила игры:

— играют два игрока,

— задано 4*n спички,

— игроки по очереди берут не более 3-х спичек,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

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

Игра N4.

Правила игры:

— играют два игрока,

— задано (k+1)*n спички,

— игроки по очереди берут не более k спичек,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

В данном случае второй игрок при желании может выиграть после хода первого, забирая число спичек, дополняющих до k+1 ход противника

Для усвоения игр можно их проводить в классе следующим образом

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

Данный метод игры позволит быстро провести турнир и держать учеников в определенной активности.

Если ученики осознают игру, можно организовать разбор метода решения. Если же метод решения не определится, то предложить сыграть с победителем. Что позволит повысить Ваш авторитет и возможно позволит ученикам увидеть выигрышную стратегию игры.

Если же и в этом случае ученики не определят стратегию, нужно перейти к рзбору Игр N1, N2 и N3.

После чего переходим к усложненой формулировке этих игр.

Игра N5.

Правила игры:

— играют два игрока,

— задано n спичек,

— игроки по очереди берут не более k спичек,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

При решении этой задачи решение нужно привести к правилам Игры N4. Для этого необходимо определить n кратно (k+1) или нет. Если n кратно (k+1), то это условия игры N4. Если же нет, то первым (n mod (k+1)) ходом можно привести к условиям игры N4.

Игра N6.

Правила игры:

— играют два игрока,

— задано n спичек,

— игроки по очереди берут не более k спичек,

— проигрывает тот, кто берет последний.

Выигрышная стратегия:

В данном случае нужно рассмотреть рассуждения игры N1 для четырех спичек. Если мы будем оставлять по одной спичкеЮ то мы выиграем. Поэтому выигрывает тот, кто после своего хода оставляет число спичек кратное (k+1) и еще 1. Поэтому для выигрыша необходимо определить (n mod (k+1))=1 или нет. Если равно, то надо ходить вторым и своим ходом обеспечивать это равенство, иначе надо сделать первый ход обепечивающий выполнение этого равенства, а затем играть как уже рассматривалось.

Игра «Гонки»

Как модификация данной игры можно рассмотреть игру «Гонки».

Правила игры:

— играют два игрока,

— задано n клеток на линии,

— игроки по очереди могут продвигать свою фишку от 1 до k клеток вправо или влево, не занимая место с фишкой противника и не перескакивая фишку противника,

— проигрывает тот, кто не сможет произвести ход.

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

Игра «Ним»

Далее заданное множество камней можно разбить на кучи и третье правило можно сменить на то, что можно брать любое число только изодной кучи. Тогда это будет игра НИМ.

Правила игры:

— играют два игрока,

— задано n куч камней,

— игроки по очереди берут любое число камней изодной кучи,

— выигрывает тот, кто берет последний.

Выигрышная стратегия:

Для решения этой задачи используется двоичное представления чисел камней в каждой кучи: k₁,k₂,…k_n. Далее их складывают поразрядно по модулю 2,

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