Задачи

1. Написать программу на языке С, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в массив строк (строки длиной не более 256 символов), лексикографически сортирует массив строк методом быстрой сортировки делением пополам с рекурсией (требуется собственная реализация) и выводит полученный массив в файл ./t0.txt по одной строке в строку файла.

2. Написать программу на языке С, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в массив строк (строки длиной не более 256 символов), лексикографически сортирует массив строк методом быстрой сортировки делением пополам без рекурсии (требуется собственная реализация) и выводит полученный массив в файл ./t0.txt по одной строке в строку файла.

3. Написать программу на языке С, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в массив строк (строки длиной не более 256 символов), лексикографически сортирует массив строк методом быстрой сортировки QSort (требуется собственная реализация) и выводит полученный массив в файл ./t0.txt по одной строке в строку файла. Можно использовать любую собственную реализацию алгоритма QSort.

4. Написать программу на языке С, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в массив строк (строки длиной не более 256 символов), лексикографически сортирует массив строк с помощью встроенной функции qsort и выводит полученный массив в файл ./t0.txt по одной строке в строку файла.

5. Написать программу на языке С, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t1.txt в массив строк (строки длиной не более 10 символов и состоят только из цифр), лексикографически сортирует массив строк с помощью цифровой сортировки с использованием сортировки подсчетом и выводит полученный массив в файл ./t1.txt по одной строке в строку файла.

6. Написать функцию
float Deg2N(float x,int n);
умножающую число x типа float на множитель 2ⁿ , использующую только сложение степени в представлении числа с числом n.

7. Написать функцию
double Deg2N(double x,int n);
умножающую число x типа double на множитель 2ⁿ , использующую только сложение степени в представлении числа с числом n.

8. На языке С++ написать собственную реализацию стека строк (строки длиной не более 256 символов) неограниченной длины на базе вектора (с реаллокацией памяти в случае заполнения стека). Заполнить стек словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). Вывести все элементы стека в файл ./t0.txt по одному слову в строке.

9. На языке С++ написать собственную реализацию очереди строк (строки длиной не более 256 символов, количество элементов в очереди не более 20). Последовательно заполнять очередь словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку) и при заполнении очереди выводить все элементы очереди в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл).

10. На языке С++ написать собственную реализацию однонаправленного списка строк с фиктивным элементом (строки длиной не более 256 символов). Последовательно заполнить список словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). После считывания всех строк вывести все элементы списка в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл).

11. На языке С++ написать собственную реализацию однонаправленного списка строк с фиктивным элементом (строки длиной не более 256 символов) на основе умных указателей. Последовательно заполнить список словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). После считывания всех строк вывести все элементы списка в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл).

12. На языке С++ написать собственную ссылочную реализацию двунаправленного списка строк (строки длиной не более 256 символов). Последовательно заполнить список словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). После считывания всех строк вывести в обратном порядке все элементы списка в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл, но в обратном порядке).

13. На языке С++ написать собственную ссылочную реализацию двунаправленного списка строк на основе умных указателей (строки длиной не более 256 символов). Последовательно заполнить список словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). После считывания всех строк вывести в обратном порядке все элементы списка в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл, но в обратном порядке).

14. На основе STL создать вектор из K списков целых чисел. Заполнить списки числами, записанными в файле /users/staff/staroverov/lectures/images/t2.txt таким образом, чтобы число, остаток от деления которого на K был бы равен i, заносился бы в список с индексом i. Число K должно вводиться с клавиатуры. Содержимое каждого списка должно быть выведено в отдельную строку файла ./t2.txt (через пробел). При выводе перебирать элементы вектора и списков надо через соответствующие итераторы.

15. Написать собственную реализацию двунаправленного списка строк (строки длиной не более 256 символов) на основе двух стеков, реализованных с помощью STL. Последовательно заполнить список словами из файла /users/staff/staroverov/lectures/images/t0.txt (слова разделяются пробелами, табуляциями и переходами на следующую строчку). После считывания всех строк вывести в обратном порядке все элементы списка в файл ./t0.txt по одному слову в строке (таким образом, все слова из исходного файла должны быть выведены в выходной файл, но в обратном порядке).

16. В файле /users/staff/staroverov/lectures/images/e.txt заданы номера вершин iv0 и iv1, количество вершин в графе и далее в каждой строке файла заданы номера вершин очередного ребра графа и длина данного ребра. С помощью STL реализовать обычный алгоритм Дейкстры, находящий кратчайший путь в графе от вершины с индексом iv0 до вершины с индексом iv1. Список вершин найденного пути и длину пути вывести в файл ./rez.txt .

17. В файле /users/staff/staroverov/lectures/images/e.txt заданы номера вершин iv0 и iv1, количество вершин в графе и далее в каждой строке файла заданы номера вершин очередного ребра графа и длина данного ребра. С помощью STL реализовать модифицированный алгоритм Дейкстры, находящий кратчайший путь в графе от вершины с индексом iv0 до вершины с индексом iv1. Список вершин найденного пути и длину пути вывести в файл ./rez.txt .

18. В файле /users/staff/staroverov/lectures/images/e.txt заданы номера вершин iv0 и iv1, количество вершин в графе и далее в каждой строке файла заданы номера вершин очередного ребра графа. С помощью STL реализовать алгоритм волны, находящий путь в графе от вершины с номером iv0 до вершины с номером iv1 с минимальным количеством ребер. Список вершин найденного пути и длину пути вывести в файл ./rez.txt .

19. Написать программу на языке Python, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в список строк, лексикографически сортирует список стандартной функцией и выводит полученный массив в файл ./t0.txt по одной строке в строку файла.

20. Написать на языке С++ реализацию вектора целых чисел. Размер вектора должен задаваться в параметрах конструктора. Для хранения вектора следует использовать обычный указатель на целые числа. В классе должны быть реализовано все необходимое для соответствия правилу пяти. Для вектора должен работать оператор (операторы) сложения с использованием и без использования r-value-ссылок.

21. Написать на языке С++ реализацию вектора целых чисел. Размер вектора должен задаваться в параметрах конструктора. Для хранения вектора следует использовать обычный указатель на целые числа. В классе должны быть реализовано все необходимое для соответствия правилу пяти. В классе должны быть реализованы обычный, const- и reverse-итераторы.

22. Реализовать на языке С++ криволинейный массив на основе STL-вектора векторов. Вектор должен заполняться данными из файла (массив задается в естественном виде без указания размеров) с использованием ifstream и потокового итератора ввода. Вывести полученный массив на экран.

23. Написать программу на языке С++, которая вводит все слова, разделенные пробелами, табуляциями и переходами на следующую строчку, из файла /users/staff/staroverov/lectures/images/t0.txt в массив string, лексикографически сортирует массив строк с STL-алгоритма sort и выводит полученный массив в файл ./t0.txt по одной строке в строку файла.

24. Написать на языке C++ реализацию вектора неограниченной длины (с различной реализацией обращения к элементам слева и справа от знака присваивания) целых чисел. Проверить реализацию.

25. Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Необходимо определить, является ли данная последовательность правильной. Пустая последовательность является правильной. Если A правильная, то последовательности (A), [A], {A} правильные. Если A и B правильные последовательности, то последовательность AB правильная. К примеру, ([]{}) – правильная последовательность, а (} и ()) – неправильные.

26. Рассмотрим массив целых чисел, в котором нет повторяющихся элементов. Нужно преобразовать этот массив в строку, «сворачивая» соседние по числовому ряду числа в диапазоны (выводя для диапазона первое и последнее значение через тире). К примеру, массив {1, 4, 5, 2, 3, 9, 8, 11, 0} преобразуется в строку “0-5,8-9,11”, массив {1, 4, 3, 2} – в строку “1-4”, а массив {1, 4} – в строку “1,4”.

27. Рассмотрим две строки. Нужно определить, возможно ли из одной строки получить другую с помощью ровно одного исправления (удаления, добавления либо изменения символа). К примеру, для пар строк {“cat”, “cats”}, {“cat”, “cut”}, {“cat”, “cast”}, {“cat”, “at”} ответ положительный, для пар строк {“cat”, “dog”}, {“cat”, “act”} – отрицательный.

28. Рассмотрим строку. Необходимо определить, является ли она палиндромом (т.е. читается ли одинаково слева направо и справа налево – без учёта знаков препинания, пробелов и вообще любых символов, не являющихся буквами). К примеру, строки “Kazak”, “A roza – upala na lapu Azora!”, “ Do geese see God?”, “Madam, I’m Adam” – являются палиндромами.

29. Рассмотрим массив из целых чисел, упорядоченных по возрастанию. Нужно за линейное время найти в нём все пары элементов, сумма которых равна указанной. К примеру, для массива {-1, 2, 7, 8, 10, 13, 19} и заданной суммы 9 необходимо найти пары {-1, 10} и {2, 7}.