Составители данного пособия сочли уместным начать обзор олимпиадных задач по информатике 1996-1997 учебного года с самого первого её этапа - со школьной олимпиады. Разумеется, обсудить задачи всех школьных олимпиад не представляется возможным. В качестве примера была выбрана олимпиада школы № 5 города Улан-Удэ, состоявшаяся в ноябре 1996 года, и хотелось бы выразить искреннюю благодарность учителю информатики этой школы Людмиле Михайловне Суворовой за предоставленные в распоряжение авторов материалы.
Читатели, регулярно интересующиеся проведением олимпиад по информатике в Бурятии, могут заметить, что некоторые из приведённых в данном разделе задач, в предыдущие годы предлагались на олимпиадах более высокого уровня: районных и даже республиканских. Такой подход вполне оправдан, поскольку за прошедшие годы уровень сложности олимпиадных заданий существенно возрос. Кроме того, не следует забывать, что победителям школьных олимпиад предстоит участвовать в следующих этапах конкурса, поэтому они должны пробовать свои силы в решении достаточно серьёзных задач. Сразу же оговоримся, что формулировки некоторых заданий данного раздела нами незначительно откорректированы по сравнению с тем, как они были представлены при проведении олимпиады.
Существует ли трёхзначное натуральное число, куб суммы цифр которого равен ему самому? Разработать алгоритм нахождения наименьшего такого числа.
Решение. Задача решается, что называется, "в лоб". Мы просто перебираем все числа от 100 до 999 и проверяем, равен ли куб суммы цифр числа самому числу. Перебор продолжается до тех пор, пока не будет найдено первое такое число.
Стоит отметить, что для того, чтобы избежать необходимости разбивать каждое очередное число на цифры, лучше организовать три вложенных цикла, перебирающих соответственно: сотни от 1 до 9 (внешний цикл по A), десятки от 0 до 9 (вложенный цикл по B) и единицы от 0 до 9 (внутренний цикл по C). Тогда очередное рассматриваемое число имеет вид A*100+B*10+C, а его сумма цифр равна A+B+C.
Заметим, что алгоритм решения составлен в предположении, что ответ на вопрос о существовании числа, удовлетворяющего сформулированному условию, неизвестен. Поэтому либо выводится значение минимального числа, обладающего нужными свойствами, либо сообщается о том, что трёхзначное число с нужными свойствами не существует. На самом деле, как показывает вычислительный эксперимент, такое число есть. Оно единственное и равно 512.
10 FOR A=1 TO 9
20 FOR B=0 TO 9
30 FOR C=0 TO 9
40 IF (A+B+C)^3=A*100+B*10+C THEN PRINT "Минимальное число с указанными свойствами";A*100+B*10+C: GOTO 60
50 NEXT C,B,A
55 PRINT "Трехзначного числа, удовлетворяющего указанному условию нет"
60 END
Var
a, b, c, l: Integer;
begin
for a := 1 to 9 do
for b := 0 to 9 do
for c := 0 to 9 do
begin
l := a+b+c;
if a*100+b*10+c=l*l*l then
begin
WriteLn('Минимальное трехзначное число, '+
'куб суммы цифр которого равен ему '+
'самому, равно ', a, b, c);
Break;
end;
end;
WriteLn(' Трехзначного числа, удовлетворяющего'+
' указанному условию нет.');
end.
Вокруг считающего стоят n человек, один из которых назван первым, а остальные занумерованы по часовой стрелке от 2 до n. Считающий, начиная с первого, ведет счёт до m. Человек, на котором остановится счёт, выходит из круга. Счёт продолжается со следующего участника (при этом выбывший из круга не считается), и так до тех пор, пока не останется один человек. Определить начальный номер участника, оставшегося последним.
Решение. Данная задача примечательна с методической точки зрения, так как позволяет обсудить с участниками олимпиады вопросы оптимизации алгоритмов.
Разумеется, для решения задачи надо смоделировать описанный в задаче процесс. При этом необходимо каким-то образом сохранять информацию о текущем состоянии цепочки считающихся. Первое, что кажется естественным, это завести массив, в котором для каждого игрока отмечается его состояние на данный момент: значение 1 показывает, что данный участник ещё в круге, 0 означает, что данный игрок уже выбыл. Вначале все элементы массива состояний имеют значение 1. Теперь надо n-1 раз считать до m по ненулевым элементам массива состояний, отмечать выбывающих игроков, устанавливая нулевые значения в соответствующих элементах массива, и в конце определить номер элемента, оставшегося с ненулевым значением (см. вариант 1).
Первое усовершенствование, в котором нуждается данный алгоритм, заметно практически сразу. Представим себе, что введены такие значения n и m, что m>n. В этом случае при счёте до m будет выполнено какое-то количество ненужных действий, связанных с необходимостью осуществить несколько "полных оборотов" по цепочке считающихся. Далее ситуация будет только усугубляться, поскольку количество игроков в круге после каждого пересчёта становится меньше. (Заметим, кстати, что рано или поздно, в связи с уменьшением числа участников, то же самое происходит и в случае, когда изначально m<n.) Этого можно избежать, если номер выбывающего игрока на каждом шаге определять не значением числа m, а остатком от деления m на количество игроков в круге в данный момент. Вариант 2 решения задачи учитывает данное замечание. Заметим, что в этом варианте изменился смысл параметра внешнего цикла. Если раньше этот параметр означал количество повторений процедуры пересчёта игроков, то теперь он указывает, сколько участников осталось в круге к началу очередного пересчёта.
А теперь хотелось бы избавиться от временных потерь в самом внутреннем цикле (цикл "пока", связанный с необходимостью пропускать при пересчёте уже выбывших игроков). Изменим начальную структуру данных. Вместо массива состояний заведём массив, где будет храниться начальная нумерация членов цепочки. Досчитав по нему до m, сдвинем содержимое элементов массива, "физически уничтожая" выбывший номер и сокращая число рабочих элементов для следующего шага. Разумеется, если выбывает участник, замыкающий в данный момент цепочку игроков, ничего сдвигать не надо: на следующем шаге соответствующий элемент массива всё равно не будет учитываться в связи с уменьшением на единицу числа рабочих ячеек. Начальный номер оставшегося последним игрока в данном алгоритме в конце концов окажется в первой ячейке массива номеров. Эта версия решения реализована в варианте 3.
Теперь попытаемся обойтись без малопродуктивных сдвижек элементов массива номеров, для чего надо по-другому организовать "физическое уничтожение" выбывающих игроков. И снова изменим представление исходных данных. Заведём линейный массив, в i-ом элементе которого будет храниться не первоначальный номер участника, оказавшегося в данный момент на i-ом месте в цепочке оставшихся игроков, а первоначальный номер игрока, который в текущий момент времени следует в цепочке за данным. Сначала значение i-го элемента просто равно i+1. Некоторая вспомогательная переменная будет выступать в роли указателя, отмечающего очередного игрока при пересчёте. Значения этого указателя меняются в соответствии с информацией, содержащейся в массиве. Определяя выбывающего на данном этапе игрока счёт будем останавливать не на нём самом, а на игроке, который находится непосредственно перед выбывающим. При такой организации действий номер выбывающего игрока определяется значением в ячейке игрока, на котором остановлен счёт (выбывает следующий за данным). Для организации "удаления" запишем в эту ячейку вместо номера выбывающего игрока значение, содержащееся в ячейке игрока, который выбывает. В результате этого следующим для игрока, на котором остановлен счёт, становится игрок, который был следующим для выбывшего игрока, т.е. из последующих пересчётов выбывший игрок действительно будет исключён.
Заметим, что в такой ситуации перед началом очередного пересчёта указатель отмечает не игрока, с которого начнётся счёт, а предыдущего. Поэтому в самом начале указатель должен указывать на самого последнего участника цепочки, так как именно он предшествует первому. Реализация данного алгоритма решения представлена в варианте 4.
5 'вариант 1
10 INPUT "Количество участников"; N
15 IF N<=1 OR N<>INT(N) THEN PRINT "некорректные данные. Повторите ввод": GOTO 10
20 INPUT "До скольки считать"; M
25 IF m<=0 OR m<>INT(m) THEN PRINT "некорректные данные. Повторите ввод": GOTO 20
30 DIM A(N)
40 FOR I=1 TO N
50 A(I)=1
60 NEXT I
70 k=0
80 FOR I=1 TO N-1
90 FOR J=1 TO M
100 IF k=N THEN k=1 ELSE k=k+1
110 IF A(k)=0 THEN 100
120 NEXT J
130 A(k)=0
140 NEXT I
150 k=1
160 if a(k)=0 then k=k+1: goto 160
170 PRINT "Номер последнего игрока -";K
5 'вариант 2
10 INPUT "Количество участников"; N
15 IF N<=1 OR N<>INT(N) THEN PRINT "некорректные данные. Повторите ввод": GOTO 10
20 INPUT "До скольки считать"; M
25 IF m<=0 OR m<>INT(m) THEN PRINT "некорректные данные. Повторите ввод": GOTO 20
30 DIM A(N)
40 FOR I=1 TO N
50 A(I)=1
60 NEXT I
70 k=0
80 FOR I=N TO 1 STEP -1
85 M1=M MOD I
86 IF M1=0 THEN M1=I
90 FOR J=1 TO M1
100 IF k=N THEN k=1 ELSE k=k+1
110 IF A(k)=0 THEN 100
120 NEXT J
130 A(k)=0
140 NEXT I
150 PRINT "Номер последнего игрока -";k
5 'вариант 3
10 INPUT "Количество участников"; N
20 IF N<=1 OR N<>INT(N) THEN PRINT "некорректные данные. Повторите ввод": GOTO 10
30 INPUT "До скольки считать"; M
40 IF m<=0 OR m<>INT(m) THEN PRINT "некорректные данные. Повторите ввод": GOTO 30
50 DIM A(N)
60 FOR I=1 TO N
70 A(I)=I
80 NEXT I
90 K=1
100 FOR I=N TO 1 STEP -1
110 M1=M MOD I
120 K=(K+M1-1) MOD I
130 IF K=0 THEN K=I: GOTO 170
140 FOR J=K TO I-1
150 A(J)=A(J+1)
160 NEXT J
170 NEXT I
190 PRINT "Номер последнего игрока -";A(1)
5 'вариант 4
10 INPUT "Количество участников"; N
20 IF N<=1 OR N<>INT(N) THEN PRINT "некорректные данные. Повторите ввод": GOTO 10
30 INPUT "До скольки считать"; M
40 IF m<=0 OR m<>INT(m) THEN PRINT "некорректные данные. Повторите ввод": GOTO 30
30 DIM A(N)
40 FOR I=1 TO N-1
50 A(I)=I+1
60 NEXT I
70 A(N)=1
80 K=N
90 FOR I=N TO 2 STEP -1
100 M1=M MOD I
110 IF M1=0 THEN M1=I
120 IF M1=1 THEN 160
130 FOR J=1 TO M1-1
140 K=A(K)
150 NEXT J
160 A(K)=A(A(K))
170 NEXT I
180 PRINT "Номер последнего игрока -";A(K)
{Вариант 3}
const
MaxN=100;
Var
A: array[1..MaxN]of Integer;
N, M, Amount, Pos, i, j: Integer;
begin
repeat
Write('Введите N:'); ReadLn(N);
if (N<1)or(N>MaxN) then
WriteLn('Неверное значение. Повторите.');
until (N>0)and(N<=MaxN);
repeat
Write('Введите M:');
ReadLn(M);
if M<1 then WriteLn('Неверное значение. Повторите.');
until M>0;
for i := 1 to N do A[i] := i;
Amount := N; Pos := 0;
for i := 1 to N-1 do
begin
Pos := (Pos+M-1)mod Amount;{счет останавливается на игроке,
который предшествует выбывающему}
for j := 1+Pos to Amount-1 do A[j] := A[j+1];
Dec(Amount);
end;
WriteLn('Останется игрок под номером ', A[1]);
end.
{Вариант 4}
const
MaxN=100;
Var
Next: array[1..MaxN] of Integer;
{Next[i] указывает номер следующего за i-ым}
N, M, Pos, i, j: Integer;
begin
repeat
Write('Введите N:');
ReadLn(N);
if (N<1)or(N>MaxN) then
WriteLn('Неверное значение. Повторите.');
until (N>0)and(N<=MaxN);
repeat
Write('Введите M:'); ReadLn(M);
if M<1 then WriteLn('Неверное значение. Повторите.');
until M>0;
for i := 1 to N-1 do Next[i] := i+1;
Next[N] := 1; Pos := N;
for i := N downto 2 do
begin
for j := 1 to (M-1)mod i do
Pos := Next[Pos];
Next[Pos] := Next[Next[Pos]];
end;
WriteLn('Останется игрок под номером ', Pos);
end.
Составить алгоритм, определяющий в заданном тексте на русском языке количество слов, содержащих 1, 2, 3 и более 3-х слогов.
Решение. Алгоритм решения данной задачи понятен сразу, и остаётся обсудить только технические вопросы его реализации.
Заведём массив из 4-х элементов, в котором будем хранить найденные количества слов, содержащих соответственно 1, 2, 3 и более 3-х слогов. Первоначально все элементы массива равны нулю. Затем по ходу обработки текста их значения будут должным образом изменяться.
Входной текст читаем символ за символом, выделяя отдельные слова. Признаком конца слова служит появление пробела или какого-либо знака препинания. Однако, поскольку при наборе текстов принято после любого знака препинания ставить пробел (за исключением открывающей скобки и открывающей кавычки, у которых пробел ставится перед ними), поэтому между любыми двумя словами всегда есть хотя бы один пробел. Следовательно, для определения конца слова в нашем случае можно контролировать только появление пробела или достижение окончания текста.
Заметим, что можно избежать проверки окончания текста, если изначально добавить в конец введённой строки пробел (см. реализацию на языке BASIC).
Отведём специальную вспомогательную переменную-счётчик под хранение числа слогов в текущем слове. В начале просмотра очередного слова значение этой переменной равно нулю. Как известно, число слогов в слове равно числу гласных. Поэтому действуем так. Встретив при просмотре слова гласную, увеличиваем значение счётчика на единицу. Определив, что очередное слово закончилось, в зависимости от значения счётчика наращиваем соответствующий элемент массива и обнуляем переменную-счётчик, чтобы приготовиться к подсчёту слогов в следующем слове (если оно есть).
Отдельно надо предусмотреть обработку ситуации, когда встретилось слово, не содержащее ни одного слога, например, предлог "в". Сделать это можно двояко. Можно завести элемент массива для слов, количество слогов в которых равно нулю, но не выводить значение этого элемента в итоговом сообщении (см. реализацию на языке BASIC), а можно просто исключить запись в массив, если переменная-счётчик хранит нуль (см. реализацию на языке PASCAL).
10 DIM L(4)
20 INPUT "Введите текст на русском языке (если в тексте есть запятые, он должен быть взят в кавычки)"; A$
30 A$=A$+" ": K=0
40 FOR I=1 TO LEN(A$)
50 B$=MID$(A$,I,1)
60 IF B$<>" " THEN 110
70 IF K>4 THEN K=4
80 L(K)=L(K)+1
90 K=0
100 GOTO 120
110 IF INSTR("АаОоЕеИиЫыУуЭэЮюЯя",B$)<>0 THEN K=K+1
120 NEXT I
130 FOR I=1 TO 3
140 PRINT "количество слогов"; I;" - слов";L(I)
150 NEXT I
160 PRINT "количество слогов более 3-х - слов";L(4)
const
Vowel = ['а', 'А', 'е', 'Е', 'и', 'И', 'о', 'О', 'у', 'У',
'ы', 'Ы', 'э', 'Э', 'ю', 'Ю', 'я', 'Я'];
Var
s: String;
Pos, Amount, i: Byte;
Number: array[1..4] of Byte;
begin
Write('Введите текст:'); ReadLn(s);
for i := 1 to 4 do Number[i] := 0;
Pos := 1; Amount := 0;
while Pos<=Length(s) do
begin
if (s[Pos]=' ')or(Pos=Length(s)) then
begin
if Amount>4 then Amount := 4;
if Amount>=1 then
Inc(Number[Amount]);
Amount := 0;
end else
if s[Pos] in Vowel then Inc(Amount);
Inc(Pos);
end;
for i := 1 to 3 do
WriteLn('Число ', i, '-сложных слов = ',Number[i]);
WriteLn('Число слов с 4-мя и более слогами = ',
Number[4]);
end.
Дана целочисленная таблица A[1:100], не содержащая нулевых элементов. Все отрицательные элементы надо переписать в левую часть таблицы без перестановки относительно друг друга, а все положительные - в правую. За алгоритм решения, не использующий новых таблиц, присуждается дополнительное количество баллов.
Решение. Приведём два варианта решения задачи: в одном варианте используется дополнительный линейный массив для хранения отсортированной в соответствии с заданием таблицы, в другом - не используется.
В первом варианте при заполнении исходного массива ненулевыми целыми числами производится подсчёт количества отрицательных значений элементов массива. Таким образом, после ввода исходного массива уже известно, начиная с какого номера в итоговом массиве должны следовать положительные элементы. Вводим две вспомогательные переменные: одна из них указывает номер ячейки итогового массива, куда будет помещён очередной отрицательный элемент исходного массива, другая переменная играет ту же роль для положительных элементов. Просматривая в цикле исходный массив, мы заносим очередное значение в ту или иную ячейку в зависимости от знака очередного элемента, одновременно наращивая значение соответствующей переменной.
Во втором варианте сортировка производится непосредственно в исходном массиве. Вспомогательная переменная k отмечает номер ячейки, куда должен быть помещён очередной обнаруженный отрицательный элемент массива. Естественно, сначала k=1. Обнаружив при просмотре исходного массива отрицательный элемент в позиции i, мы извлекаем его из i-ой ячейки, осуществляем сдвиг элементов массива, "освобождая" ячейку с номером k, записываем в эту ячейку найденное отрицательное значение, после чего увеличиваем значение переменной k.
В реализации алгоритмов решения задачи на языках программирования исходный массив заполняется случайными целыми числами. Для действительного обеспечения элемента случайности в начале программ производится настройка генератора случайных чисел. В реализации алгоритмов на языке BASIC приведён вариант такой настройки, не зависящий от особенностей различных диалектов языка. Разумеется, имея в виду какую-либо конкретную версию языка BASIC, эту настройку можно было бы выполнить иначе.
5 'вариант 1
10 DIM A(100),B(100)
20 PRINT "Нажмите любую клавишу"
30 A$=INKEY$
40 IF A$="" THEN I=I+1: GOTO 30
50 H=RND(-I): L=0
60 PRINT "Исходная таблица"
70 FOR I=1 TO 100
80 A(I)=-100+INT(RND(1)*201)
90 IF A(I)=0 THEN 80 ELSE PRINT A(I);
100 if A(I)<0 THEN L=L+1
110 NEXT I
120 PRINT
130 K=1: L=L+1
140 FOR I=1 TO 100
150 IF A(I)<0 THEN B(K)=A(I): K=K+1
160 IF A(I)>0 THEN B(L)=A(I): L=L+1
170 NEXT I
180 PRINT "Итоговая таблица"
190 FOR I=1 TO 100
200 PRINT B(I);
250 NEXT I
5 'вариант 2
10 DIM A(100)
20 PRINT "Нажмите любую клавишу"
30 A$=INKEY$
40 IF A$="" THEN I=I+1: GOTO 30
50 H=RND(-I)
60 PRINT "Исходная таблица"
70 FOR I=1 TO 100
80 A(I)=-100+INT(RND(1)*201)
90 IF A(I)=0 THEN 80 ELSE PRINT A(I);
100 NEXT I
110 PRINT
120 K=1
130 FOR I=1 TO 100
140 IF A(I)>0 THEN 210
150 A(0)=A(I)
160 FOR J=I TO K+1 STEP -1
170 A(J)=A(J-1)
180 NEXT J
190 A(K)=A(0)
200 K=K+1
210 NEXT I
220 PRINT "Итоговая таблица"
230 FOR I=1 TO 100
240 PRINT A(I);
250 NEXT I
{Вариант 2}
const
N = 100;
Var
Arr: array[1..N]of integer;
i, j, Pos: Byte;
T: integer;
procedure Print;
begin
for i := 1 to N do Write(Arr[i],' ');
WriteLn;
end;
begin
Randomize; Pos := 1;
for i := 1 to N do
repeat
Arr[i] := Integer(Random(200))-100;
until Arr[i]<>0;
WriteLn('Исходный массив'); Print;
repeat
{поиск отрицательного правее Pos}
i := Pos;
while (i<=N)and(Arr[i]>0) do Inc(i);
if i>N then Break;{нет отрицательных правее Pos}
{сдвиг отрицательного к Pos}
T := Arr[i];
for j := i downto Pos+1 do Arr[j] := Arr[j-1];
Arr[Pos] := T;
Inc(Pos);
until False;
WriteLn('Итоговый массив'); Print;
end.