Олимпиадные задачи с решениями на Turbo Pascal от двух Дмитриев, Ильи ну и Александра
| Информационный Канал Subscribe.Ru |
Разбор полетов.
Задача №4. Максимальная подматрица.
Идея решения этой задачи заключается в использовании предыдущей задачи для столбцов
Приведенным выше рассуждением мы хотели показать, что предложенный вами алгоритм решения задачи нужно уметь обосновывать, поскольку он может содержать в себе ошибки.
Задача №5. Шутка
13+23+33+...+N3=(1+2+3+...+N)2.
Примечание: для людей только начинающих программировать добавим, что складывать все числа подряд смысла нет, ибо это сумма N первых членов арифметической прогрессии.
Задача №6. Сумма коэффициентов.
Сумма коэффициентов после возведения многочлена в степень (аnхn+...+a2x2+a1x+a0)k будет равна (an+...+a2+a1+a0)k. Это легко выводится из бинома Ньютона. Но самому выводу в рассылке места не найдётся. Да это и хорошо.
Новые горизонты.
Сегодня мы рассмотрим самые простые динамические структуры - линейные списки.
Списки являются чрезвычайно гибкой структурой, так как их легко сделать большими или меньшими, и их элементы доступны для вставки или удаления в любой позиции списка. Списки также можно объединять или разбивать на меньшие списки. Списки регулярно используются в приложениях, например, в программах информационного поиска, трансляторов программных языков или при моделировании различных процессов.
По своему назначению списки похожи на одномерные массивы, но у них есть одно существенное отличие: при работе со списками, как и при работе с файлами, существует понятие текущего элемента, то есть элемента, с которым мы работаем в настоящий момент.
Перечислим основные операции, которые нужно уметь выполнять со списками:
- вставлять элемент в произвольную позицию в списке, сдвигая при этом последующие позиции
- получать позицию некоторого элемента. Если таких элементов несколько, то первый из них, если таких элементов нет, то некоторое специальное значение (например, -1)
- получать элемент по его позиции в списке
- удалять элемент из списка
- получать следующий и предыдущий элементы
- обнулять список
- получать позицию первого элемента и сам этот элемент.
Обычно списки реализуют либо с помощью массивов, либо с помощью указателей. Рассмотрим обе реализации и затем сравним их между собой.
Для реализации списка удобно использовать объект, в котором будет храниться вся информация о списке, собственно список и методы его обработки.
Для реализации списка массивом имеем:
TList=class
Data: array of TElemType;
CurElem: integer;
procedure Insert(elem: TElemType; i: integer);
procedure Delete(i: integer);
procedure Clear();
constructor Create(n: integer);
end;
Комментарий:
Здесь представлен код на языке Object Pascal/Delphi. При записи на Turbo Pascal'е нужно заменить ключевое слово class на object, хотя и там и там можно использовать объекты, но при работе с Delphi более предпочтительным является класс, так как классы предоставляют программисту большие возможности, чем объекты. В TP нет динамических массивов, поэтому придется использовать статический массив, длины которой должно заведомо хватить для решения конкретной задачи (например, 100 или 1000):
Data: array[1..1000]of integer;
Массив Data имеет тип TElemType, который и представляет собой элементы списка. Переменная CurElem представляет собой индекс текущего элемента. Назначение следующих трех процедур ясно из их названия. В конструкторе Create будет создаваться динамический массив и его длина будет установлена равной n (поскольку в TP массив статический, то нам понадобится дополнительная переменная для текущей длины массива).
Мы не будем реализовывать указанные методы, поскольку списки довольно редко представляют с помощью массивов, скажем лишь, что для вставки нужно увеличить размер массива и освободить место, скопировав все элементы на соседние позиции. Аналогично реализуется удаление элемента.
Для реализации списка с помощью указателей нам понадобится та структура, о которой мы рассказывали в предыдущем выпуске. Перепишем ее с учетом наших потребностей:
PElem=^TElem;
TElem=record
Data: TDataType;
next: PElemType;
end;
TList=class
FirstElem, CurElem: PElem;
procedure Insert(elem: TElemType);
procedure Delete();
procedure Clear();
constructor Create();
end;
Комментарий:
PElem - тип указателя на элемент списка TElem, Data - информационное поле списка, Next - указатель на следующий элемент списка. FirstElem и CurElem в классе TList - соответственно указатели на первый и текущий элемент списка; методы Delete() и Insert() соответственно удаляют и вставляют новый элемент на текущее место. В конструкторе же просто обнуляются все указатели.
Примечание: если вы не знакомы или мало знакомы с понятием объекта/класса, то можете использовать просто записи, а обрабатывать их либо просто процедурами, либо непосредственно в тексте программы. Следует также отметить, что для реализации списков объекты целесообразно использовать лишь в больших программах, а в небольших обычно применяют записи.
Графически такие списки можно представить следующим образом:
+----++ +----++ +----++
|data||-->|data||--> ... -->|data||-->nil
+----++ +----++ +----++
Здесь data - информационное поле записи, а пустой прямоугольник - поле связи со следующим элементом списка.
Решим с помощью списка задачу "Считалочка":
Вокруг ведущего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке от 2 до N. Ведущий, начиная с некоторого, ведет счет до M. Человек, на котором закончился счет, выходит из круга. Далее счет начинается со следующего человека и так дол тех пор, пока в кругу не останется один человек. Нужно определить номер оставшегося человека, если известно M и то, что счет начинался с первого человека.
Для решения задачи применим особый вид списков - циклические списки, то есть списки, у которых за последним элементом следует первый: P^.next=FirstElem, где P - последний элемент в списке.
Итак, поехали; комментарии будем давать по ходу самой программы:
type PElem = ^TElem; {наши структуры}
TElem = record
Number: integer; {номер человека}
next: PElem; {указатель на следующего}
end;
var first, cur, temp: PElem;
i,N,M: integer;
inp: text;
begin
first:=nil; {обнуляем указатели}
cur:=nil;
assign(inp,Тinput.txtТ);
reset(inp);
read(inp,N,M); {читаем данные}
close(inp);
for i:=1 to N do {создаем список и заполняем его}
begin
begin {здесь происходит его создание}
new(first);
first^.number:=i;
first^.next:=nil;
cur:=first; {первый становится текущим}
end else
begin
{добавлять можно и так, но как сделать это проще,
сказано ниже}
new(cur^.next);
(cur^.next)^.number:=i;
(cur^.next)^.next:=nil;
cur:=cur^.next; {здесь и происходит связывание}
end; {элементов списка}
end;
cur^.next:=first; {зацикливаем список}
cur:=first; {переходим на его начало}
{пока следующий не совпадет с текущим, то есть в списке
не останется один элемент}
while cur^.next<>cur do
begin
емому элементу, нужно сделать M шагов, но 1 шаг уже
сделан: мы стоим на первом элементе. Последний шаг к
M-ому элементу делать не нужно: далее мы будем его
удалять и нам потребуется обновить связь (M-1)-го
элемента, а если мы все-таки перейдем на M-й элемент,
то обновление связи будет невозможно}
for i:=2 to M-1 do cur:=cur^.next;
{далее будет происходить удаление следующего элемента
из списка. Для этого запомним его адрес в переменной
temp и свяжем текущий ((M-1)-й) элемент со следующим
за удаляемым (M-тым). Таким образом, требуемый элемент
удален. Зачем нам нужно было запоминать его адрес? А
затем, чтобы его можно было удалить и он больше не
занимал место в памяти}
temp:=cur^.next;
cur^.next:=temp^.next;
{текущим становится следующий за удаленным элемент}
cur:=cur^.next;
dispose(temp); {то самое удаление}
end;
writeln(cur^.number);
readln;
end.
Укажем теперь, как можно проще добавить новый элемент в список: для этого можно использовать вспомогательную переменную temp:
new(temp);
temp^.number:=i;
temp^.next:=nil;
cur^.next:=temp;
cur:=cur^.next;
Как видите, при такой реализации процесс вставки реализован более очевидно, но для этого нам пришлось потратить лишнюю строчку кода.
Мы думаем, что на сегодня достаточно теории. В следующем выпуске мы расскажем вам об особых типах списков: стеках, деках и очередях.
Время покодить.
Задача №7. Правильное скобочное выражение.
Дано N пар открывающих и закрывающих скобок. Определим правильное скобочное выражение следующим образом:
- пустое выражение правильное;
- если E - правильное скобочное выражение, то (E), [E], ..., <E> - тоже правильные, причем ( ), [ ], ..., < > - все возможные типы скобок;
- если E и F - правильные скобочные выражения, то EF - тоже правильное;
- других правильных скобочных выражений нет.
Примеры правильных скобочных выражений:
()
[ ( ) ] ( [ [ ( ) ] ] ) [ ] [ [ [ ( ( ) ) ] ] ]
Примеры неправильных скобочных выражений:
(
]
( [ ) ]
( ] [ )
От вас требуется определить, является ли данное скобочное выражение верной.
В входном файле input.txt в первой строке указано N - количество пар скобок (N не превосходит половины печатаемых ASCII-символов), в последующих N строках парами указаны сами скобки: сначала открывающая, затем - закрывающая. В последней строке содержится само выражение (без пробелов) длины не превосходящей 100 000 (предполагается, что кроме скобок последовательность не содержит других символов).
В выходном файле output.txt должно быть слово "correct", если скобочное выражение верно, и слово "incorrect" в противном случае.
Примеры:
input.txt:
2
()
<>
<<()>()>
output.txt:
correct
input.txt:
3
12
34
56
134652
output.txt:
incorrect
Задача №7. Медиана подпоследовательности.
Дана последовательность из N целых неотрицательных чисел. Медианой такой последовательности в случае нечетного N называется элемент, который будет равноудален от концов последовательности, если ее отсортировать по возрастанию ил убыванию. В случае четного N медианой называется среднее арифметическое двух элементов, стоящих на местах N/2 и (N/2)+1 после сортировки последовательности. Требуется по заданной последовательности найти ее медиану.
В первой строке входного файла input.txt содержится N - число элементов последовательности. Во второй строке расположены сами элементы. Каждый элемент последовательности не превосходит числа 65535.
В выходном файле output.txt содержится медиана последовательности.
Пример:
input.txt:
4
3 6 4 5
output.txt:
4.5
Ну что же, спасибо за внимание, и до следующих выпусков.
P.S. Хотим извиниться за скорость ответа на письма, просто не всегда есть возможность добраться до компьютера, а так же хотим лишний раз напомнить вам о том , что авторов у рассылки много. Поэтому будьте внимательны при отправке решений на наш ящик.
Пишите на olimp@math.pomorsu.ru
Ищешь фильм? http://aslof.balzer.ru/
http://subscribe.ru/catalog/rest.cinema.filmforyou
| http://subscribe.ru/
E-mail: ask@subscribe.ru |
Отписаться
Убрать рекламу |
| В избранное | ||
