Вариант: поиск на графе
./prog preprocess --nodes <nodes file> --edges <edges file> --output <preprocessed graph>
./prog search --graph <preprocessed graph> --input <input file> --output <output file> [--full-output]
Файл узлов
<id> <lat> <lon>
Файл рёбер
<длина пути в вершинах [n]> <id 1> <id 2> … <id n>
Выходной файл
<длина найденного пути с относительной погрешностью не более 1e-6>
<длина пути в вершинах [n]> <id 1> <id 2> … <id n>
Расстояние между точками следует вычислять как расстояние между точками на сфере с радиусом 6371км, если пути между точками нет, вывести -1 и длину пути в вершинах 0.
Алгоритм: astar
Алгоритм: поразрядная сортировка.
Требуется разработать программу, осуществляющую ввод пар «ключ- значение», их упорядочивание по возрастанию ключа указанным алгоритмом сортировки за линейное время и вывод отсортированной последовательности.
Ключи - даты в формате DD.MM.YYYY , например: 1.1.1 , 1.9.2009 , 01.09.2009 , 31.12.2009, данные - числа от 0 до 2 64 - 1.
Структура данных - PATRICIA.
Необходимо создать программную библиотеку, реализующую указанную структуру данных, на основе которой разработать программу-словарь.
В словаре каждому ключу, представляющему из себя регистронезависимую последовательность букв английского алфавита длиной не более 256 символов, поставлен в соответствие некоторый номер, от 0 до 2 64 - 1. Разным словам может быть поставлен в соответствие один и тот же номер.
Программа должна обрабатывать строки входного файла до его окончания. Каждая строка может иметь следующий формат:
word 34 — добавить слово «word» с номером 34 в словарь. Программа должна вывести строку «OK», если операция прошла успешно, «Exist», если слово уже находится в словаре.
- word — удалить слово «word» из словаря. Программа должна вывести «OK», если слово существовало и было удалено, «NoSuchWord», если слово в словаре не было найдено.
word — найти в словаре слово «word». Программа должна вывести «OK: 34», если слово было найдено; число, которое следует за «OK:» — номер, присвоенный слову при добавлении. В случае, если слово в словаре не было обнаружено, нужно вывести строку «NoSuchWord».
! Save /path/to/file — сохранить словарь в бинарном компактном представлении на диск в файл, указанный параметром команды. В случае успеха, программа должна вывести «OK», в случае неудачи выполнения операции, программа должна вывести описание ошибки (см. ниже).
! Load /path/to/file — загрузить словарь из файла. Предполагается, что файл был ранее подготовлен при помощи команды Save. В случае успеха, программа должна вывести строку «OК», а загруженный словарь должен заменить текущий (с которым происходит работа); в случае неуспеха, должна быть выведена диагностика, а рабочий словарь должен остаться без изменений. Кроме системных ошибок, программа должна корректно обрабатывать случаи несовпадения формата указанного файла и представления данных словаря во внешнем файле.
Вариант задания: поиск большого количества образцов при помощи алгоритма Ахо-Корасик.
Формат входных данных
Искомый образец задается на первой строке входного файла.
В случае, если в задании требуется найти несколько образцов, они задаются по одному на строку вплоть до пустой строки.
Затем следует текст, состоящий из слов или чисел, в котором нужно найти заданные образцы.
Никаких ограничений на длину строк, равно как на количество слов или числ в них, не накладывается.
Необходимо реализовать алгоритм Укконена построения суффиксного дерева за линейное время. Построив такое дерево для некоторых из входных строк, необходимо воспользоваться полученным суффиксным деревом для решения своего варианта задания.
Алфавит строк: строчные буквы латинского алфавита (т.е., от a до z).
Вариант задания: поиск в известном тексте неизвестных заранее образцов
Входные данные: текст располагается на первой строке, затем, до конца файла, следуют строки с образцами.
Выходные данные: для каждого образца, найденного в тексте, нужно распечатать строчку, начинающуюся с последовательного номера этого образца и двоеточия, за которым, через запятую, нужно перечислить номера позиций, где встречается образец в порядке возрастания.
Необходимо разработать программную библиотеку на языке C или C , реализующую простейшие арифметические действия и проверку условий над целыми неотрицательными числами. На основании этой библиотеки, нужно составить программу, выполняющую вычисления над парами десятичных чисел и выводящую результат на стандартный файл вывода.
Список арифметических операций:
- Сложение ( ).
- Вычитание (-).
- Умножение (*).
- Возведение в степень (^).
- Деление (/).
В случае возникновения переполнения в результате вычислений, попытки вычесть из меньшего числа большее, деления на ноль или возведении нуля в нулевую степень, программа должна вывести на экран строку Error.
Список условий:
- Больше (>).
- Меньше (<).
- Равно (=).
В случае выполнения условия, программа должна вывести на экран строку true, в противном случае — false.
При помощи метода динамического программирования разработать алгоритм решения задачи, определяемой своим вариантом; оценить время выполнения алгоритма и объем затрачиваемой оперативной памяти. Перед выполнением задания необходимо обосновать применимость метода динамического программирования.
Вариант задания: игра с числом.
Имеется натуральное число n. За один ход с ним можно произвести следующие действия:
- Вычесть единицу
- Разделить на два
- Разделить на три
При этом стоимость каждой операции - текущее значение n. Стоимость преобразования - суммарная стоимость всех операций в преобразовании. Вам необходимо с помощью последовательностей указанных операций преобразовать число n в единицу таким образом, чтобы стоимость преобразования была наименьшей. Делить можно только нацело.
Разрабтать жадный алгоритм решения задачи, определяемой своим вариантом. Доказать его корректность, оценить скорость и объём затрачиваемой оперативной памяти.
Вариант задания: оптимальная сортировка чисел
Дана последовательность длины N из целых чисел 1, 2, 3. Необходимо найти минимальное количество обменов элементов последовательности, в результате которых последовательность стала бы отсортированной.
Входные данные: число N на первой строке и N чисел на второй строке.
Выходные данные: минимальное количество обменов.
Вариант задания: алгоритм Дейкстры
Задан взвешенный неориентированный граф, состоящий из n вершин и m ребер. Вершины пронумерованы целыми числами от 1 до n. Необходимо найти длину кратчайшего пути из вершины с номером start в вершину с номером finish при помощи алгоритма Дейкстры. Длина пути равна сумме весов ребер на этом пути. Граф не содержит петель и кратных ребер.
Входные данные:
В первой строке заданы 1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ start ≤ n и 1 ≤ finish ≤ n. В следующих m строках записаны ребра. Каждая строка содержит три числа – номера вершин, соединенных ребром, и вес данного ребра. Вес ребра – целое число от 0 до 109.
Выходные данные:
Необходимо вывести одно число – длину кратчайшего пути между указанными вершинами. Если пути между указанными вершинами не существует, следует вывести строку "No solution" (без кавычек).