Материалы по курсу «Работа на ЭВМ и программирование» за 2 семестр.

Задача 1. Числа с плавающей точкой

Считать с клавиатуры и построить в памяти число с плавающей точкой (включая inf, -inf, nan, денормализованные числа), используя только операции над его побитовым представлением.

Задача 2. Численное интегрирование

Вычислить значение определённого интеграла заданной в коде программы функции на заданном отрезке с заданной точностью (передаются в форме аргументов командной строки) с помощью составной квадратурной формулы (вариант 1 — трапеций, вариант 2 — Симпсона). Ответ обозначим A, погрешность δ. После этого для полученного количества отрезков (n) вычислить значение по составным формулам средних прямоугольников R и Гаусса G. Вывести на экран:

A  δ  кол-во точек
T  |A-T|
G  |A-G|

Погрешности выводятся в формате %e.

Возможен случай, когда при нескольких итерациях подряд точность не возрастает (и не достигает требуемого значения). В этом случае работу алгоритма нужно остановить и вывести ответ с замечанием, что требуемая точность не была достигнута. Значение функции в каждой точке при вычислении A должно вычисляться только один раз.

Задача 3. Приближенное вычисление значения функции в точке с помощью разложения в ряд Тейлора

Вычислить с помощью разложения в ряд Тейлора значение функции в точке x с точностью ε (передаются в виде аргументов командной строки). Варианты функций: cos x, sin x, eˣ (разложение в ряд в точке x=0), ln x (разложение в ряд в точке x=1).

Программа должна выводить:

• значение
• количество элементов ряда
• модуль разности между найденным приближённым значением и значением функции из стандартной библиотеки в формате %e

Вычислять частичную сумму ряда Тейлора следует только в точках, которые находятся «недалеко» от точки, в которой было выполнено разложение в ряд. Для других точек:

• В случае cos x, sin x нужно воспользоваться периодичностью функции и с помощью тригонометрических формул свести задачу к вычислению значения функции на отрезке [0, π/4].

• В случае eˣ с помощью свойств показательной функции задача сводится к случаю x > 0. Затем x раскладывается на целую и дробную части. Для целой части используется алгоритм быстрого возведения в степень. Для дробной используется разложение в ряд Тейлора.

• В случае ln x с помощью свойств логарифма задача сводится к случаю x > 1. Затем используется представление x в виде (√e)ⁿ (1 + y), |y| < 1.

Дополнительные материалы

Задача 4. Приближенный поиск корня нелинейного уравнения

Входные данные: границы отрезка [a, b] и точность ε (передаются в виде аргументов командной строки).

В коде программы задана функция, непрерывная на отрезке [a, b], такая, что f(a) f(b) < 0 (последнее нужно проверить в программе).

Найти один корень уравнения на этом отрезке с точностью ε с помощью двух методов: бисекции (у всех) и (в зависимости от варианта) касательных, секущих или хорд.

Вывод:

• корень методом бисекции, значение функции в этой точке, количество итераций
• корень другим методом, значение функции в этой точке, количество итераций

Задача 5. Работа с матрицами

С помощью приведения квадратной матрицы к треугольному виду методом Гаусса найти (по вариантам):

1. ранг матрицы и решение системы линейных уравнений в случае максимального ранга;
2. определитель матрицы и решение системы линейных уравнений;
3. ранг матрицы и обратную матрицу в случае максимального ранга;
4. определитель матрицы и обратную матрицу.

Метод Гаусса должен быть реализован с выбором главного элемента по столбцу, или (+1 балл) с выбором главного элемента по всей матрице. В качестве аргументов командной строки передаётся размер матрицы (в этом случае матрица требуемого размера генерируется внутри программы) или имя файла (первое число в файле — размер матрицы, далее — элементы матрицы). Элементы матрицы — числа типа double. Матрица хранится в одномерном массиве типа double*, память под который выделяется динамически.

Ответ выводится на экран. После ответа необходимо дополнительно вывести:

• для решения линейной системы Ax = b — максимальный модуль элемента вектора (Ax - b).
• для обратной матрицы AA⁻¹ — максимум суммы модулей элементов в строках матрицы (AA⁻¹ - I), где I — единичная матрица.

Задача 6. Реализация функций стандартной библиотеки для работы со строками

Написать собственные реализации функций работы со строками из заголовочного файла <string.h>, используя только циклы и операции работы с массивами.

Реализация должна сопровождаться набором тестов, которые сравнивают работу вашей реализации с реализацией из стандартной библиотеки на разных наборах данных, включая NULL-указатели, и интерактивной программой для тестирования, которая запрашивает с клавиатуры исходные строки и прочие аргументы, которые нужны для этой функции, и выводит на экран результат применения вашей функции и результат применения функции из стандартной библиотеки.

Материалы: https://en.cppreference.com/w/c/string/byte

Варианты:

1. memcpy, memchr
2. memset, memcmp
3. strdup, strtok
4. strcat, strstr
5. strlen, strncpy
6. strncmp, strspn
7. strcmp, strrchr
8. strcpy, strchr
9. strcspn, strncat
10. strpbrk, memmove

Задача 7. Работа с кодировкой UTF-8 (bonus)

1. (1 балл) Написать программу, которая считывает с командной строки коды Unicode (UCS-4) символов и выводит эти символы на экран в кодировке UTF-8.

2. (2 балла) Написать программу, которая считывает с командной строки фрагменты имён символов из файла UnicodeData.txt и выводит на экран первый подходящий символ в кодировке UTF-8. https://www.unicode.org/Public/13.0.0/ucd/UnicodeData.txt

Задача 8. Содержательная работа со строками

Во всех задачах ответ выводится в поток стандартного вывода.

1. В аргументе командной строки передаётся набор символов. Заменить в файле каждую последовательность повторяющихся символов из набора на одну такую последовательность. Пример вызова программы (заменить "121212" на "12"):

./a.out "12" input.txt

2. Заменить всюду в файле один заданный в аргументе командной строки набор символов на другой (с учетом разницы в их длине).

./a.out "q" "qwe" input.txt

3. Вывести все слова из данного файла в другой файл в порядке их появления по одному слову на строке без дублирования. Слова отделяются пробелами.
4. Вывести номера строк исходного файла и номер позиции в строке, где встречается заданное в аргументе командной строки слово. Слова отделяются пробелами.
5. Определить максимальную, минимальную и среднюю длину слов из данного файла, а также частоту (процент) встречаемости каждого символа.
6. Вывести все слова из данного файла в алфавитном порядке.
7. Разрезать «длинные» строки в файле по пробелам на более короткие (не более заданной в аргументе командной строки длины).
8. Удалить из файла часть текста между двумя «скобками», где скобки — это заданные в аргументе командной строки наборы символов. Например, убрать из файла комментарии в стиле C:

./a.out '/*' '*/' input.txt

9. Реализовать инструкцию типа #include, т.е. вставить содержимое файла filename в то место файла, где встречается строка #include filename.
10. Реализовать инструкции типа #define и #undef, т.е. выполнить указанные подстановки в области их задания (#define A 5 ... #undef).
11. Реализовать инструкции типа #ifdef #else #endif, т.е. оставить в файле требуемый текст в зависимости от условия (#ifdef A ... #else ... #endif), пример вызова программы:

./a.out A input.txt

12. Отформатировать абзацы текста в заданных границах и с красной строкой (без разбиения слов). Абзац — это фрагмент текста между пустыми строками