Олимпиадные задачи с решениями на Turbo Pascal
| Информационный Канал Subscribe.Ru |
Бодрое время суток, уважаемые подписчики!
Сначала хотим поздравить тех, кто гордо относит себя к женскому полу. Хотим пожелать
переплюнуть нас, парней, во всех сферах жизни, включая программирование. А то,
что в скобках попросим не читать.
(Мужики, мы пошутили. Им нас всё равно не обойти.)
А теперь о серьёзном. Структура этого выпуска, как и всех последующих, будет
выглядеть так:
1)Разбор задач из прошлого выпуска (с respect’ом лучшим решениям);
2)Немного теории об алгоритмах, методах решения и окололежащих вопросах;
3)Новые задачи.
Сразу хотим сказать кое-что о формате присылаемых вами программ и используемых
языках программирования.
Многие из вас изъявили желание писать на C/C++, поэтому решения вы можете присылать
как на Turbo Pascal’е, так и на C/C++. Только учтите, что для получения исполнимых
файлов мы используем только компиляторы Turbo Pascal 7.0 и Borland C++ 3.0 (EXE-модули
присылать не нужно).
Итак приступаем.
Разбор предыдущих задач.
Задача №1.
Идея состоит в следующем:
если требуемый символ является последним в строке, то выводим этот символ (по
номеру строки он определяется однозначно). В противном случае, вычтем единицу,
получив строку с четной длиной. Получившая строка состоит из двух одинаковых,
поэтому, если номер символа попадает во вторую часть, то мы уменьшим его на n/2,
при этом искомый символ не изменится. Будем повторять указанную процедуру. Очевидно,
что рано или поздно искомый символ будет найден.
var inp, outp: text;
l, i, n, s: longint;
begin
assign(inp,'input.txt');
assign(outp,'output.txt');
reset(inp);
rewrite(outp);
readln(inp,n);
readln(inp,s);
l:=(1 shl n)-1; {вычисление длины строки}
while s<>l do
begin
dec(l);
if s>l div 2 then s:=s-l div 2;
l:=l div 2;
dec(n);
end;
write(outp,chr(ord('a')+n-1));
close(outp);
close(inp);
end.
Задача №2.
Этой задача решается аналогично предыдущей с той разницей, что мы должны хранить
все длины строк или вычислять по мере надобности.
Теория.
Сложность алгоритмов.
После того, как программист ознакомится с задачей, которую он должен решить,
он должен выбрать алгоритм, с помощью которого он и будет ее решать. Обычно задача
имеет несколько различных решений, эффективных и не очень, иногда крайне нерациональных.
Рассмотрим простейшую задачу: найти сумму всех натуральных чисел от 1 до N, где
1<=N<=3 000 000 000. В первую секунду раздумий приходит простейшее решение: for
i:=1 to N do sum:=sum+i. Разумеется, оно неэффективно: на третью секунду размышлений
приходит другой вариант: sum=(1+N)/2*N, принципиально улучшить который невозможно.
Отсюда возникает вопрос: насколько эффективен должен быть алгоритм и когда его
улучшение можно прекратить. Все задачи, решаемые программистами, можно разделить
на три класса: учебные, олимпиадные и реальные. Учебные задачи обычно просты
и требуют от решающего лишь знания определенного материала. Творческий подход
здесь почти отсутствует. В отличие от учебных задач, олимпиадные могут требовать
для своего решения знания практически чего угодно и каких угодно разделов науки
(обычно математики, реже – физики); кроме того, часто нужно время, а иногда и
немалое, чтобы пообобрать подходящий алгоритм решения. Но у этих задач, по сравнению
с реальными, есть одно несомненное преимущество: обычно они предусматривают решению,
удовлетворяющее условиям. То есть в этих задачах есть ограничения на входные
данные. Еще более непредсказуемы задачи, возникающие на практике, названные мной
реальными. Часто они бывают довольно просты, но иногда попадаются и такие, для
решения которых придется основательно пораскинуть мозгами. Если подобные задачи
сразу не решаются, то у программиста обычно возникает одна из двух мыслей: «Я
слишком туп для решения этой задачи», «А можно ли вообще найти эффективной решение
этой задачи». Что касается второй мысли, то, действительно, существуют классы
задач, удовлетворительного решения которых до сих пор пока не и, вероятно, никогда
не будет. В качестве примеров можно привести задачи дешифровки данных, закодированных
с помощью некоторых современных алгоритмов. Но это еще не самое страшное: существуют
задачи, решить которые невозможно вообще! В качестве примера можно привести десятую
проблему Гильберта: существует ли алгоритм, который позволяет для произвольного
многочлена p(x[1],x[2],…,x[n]) выдает, имеет ли решение в целых числах уравнение
p=0. Также, например, невозможно построить алгоритм, который для произвольной
программы и произвольных входных данных определял бы, корректно ли работает данная
программа.
Зачастую время выполнения программы определяется не столько сами исходные данные,
сколько их «размер». Под размером здесь и далее мы понимаем как физический размер
данных (например, длина последовательности), так и размер рассматриваемых объектов
(например, строки в задачах предыдущего выпуска). Обычно говорят, что время выполнения
программы имеет порядок T(n) от входных данных размера n. Например, некая программа
имеет время выполнения T(n) = cn^2, где c – константа. Единица измерения точно
не определена, но мы будем понимать T(n) как количество инструкций, выполняемых
на идеализированном компьютере. Можно также рассматривать T(n) как время выполнение
программы в случае наихудшего набора входных данных, кроме того, иногда T(n)
рассматривают как среднее время выполнения программы.
Для описания скорости роста функции T(n) используется O-символика. Например,
когда говорят, что время выполнения T(n) некоторой программы имеет порядок O(n^2),
то подразумевают, что существуют положительные константы c и n0 такие, что для
всех n>=n0 выполняется неравенство T(n)<=cn^2.
Так как обычно вся программа разбивается на фрагменты, то время ее выполнения
можно сосчитать как сумму или произведение отдельных ее частей. Пусть T1(n) и
T2(n) – время выполнения двух программных фрагментов P1 и P2. T1(n) имеет степень
роста O(f(n)), а T2(n) – O(g(n)). Тогда T1(n)+T2(n), т. е. время последовательного
выполнения фрагментов P1 и P2, имеет степень роста O(max(f(n),g(n))). Аналогично
вычисляется степень роста произведения T1(n)*T2 (n): она равна O(f(n)*f(n)).
Проиллюстрируем сказанное на примере пузырьковой сортировки.
const n=100;
var A: array[1..n] of integer;
i, j, temp: integer;
begin
for i:=1 to n do A[i]:=random(1000);
for i:=1 to n-1 do
for j:=n downto i+1 do
if A[j-1]>A[j] then begin
{ перестановка местами A[j-1] и A[j] }
temp:=a[j-1];
a[j-1]:=a[j];
a[j]:=temp;
end;
for i:=1 to n do write(A[i],’ ’)
end.
Здесь P1 – ввод данных, P2 – сортировка, P3 – вывод данных. Степень роста P1
и P2 равна O(n), так как выполняется ровно n операций. Время выполнения внутреннего
цикла в сортировки зависит от i: он выполняется от 1 до n-2 раз, поэтому для
него порядок времени выполнения можно считать n/2, то есть O(n); для внешнего
цикла его также можно считать O(n), но тогда порядок времени выполнения всего
цикла равен O(n*n)=O(n^2). Порядок времени выполнения всей программы будет равен
O(max(n,n^2,n)) = O(n^2).
Стоит также отметить то, что иногда вместо того, чтобы говорить «порядок времени
выполнения» говорят просто «время выполнения», подразумевая, что время работы
программы зависит от n так же, как и выражение, находящееся под символом O.
Если время выполнения участка кода не зависит от n, то его сложность считают
равной О(1).
В следующем выпуске мы предполагаем осветить вопрос об NP-полных задачах.
Новые задачи.
Задача 3.
Максимальная подпоследовательность.
Дана последовательность из N целых двузначных чисел. Требуется найти подпоследовательность
(идущих друг за другом элементов) с тем условием, чтобы сумма чисел этой подпоследовательности
была максимальной.
Входной файл (input.txt):
В первой строке содержится количество чисел последовательности.
Во второй строке записана сама последовательность.
Выходной файл:
Сумма найденной подпоследовательности.
Пример:
input.txt
-----начало файла-----
12
3 0 –7 14 20 –5 17 99 –99 0 11 –1
-----конец файла-----
output.txt
-----начало файла-----
145
-----конец файла-----
Комментарий: 14+20+(-5)+17+99 = 145
Задача 4.
Максимальная подматрица.
Дана матрица N*N из целых двузначных чисел. Требуется найти подматрицу с тем
условием, чтобы сумма чисел этой подматрицы была максимальной.
Входной файл (input.txt):
В первой строке содержится количество строк исходной матрицы.
В последующих N строках записана сама матрица.
Выходной файл:
Сумма найденной подматрицы.
Пример:
input.txt
-----начало файла-----
5
3 0 –7 14 20
–5 17 99 –99 0
11 –1 5 0 10
-9 10 34 78 –53
3 -27 15 –2 -10
-----конец файла-----
output.txt
-----начало файла-----
159
-----конец файла-----
Комментарий: 17+99+(-1)+5+10+34 = 159
Удач в решении задач. До следующего выпуска.Ищешь фильм? http://aslof.balzer.ru/
http://subscribe.ru/catalog/rest.cinema.filmforyou
| http://subscribe.ru/
E-mail: ask@subscribe.ru |
Отписаться
Убрать рекламу |
| В избранное | ||
