Вступительная работа

Вступительная работа

для поступающих в группы A, B, C, D олимпиадного отделения

ЛКШ—2004

Решением задач теоретической части должен быть текстовый файл в windows-кодировке, либо файл в формате Microsoft Word или в формате rtf. Файл может быть заархивирован архиватором winzip или winrar.

В начале файла должны быть указаны: фамилия, имя школьника, класс, планируемая группа олимпиадного отделения, e-mail.

Решения нужно до 10 июня отправить на адрес *****@***ru

Решением задач практической части должен быть исходный текст программы. В начале файла в комментариях должны быть указаны: фамилия, имя школьника, класс, планируемая группа олимпиадного отделения, номер задачи. Файл (или несколько файлов) могут быть заархивированы архиватором winzip или winrar.

У каждой задачи в скобках указан список групп, на поступающих в которые она ориентирована. Однако вы (при желании) можете прислать решения не только задач для вашей группы, но и других.

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

Пожалуйста, выполняйте работу самостоятельно! Преподавателям важно знать именно ваш уровень знаний, так как учить предстоит именно вас J.

Раздел 1. Теоретическая часть

Задача Т–1 (C, D)

Задача: из строки удалить все пробельные символы. Решение:

procedure delspace(var s:string);

var i:integer;

begin

for i:=1 to length(s) do

if s[i]=' ' then delete(s, i,1);

end;

Постройте пример, на котором данная процедура будет удалять не все пробелы. Объясните, почему так происходит.

Задача Т–2 (A,B,C)

Дан связный невзвешенный граф. Требуется построить каркас (остовное дерево), т. е. выбросить из него некоторые ребра так, чтобы осталось дерево (связный граф без циклов). Какие из перечисленных ниже алгоритмов дают ответ на этот вопрос, какие делают это с наименьшей сложностью:

·  топологическая сортировка

·  алгоритм Прима

·  алгоритм Крускала

·  алгоритм Форда-Фалкерсона

·  алгоритм построения паросочетания в произвольном графе

·  алгоритм Дейкстры

·  алгоритм Форда-Беллмана

·  алгоритм Флойда

·  алгоритм обхода графа в ширину

·  алгоритм обхода графа в глубину

·  алгоритм построения эйлерова цикла

Задача Т-3 (A,B)

В пространстве даны три точки (X1,Y1,Z1), (X2,Y2,Z2), (X3,Y3,Z3). Требуется посчитать площадь треугольника с вершинами в этих точках.

Задача Т-4 (A,B)

Сформулируйте нерекурсивный алгоритм подсчета значения функции Аккермана A(i, j), где i и j — натуральные:

A(1,j)=2j

A(i,1)=A(i-1,2) при i>1

A(i, j)=A(i-1,A(i, j-1)) при i>1, j>1

Задача Т-5 (А,B,C)

Можно ли с помощью алгоритмов:

·  Флойда

·  Форда-Беллмана

установить, есть ли в графе циклы отрицательного веса. Если можно, то каким образом?

Задача Т-6 (A,B,C,D)

Рассмотрим процедуру, которая меняет местами значения двух переменных типа integer без использования дополнительной памяти, то есть если в программе описаны две переменных с и d типа integer, то вызов swap(c, d) меняет местами их значения.

procedure swap(var a, b:integer);

begin

a:=a+b;

b:=a-b;

a:=a-b;

end;

В каком случае это не работает?

Раздел 2. Практическая часть

Задача П–1 (A,B,C)

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

Входные данные. В файле INPUT. TXT записаны два числа (первое — в первой строке, второе — во второй). Каждое из чисел состоит не более, чем из 100 цифр.

Выходные данные. В файл OUTPUT. TXT выведите разность этих чисел.

Пример входного файла	Пример выходного файла
1
123 125	-2

Задача П–2 (A,B,C)

Напишите программу, которая по дате устанавливает день недели.

Примечание: Вам задается дата по новому стилю. Високосными являются годы, номера которых делятся на 4 и не делятся на 100, а также годы, номера которых делятся на 400.

Входные данные. В файле INPUT. TXT записаны три числа числа — D, M, Y — день месяц, год, задающие реальную дату (1£Y£4000).

Выходные данные. В файл OUTPUT. TXT запишите одно число от 1 до 7 — номер дня недели (1 – понедельник, …, 7 — воскресенье).

Пример входного файла	Пример выходного файла
1	4
	3

Задача П-3 (A,B)

Правильной скобочной последовательностью называется такая последовательность, которая состоит из сбалансированных пар скобок, расположенных друг относительно друга правильным образом (либо одна пара строго внутри другой, либо вне). Другими словами, если взять любое арифметическое выражение, и удалить из него все, кроме скобок, получится правильная скобочная последовательность. Любую правильную скобочную последовательность можно получить таким образом. Последовательность, которую таким образом получить нельзя, правильной не является.

Пусть возможны скобки двух типов: круглые и квадратные.

Занумеруем все такие правильные скобочные последовательности из двух типов скобок, состоящие из N пар скобок (т. е. длины 2N) в лексикографическом порядке. При этом будем считать, что символы идут в следующем порядке: ( ) [ ].

Напишите программу, которая по номеру последовательности в этом упорядочивании выдает саму скобочную последовательность.

Входные данные. В файле INPUT. TXT в первой строке записано число N, а во второй — номер последовательности. 1£N£20

Выходные данные. В файл OUTPUT. TXT выведите скобочную последовательность.

Пример входного файла	Пример выходного файла
2 1	(())
2 2	()()
2 4	([])

Задача П–4 (D)

Напишите программу, которая раскладывает натуральное число на простые множители.

Входные данные. В файле INPUT. TXT записано одно натуральное число (из диапазона от 2 до 2*109).

Выходные данные. В файл OUTPUT. TXT выведите простые множители в неубывающем порядке.

Пример входного файла	Пример выходного файла
68	2 2 17
17	17

Задача П–5 (C, D)

Напишите программу, упорядочивающую набор чисел по неубыванию.

Входные данные. В файле INPUT. TXT записано сначала число N (1£N£2000), а затем набор из N целых чисел, каждое по модулю не превышает 200000.

Выходные данные. В файл OUTPUT. TXT выведите числа набора, отсортированные в порядке неубывания.

Теоретическое задание. Укажите, какова сложность использованного вами для сортировки алгоритма и обоснуйте, почему он работает правильно (ответ на этот вопрос должен быть включен в теоретическую часть работы)

Пример входного файла	Пример выходного файла
4

Задача П–6 (B,C,D)

Требуется посчитать (A^B) mod C, где ^ — возведение в степень, а mod — взятие остатка при делении.

Входные данные. В файле INPUT. TXT записаны числа A, B, C (1£A£2*109, 1£B£2*109, 1£C£30000).

Выходные данные. В файл OUTPUT. TXT выведите искомое число.

Пример входного файла	Пример выходного файла
2 2 3	1
20 20 4	0
2	2003