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

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

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

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

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

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

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

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

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

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

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

На входе последовательность чисел с плавающей точкой двойной точности и положительное число 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

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

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

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

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

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