discrete analysis
Вариант: поиск на графе
./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” (без кавычек).