Задачи по программированию. I семестр

Задача 1. Перевернуть строку неизвестной длины

Считывать из стандартного ввода символы до двух ‘ ‘. Распечатать их в обратном порядке. Длина строки больше 256 символов.

Задача 2. Перевернуть список

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

Задача 3. Найти значение k-ого по возрастанию элемента массива

На входе массив чисел и номер k. Не использовать сортировку, асимптотическая сложность - O(N). Массив можно портить.

Задача 4. Перевернуть биты в индексах массива

На входе массив длины 2^N. Переставить местами значения в ячейках массива, так чтобы в на индексах массива были произведен бит-реверс. То есть переставить A[0101]↔A[1010].

Задача 5. Умножить 2 матрицы NxN

На входе 2 матрицы NxN с коэффициентами с плавающей точкой двойной точности. Вычислить произведение матриц. Сравнить асимптотическую сложность с измеренным временем работы. Определить влияние на время работы транспонирования матриц.

Задача 6. Игра в числа

Петя с Васей играют в числа. Петя загадывает число от 1 до 100 включительно. Вася называет числа до тех пор пока не угадает. Если число меньше загаданного, Вася получает 1 щелбан, если больше, то 2 щелбана. Определить какое минимальное количество щелбанов в худшем случае получит Вася при оптимальном алгоритме игры. Написать программу, реализующую оптимальную оценку в худшем случае. Проверить на всех входных значениях.

Задача 7. Вытесняющий стек

Реализовать стек для значений типа байт с использованием 2N ячеек оперативной памяти. При заполнении всех ячеек данные должны перемещаться в файл, таким образом, чтобы время между последовательными доступами к файлу было максимальным при наихудшей последовательности операций со стеком.

Задача 8. Быстрая сортировка

Реализовать быструю сортировку используя не более одного рекурсивного вызова, не переставляя элементы в отсортированном массиве. Для массивов близких к сортированному время работы должно быть близко к среднему.

Задача 9. Кольцевая гонка

Проверить наличие или отсутствие цикла в односвязном списке за линейное время от длины списка. Данные списка нельзя портить. Можно использовать константное количество памяти.

Задача 10. Трансформация дерева

На входе префиксное выражение из букв и бинарных операций +-*/, например (*/a*bc+de). Преобразовать к инфиксной форме, с использованием только необходимых скобок - a/(b*c)*(d+e). Запрещена замена операций и изменение их порядка по сравнению с префиксной записью.

Задача 11. Поиск минимума разности

На входе последовательность чисел с плавающей точкой двойной точности и положительное число D. Одинаковые числа на входе игнорируются. Считывать до тех пор пока расстояние между любыми двумя соседними в порядке сортировки числами больше D. Вывести в порядке сортировки. Пример: на входе D = 1.0; 0.0, 2.0, 4.0, 0.0, 6.0, 1.0, 7.0, 6.0; ответ: 0.0, 1.0, 2.0, 4.0, 6.0

Задача 12. Подсчет слов

На входе последовательность слов. Подсчитать количество повторений каждого слова.

Задача 13. Коммутативный хэш

Реализовать структуру для хранения ребер неориентированного графа со сложностью добавления и удаления О(1).

Задача 14. Избыточность сети

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

Задача 15. Расписание

Построить оптимальное расписание выполнения заданий, связанных по данным для одного процессора. На входе ориентированный ациклический граф с весами на вершинах, заданный списками смежности вершин. Вершины графа - задания, ребра - связи по данным, веса вершин - время исполнения заданий. Вывести расписание в виде списка пар чисел (номер задания, время начала выполнения).

Задача 16. Ханойские башни по-новому

Для заданного N - количества дисков распечатать последовательность переносов дисков для задачи Ханойские башни. Программа должна требовать O(1) памяти. Проверить совпадение результатов с рекурсивной версией.