- •2008 № I информатика
- •2008 № 4 Информатика
- •2. Статья "Частотный анализ"
- •1. Общие вопросы
- •2. Особенности выполнения рекурсивных алгоритмов
- •3. Рекурсивные функции и процедуры для обсуждения
- •2008 Nt 5 информатика
- •4. Задания на использование рекурсии
- •2008 № 5 Информатика
- •2008 N» 5 информатика
- •2008 N» 5 информатика
- •2008 № 5 Информатика
- •5. Прямая и косвенная рекурсия
- •5. Формы рекурсивных процедур6
- •2008 № 5 Информатика
Две простые олимпиадные задачи
на использование сортировки подсчетом
От редакции. Уместно напомнить, что вместе ■ ^ 24/200. наши подписчики получили брошюру Методы поиска и сортировки", в которой содержится систематический обзор различных методов сортировки, в том числе и с точки зрения использования их в олимпиадных задачах.
Задача «Палиндром»
Палиндром — это строка, которая читается одинаково как справа налево, тик н слева направо.
Во входном файле записан набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется написать программу, которая из данных букв по указанны.и правилам составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке.
Формат входных данных
В первой строке записано число N (1 < N< 100 000). Во второй строке записана последовательность из N больших латинских букв (буквы записаны без пробелов).
Формат выходных данных
В единственной строке выдайте искомый палиндром.
Примеры
Входные данные |
Выходные данные |
ДАВ |
ABA |
6 QAZQS.Z |
AQZZQA |
6 |
|
Решение
Сначала найдем решение задачи для строк, в которых каждая буква встречается четное количество раз (второй пример как раз соответствует такому случаю). Естественно, что в этом случае палиндром наибольшей длины будет также иметь четную длину, и во второй его половине будут содержаться те же буквы, что и в первой, отраженные зеркально относительно середины. При
М.С. ГУСТОКАШИН,
Москва
его составлении будут использованы все буквы исходной строки.
Таким образом, нам надо построить только первую половину палиндрома (вторая получается выводом п обратном порядке), и количество вхождений каждой буквы в первую половину должно составлять половину от количества вхождений этой буквы в исходную строку.
Кроме того, необходимо, чтобы палиндром был наименьшим в алфавитном порядке. Для этого буквы, стоящие раньше по алфавиту, должны находиться как можно ближе к началу палиндрома.
Исходя из этого, можно построить решение для случая, когда все буквы входят в строку четное количество раз. Будем идти по буквам, начиная с меньших по алфавиту, и выводить каждую вдвое меньше раз, чем она входила в исходную строку. После этого необходимо вывести вторую половину палиндрома. Ее вывод отличается только тем, что перебирать буквы нужно от больших к меньшим (от Z к А).
Теперь рассмотрим случай, когда буквы встречаются нечетное количество раз. По свойству палиндрома можно понять, что каждая буква должна иметь пару (т.е. входить в палиндром четное количество раз), кроме, возможно, одной буквы, которая будет находиться ровно посередине палиндрома (она будет парной "сама с собой"). Таким образом, для случая с нечетным количеством букв генерация "половинок" палиндрома будет полностью совпадать с четным случаем, но между половинками будет еще одна буква. Критерии выбора этой буквы следующие: во-первых, она должна входить в строку нечетное число раз, а во-вторых, среди всех букв, входящих нечетное количество раз, она должна быть наименьшей в алфавитном порядке (это требуется для того, чтобы сгенерировать наименьший в алфавитном порядке палиндром).
Алгоритм решения задачи понятен, осталось подобрать наиболее удобную реализацию. В данном случае это будет сортировка подсчетом. Заведем массив от А до Z и на этапе считывания в каждой ячейке этого массива запомним, сколько раз она входила в исходную строку. Для этого при считывании очередной буквы будем увеличивать соответствующий элемент массива на единицу. После этого предложенное выше решение легко реализуется.
28
2008 N» 1 ИНФОРМАТИКА
Формат выходных данных
И lU.lXOAM'"' '..... '" ..... ■
|
: array |
' -"■■' - |
|
of |
|
egin |
|
|
|
|
|
for с |
|
to ' . |
1 do |
|
заполняе!ь |
Пример
readlr. (г.) ;
for i := i to :"- do begin read(c);
// увеличиваем - ^:£: элемент
I г. с (? vrr.t ' ~ ) ; end; for г :~ 'A' to ' ' do
for - : - 1 to г \тт,Ъ i с j div 2 do
w:;:ei:i; первая половина р.алиндрома for с := 'A' to ':' do
■/ ищем "нечетньо*" симвсг if syrijc; Bod С = 1 then begin write(C);
Еывели егс, :." --неинтересны : ^ •:; end; for r : ' _ ' downto ' Л' do
for i : = 1 to с vt-j: ; с; div 2 do = торзя ~з."~=:'на палиндрома
Задача «Шифровка»
Мальчик Петя чрезвычайно увлекается различными шпионскими рассказами и недавно от чтения романов со стрельбой и погонями перешел к изучению серьезной литературы. Особенно его заинтересовал один из методов шифровки секретных сообщений, прочитанный им в брошюрке по криптографии из серии ''Библиотечка кровавого режима".
Метод заключается в следующем: среди большого количества чисел спрятано то, которое несет секретную информацию, причем все числа встречаются трижды (или кратное трем число раз), кроме секретного числа, которое встречается некратное трем число раз. Так как Петя был маленьким и обладал чрезвычайно живым воображением, то он представил себе сотни шифровщиков с красными глазами, сидящих под зелеными лампами и с огромной напряженностью выискивающих секретное число на распечатках, ошибающихся и рвущих на себе волосы. Однако в реальности такой шифр легко взламывается компьютерной программой, которую вам предстоит написать.
Формат входных данных
Во входном файле записано целое число N — количество чисел (1 < N < 300 001). Далее записано X целых чисел Ad (1 < М < 2- 10').
Входные данные |
Выходные данные |
31231322133 |
|
Решение
Oi риничснис по памяти (при решении данной задачи можно было использовать не более 1 Мб оперативной памяти) и количество чисел не дает возможности ни сохранить все числа для последующей сортировки, ни даже просто запомнить их в единственном эклемиля]х*; кроме того, исходя из ограничения по времени и количеств;! чисел, можно сделать вывод, что палача должна решаться за и шейное время.
При решении этой задачи воспользуемся той же ::деей сортировки подсчетом. Допустим, что все числа состоят из одной цифры. Тогда нам достаточно посчитать, сколько раз встречалось каждое число (для хранения этих данных достаточно массива с индексами от 0 до 9). После этого среди всех чисел выберем то, которое встречалось некратное трем число раз, его индекс и будет ответом. Для этого достаточно одного прохода по массиву и подсчета остатка от деления каждого элемента на 3.
Теперь попробуем найти решение для двузначных чисел. В принципе мы можем сделать "сортировку подсчетом" для всех чисел от 0 до 99, и этот метод будет работать. Но наша задача подразумевает числа до двух с лишним миллиардов и таким методом уже не решится, хотя бы потому, что мы не имеем доступа к 8 гигабайтам памяти. Поэтому будем искать правильное решение на примере двузначных чисел.
Поступим следующим образом: разобьем каждое двузначное число на разряд десятков и разряд единиц (однозначные числа будут иметь в качестве разряда десятков 0). Таким образом, мы получим две цифры, для которых можно по отдельности применить описанное выше решение задачи для цифр! После этого из двух полученных в качестве ответа цифр мы с легкостью можем получить ответ: умножим цифру десятков на 10 и прибавим к ней цифру единиц.
Аналогично составляется решение и для полной задачи, только вместо 2 используется уже 10 разрядов.
table : array[1..10, 0..9] of longint;
i, j, k, r. : longint; begin
for i := 1 to 10 do
2008 № 1 ИНФОРМАТИКА
29
for j := 0 to 9 do
// заполняем таблицу нулями table[i, j] := 0; :ead(n);
for i := 1 to r, do begin read(k);
j := 1; // номер разряда while к о 0 do begin // на месте j добавилась цифра к mod 10
inc(table[j, k mod 10]); // выкидываем последнюю цифру -- := k div 10;
переходим к следующему- разряду ir.c(j); end; end; ■: : ; - ; здесь будем восстанавливать число
- начиная со старших разрядов for i := 10 downto 1 do begin // переходим к следующей цифре k := k • 10; // перебираем все цифры for j := С to 9 do
// нашли "секретную" цифру if tabled, j] mod 3 <> 0 then // и прибавляем ее к ответу к := k + j; end;
end.
У этой задачи существует и другое решение, в котором используется тема "системы счисления . Представим каждое число в троичной системе счис-
ления. Каждый т|Ч)ичный разряд будем рассматривать отдельно. Воспользуемся тем, что каждое число встречается трижды, т.е. в каждом разряди одна и та же цифра (допустим, л') встречается три раза. При суммировании r этом разряде получим 3 • х. Будем проводить поразрядное суммирование по модулю 3 (т.е. после каждого суммирования брать в каждом разряде остаток от деления на 3). 'Гак как порядок слагаемых не имеет значения, то все тройки чисел дадут н каждом разряде 0 (остаток от деления 3- х на 3 равен О независимо от значения х). В итоге, после такого суммирования всех чисел мы получим искомое число в троичной системе счисления (все остальные в сумме дадут 0 во всех разрядах). Остается только перевести это число в десятичную систему счисления и вывести его. При этом количество разрядов в т]юичном числе определяется из соотношения У" > 2 • 10'. Подбором легко определить минимальное т — 20.
Мы научились восстанавливать число, если оно встречалось один раз (или Зк + 1 раз). Если число встречалось дважды (или Зк -\~ 2 раза), то следует в каждом разряде 2 заменить на 1, а 1 — на 2. Это объясняется тем, что два числа, имеющие 1 в данном разряде, в сумме дадут 2, а две 2— 1 (2+ 2 = 4, берем остаток от деления на 3 и получаем 1). Самый простой способ произвести замену — умножить каждый разряд на 2 и взять остаток от деления на 3. Для нулей ничего не меняется, они и в сумме дают ноль. Определить, какой из случаев имеет место, можно, посчитав остаток от деления на 3.
ФОТОКОНКУРС "МЫ УЧИМ И УЧИМСЯ ИНФОРМАТИКЕ»
2008 № I информатика
21
Две несложные олимпиадные задачи
по программированию с математическим
содержанием
Задача "Трамвай"
Трамвайная линии имеет вид примой. Мстя живот в N трамвайных остановках от метро. Метро находится у нулевой остановки, и точке с координатой 0.
Выходя ил метро. 11етя хочет попасть домой как можно быстрее, по он очень не любит ждать трамвай на остановке. Поэтому, если, подходя к очередной трамвайной остановке, он не видит трамвая, то идет пешком вдоль трамвайной линии. Если в какой-то момент Петя видит трамвай, то он может принять решение вернуться на остановку или продолжить свое движение к следующей остановке. Петя идет со скоростью U, трамвай едет со скоростью V. Нужно найти минимальное расстояние L которое должно просматриваться перед нулевой остановкой, чтобы он мог идти со своей скоростью в сторону дома, не опасаясь, что траллвай его обгонит между остановками.
Формат входных данных
Во входном файле находятся три числа — N, U и V (N < 1000, U и V — положительные вещественные), за которым будет следовать N вещественных чисел — Х,,Х2, -, X, (0<Лг| < Х2 <...<Х„ < МУ), разделенных пробелами.
Формат выходных данных
В выходной файл ваша программа должна вывести число /. с точностью до 10" . Примеры
Входные данные |
Выходные данные |
3 12 2 4 12 |
1.000 |
Решение
Рассмотрим положение Пети в некоторый момент, когда он находится в некоторой точке между остановками. Если он видит трамвай в этот момент, то у него есть два варианта: дойти до следующей остановки или вернуться на предыдущую. Чтобы минимизировать расстояние, необходимо выбрать из двух этих вариантов лучший. Понятно, что Петя должен ока-
— М.С. ГУСТОКАШИН,
Москва
xrriioi на остановке одновременно с трамваем (ожидание нам ни к чему; если его исключить, то можно уменьшить дистанцию). Таким образом, нужно определить время, за которое трамвай доедет до преды-дум|ей и до следующей остановки. Проделаем то же самое дли Пети — посчитаем время его прихода на следующую остановку и на предыдущую. После этого можно выбрать лучший из этих двух вариантов и, решив уравнение, определить расстояние, которое должно просматриваться перед нулевой остановкой. Теперь посмотрим внимательно на худший случай, когда Петя приходит на обе остановки одновременно с трамваем. Исходя из этого, можно составить следующую систему уравнений:
(X\i + 1] + L)/V = (X\i + 1]- X[i\-dist)/U
Здесь / — номер предыдущей остановки, a (list — расстояние, на которое Петя отдалился от предыдущей остановки. Из первого уравнения выразим dist
и подставим его во второе уравнение:
перенесем все слагаемые с I. в левую часть, а остальные — в правую:
L/V + L/V = (Х[/ + 1] - X[i] )/U- (Х(/| + Х|< + Ц )/ V,
теперь можно выразить L:
I, = ((X[i + 1] - X\i] )/(./ х V -(X[i| + Х(/ + 1] ))/2 .
Таким образом, для любой пары последовательных остановок мы получили формулу для определения расстояния до нулевой остановки, на которое должен видеть Петя, чтобы не упустить трамвай. Так как трамвай может появиться в любой момент, то для получения окончательного ответа нужно перебрать все пары последовательных остановок и выбрать наибольшее из всех получившихся L. Из условия задачи можно понять, что L не может быть меньше нуля, т.е. в начале программы следует записать туда 0.
var
у. : аггау[0. .1000] of double; i, n : longint; 1, maxl, u, v : double; begin
readln, u, v); x[0] := 0; maxl := 0;
22