Дополнительное занятие по подготовке школьников к олимпиаде по информатике

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

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

Как известно, “правильную” задачу для подготовки к олимпиаде гораздо труднее выбрать, чем решить, т.к. их великое множество, но далеко не каждая содержит ценную крупицу тех знаний, которые окажутся необходимыми. При подготовки данной статьи автор пользуется материалами компетентного сайта acmp.ru, который, безусловно отражает и новизну заданий и необходимый уровень сложности и разнообразие.

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

Задача 1. Нумеролог (Время: 1 сек. Память:16 Мб ).

(http://acmp.ru/index.asp?main=task&id_task=95)

Чтобы предсказать судьбу человека, нумеролог берет время жизни человека в секундах, затем складывает все цифры этого числа. Если полученное число состоит более чем из одной цифры, операция повторяется, пока в числе не останется одна цифра. Затем по полученной цифре и числу операций, необходимых для преобразования числа в цифру нумеролог предсказывает судьбу человека. Нумеролог плохо умеет считать, а числа, с которыми он работает, могут быть очень большими. Напишите программу, которая бы делала все расчеты за него.

Входные данные Входной файл Input.txt содержит число N – время жизни человека в секундах (1 ≤ N ≤ 10¹⁰⁰⁰).

Выходные данные В выходной файл Output.txt выведите два числа через пробел: полученную цифру из числа N и число преобразований.

Примеры:

Идея решения: считываем строку из файла. В цикле, пока длина строки не станет единичной, посимвольно складываем все элементы данной строки, переводя их в числовой формат, в некое число. Превращаем это число в новую строку и снова проверяем ее длину. Как только получаем строку единичной длины – задача решена.

var s:string; i,k,n:longint; f1,f2:text;
begin
assign(f1,'Input.txt');
reset(f1);
read(f1,s);
close(f1);
k:=0; n:=0;
while length(s)>1 do
begin {Пока длинна строки s не станет единичной, повторять.}
for i:=1 to length(s) do begin
inc(k,strtoint(s[i])); {Складываем все элементы строки s в число k.}
end;
inc(n); s:=''; {Обнуляем строку s для создания новой.}
while k>0 do
begin
s:=s+inttostr(k mod 10); k:=k div 10; {Создаем новую строку s из всех цифр числа k.}
end;
end;
assign(f2,'Output.txt');
rewrite(f2);
write(f2,s[1],' ',n); close(f2);
end.

Задача 2. Словарь. (http://acmp.ru/index.asp?main=task&id_task=291)

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

Входные данные: В первой строке файла Input.txt записано число N – количество слов в словаре (0 <= N <= 1000). В следующих N строках файла записано по одному слову из словаря. Слова содержат от 1 до 10 маленьких латинских букв. Все слова в словаре различны. В последней строке файла записан набор букв (не более 100 букв). Выходные данные: Запишите в файл Output.txt количество различных слов из словаря, которые можно составить из заданного набора букв.

Примеры.

Идея решения: После считывания числа n, n – слов, строки – s, в которой записаны все символы, допустимые для использования в словах. Затем заполняем массив mn, определяя, сколько раз может встречаться буква в слове. Если в строке s нет какого-то символа, то 0. Проверяем, составлено ли каждое слово из разрешенных символов, используя логическую функцию Check(s :string) : boolean. В ней массив с символьными индексами mn1=mn. Затем проходим все символы в слове, уменьшая количество использованных символов в mn1.

Var i,n,r,l : integer;
a :array of string;
s :string;
j : char;
mn,mn1 : array['a'..'z'] of integer;
{Функция для проверки, составлено ли слово из разрешенных символов}
function Check(s : string) : boolean;
vari,j : integer;
begin
result:=true; mn1:=mn;
for i:=1 to Length(s) do
if mn1[s[i]]>0 then dec(mn1[s[i]]) else result:=false;
end;

begin
reset(input,'input.txt');
rewrite(output,'output.txt');
readln(n); r:=0;
for j:='a' to 'z' do mn[j]:=0;
if n<>0 then
begin
SetLength(a,n+1); {а – одномерный динамический массив строк размерности – n}
fori := 1 to n do readln(a[i]); {заполняем массив (а) нашими строками}
readln(s); {контрольная строка}
if s<>'' then
begin
{Определяем сколько раз каждая буква из контрольной строки встречается в ней}
for i:=1 to Length(s) do inc(mn[s[i]]);
for i:=1 to n do
{Отправляем каждое слово на проверку в нашу функцию}
if Check(a[i]) then inc(r);
end; writeln(r);
end;
end.

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

Сайты: http://acmp.ru/