"Программирование на Си" 2 и 3 семестры, BMSTU(Bauman Moscow), IU7, 2017

Автоперенос из GitLab(кафедры), если есть какие-то проблемы или недочеты- отпишите

ПЕРВАЯ ЧАСТЬ.

Лабораторная работа 1.

Задача 1

Даны основания равнобедренной трапеции и угол при большем основании. Найти площадь трапеции.

Задача 2

include studio.h

main{}

(

 int s;

 s: = 56;

 print (Year has s weeks)

)

Задача 3

Смешано v₁ литров воды температуры t₁ с v₂ литрами воды температуры t₂. Найти объем и температуры образовавшейся смеси.

Задача 4

Определите номер подъезда и этажа по номеру квартиры девятиэтажного дома, считая, что на каждом этаже ровно 4 квартиры, а нумерация квартир начинается с первого подъезда

Лабораторная работа 2.

Задача 1

Последовательность Фибоначчи определяется так:
F₀ = 0, F₁ = 1, F_k = F_k-1 + F_k-2 при k >= 2.
Дано n, вычислить F_n.

Задача 2

Дана точка и треугольник заданный координатами своих вершин. Определить лежит ли точка внутри, на границе или вне этого треугольника

Задача 3

Вычислит с точность eps:

• приближенное значение функции s(x);
  
• точное значение функции f(x);
  
• абсолютную |f(x)-s(x)| и |f(x)-s(x)|/|f(x)| относительную ошибки приближенного значения.
  
  

s(x) = x + x³/(23) + 3x⁵/(245) + 35x⁷/(2467) + 357x⁹/(24689) + ...
|x| < 1, f(x) = arcsin(x)

Утилита gcov

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

• как часто выполняется каждая строка кода;
  
• какие строки кода не выполняются;
  
• какой процент строк кода покрыт тестами (для каждого файла);
  
• какой процент ветвлений покрыт тестами (для каждого файла).
  
  

gcov обрабатывает программы, которые были получены только с помощью компилятора gcc. При сборке программы желательно выключить оптимизацию с помощью ключа «-O0» и добавить следующие ключи «-fprofile-arcs» и «-ftest-coverage».

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

Лабораторная работа 3.

Задача 1

Пользователь вводит целые числа, по окончании ввода чисел нажимает Ctrl-Z и Enter или вводит букву.

Написать программу, которая:

Определяет количество локальных максимумов в последовательности (Элемент последовательности называется локальным максимумом, если он строго больше предыдущего и последующего элемента последовательности. Первый и последний элемент последовательности не являются локальными максимумами.);

Требования к решению задачи:

- Прототип функции, которая реализует решение задачи, должен выглядеть следующим образом:

int process(FILE *f [, прочие выходные параметры]);

• Функция process возвращает 0 в случае успешного решения задачи и отрицательный код ошибки в противном случае (например, -1 – входных данных нет и т.д.). Для каждого кода ошибки задается мнемоническое имя с помощью директивы define.
  
• При решении любой задачи из варианта 1 два цикла ввода и массивы не использовать.
  
• Необходимо подготовить наборы тестовых данных по классам эквивалентности. Каждый набор разместить в текстовом файле.
  

Задача 2

Написать программу, которая считывает из текстового файла вещественные числа и выполняет над ними некоторые вычисления:

Проверить выполняется ли правило «трех сигм» для чисел;

Требования к решению задачи:

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

Лабораторная работа 4.

Написать программу, которая запрашивает у пользователя элементы целочисленного статического массива и выполняет его обработку. Максимальное количество элементов, которое может ввести пользователь, равно 10.

Реализуйте функции для:

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

Лабораторная работа 5.

Написать программу, которая считывает из текстового файла целые числа в статический массив и Вычислить значение min(x[0]*x[1], x[1]*x[2],x[2]*x[3], ..., x[n-3]*x[n-2], x[n-2]*x[n-1]).
Где x[i] - элементы массива x из n элементов.

Максимальный размер статического массива – 100 элементов. При считывании элементов массива из файла необходимо предусмотреть контроль переполнения массива. Если в файле содержится больше 100 элементов, программа должна выдать соответствующее сообщение и обработать считанные 100 элементов. С оставшимися элементами программа ничего делать не должна.

Имя файла передается через параметры командной строки.

Лабораторная работа 6.

Необходимо реализовать многофайловый проект на основе 5-ой лабораторной работы. Заголовочные файлы оформляются с использованием "include guard". Допущения (если они есть), сделанные при реализации функций, проверяются с помощью утверждений.

Модульные тесты для функции, выполняющей решение основной задачи, оформляются как отдельный проект. Модульные тесты организуются способом, который рассказывался на последнем семинаре по ОПИ (в moodle есть пример).

Для сборки обоих проектов используется утилита make. Оба проекта (основной и модульные тесты) собираются как с отладочной информацией, так и без нее. Запуск модульных тестов из make-файла сразу после сборки тестов оценивается отдельно.

Сборка проекта в Qt Creator организуется с помощью написанного (или написанных) make-файла (файлов).

ВТОРАЯ ЧАСТЬ.

Лабораторная работа 7.

Написать программу, которая упорядочивает (сортирует) массив.

Данные в массив считываются из текстового файла. Количество элементов в файле не указано. Память под массив выделяется динамически. Число элементов в массиве определяется в первом проходе по текстовому файлу, во время второго прохода числа считываются в массив.

Полученный после сортировки массив записывается в другой файл.

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

Функция-фильтр работает следующим образом:

• определяет количество элементов массива, которые удовлетворяют заданному условию;
• выделяет память под соответствующее количество элементов;
• копирует элементы, удовлетворяющие условию, из старого массива в новый.

Функция-фильтр имеет следующее название и прототип:

int key(const int *pb_src, const int *pe_src, int **pb_dst, int **pe_dst);

Функция сортировки реализуется универсальной (т.е. имеет одинаковый прототип с функцией qsort из стандартной библиотеки (stdlib.h)) и называется mysort.

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

Формат запуска приложения должен быть следующим:

app.exe in_file out_file [f]

Для всех функций реализуются модульные тесты (отдельный проект).

При защите лабораторной работы необходимо продемонстрировать отчет утилиты Dr. Memory, свидетельствующий об отсутствии ошибок при работе с памятью. Отчеты Dr. Memory под версионный контроль не помещаются.

Кроме того, необходимо сравнить время работы реализованного алгоритма сортировки и qsort. Постараться найти примеры, когда ваша реализация лучше. Результаты представить в виде графиков (рисунки в формате PNG, оси подписаны). Графики разместить в Wiki на отдельной странице. Графики можно строить любыми средствами (например, в Excel).

Лабораторная работа 8.

Написать программу для работы с матрицами, которая реализует сложение матриц, умножение матриц и вычисление определителя с помощью разложения по строке.

Память под матрицы выделяется динамически 2 методом:

double **data = calloc(n, sizeof(double*));

    if (!data)

        return NULL;



    for (int i = 0; i < n; i++)

    {

        data[i] = malloc(m * sizeof(double));

    }

Исходные матрицы читаются из файла, результирующие матрицы записываются в файл. Один файл содержит одну матрицу. Количество строк и столбцов матрицы указывается в первой строчке файла

Тестирование выполняется с помощью сравнения полученного результата с ожидаемым. При этом нужно помнить, что сравнивать вещественные числа на равенство можно только с заданной точностью.

Имена файлов и выполняемая операция указывается через параметры командной строки.

Формат запуска приложения должен быть следующим:

 app.exe action mtr_1.txt [mtr_2.txt] res.txt 

Возможные значения action:

• a сложение;
  
• m умножение;
  
• o операция по варианту (для нее mtr_2.txt не указывается).
  
  
  
  

Лабораторная работа 9.

Задача 1

Реализовать указанные строковые функции. 1. strpbrk 2. strspn 3. strcspn 4. strchr 5. strrchr 6. strdup 7. strndup

Имена функций, которые реализуются самостоятельно, начинаются с префикса “my_” (если нужно реализовать функцию strpbrk, в программе она должна называться my_strpbrk).

Эта задача подразумевает только реализацию указанных функций и модульных тестов к ним(т.е. никакого отдельного приложения для работы с реализованными функциями можно не писать). При этом в модульных тестах нужно сравнить поведение (спецификацию) своей функции и соответствующей стандартной.

Замечание 1

Функция strdup становится доступной только при указании стандарта gnu99 (т.е. –std=gnu99).

Замечание 2

Функция strndup в библиотеке компилятора MinGW не реализована. Для ее тестирования пишутся модульные тесты, сравнение с реализацией из библиотеки не выполняется.

Замечание 3.

Для компилятора gcc из MSYS2 «замечание 2» не проверялось

Задача 2

Необходимо реализовать следующие функции:

• Чтения строки из текстового файла. Строка должна читаться целиком (т.е. до символа EOL или EOF) за один вызов функции.
  

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

ИЛИ

ssize_t getdelim(char **lineptr, size_t *n, int delimiter, FILE *stream);

Для реализации этих функций запрещается использовать посимвольное чтение из файла. Вместо этого, следует завести статический или динамический буфер небольшого (например, 128 байт) размера, чтение в этот буфер выполнять с помощью fgets, а прочитанные данные из буфера переписывать в результирующую строку. Память под результирующую строку можно выделять с помощью функции realloc.

Имена функций, которые реализуются самостоятельно, начинаются с префикса “my_”

• Замены в строке указанной непустой подстроки произвольной длины на другую подстроку произвольной длины (возможно пустую). Память под результирующую строку выделяется динамически.
  

char* str_replace(const char *source, const char *serach, const char *replace);

С помощью реализованных функций обработать текстовый файл, в котором выполнить замену всех вхождений указанной подстроки на заданную. В файле необходимо обработать все строки. Преобразованные строки записать в новый файл.

Пример

В строке "aaaa" заменяем подстроку "aa" на "bbb". После замены получаем "bbbbbb".

Все параметры передаются как аргументы командной строки.

app.exe in.txt out.txt –s search –r replace

Лабораторная работа 10.

Задачи на работу с одним элементом списка

Необходимо решить любые две задачи.

- Напишите функцию поиска элемента в списке (нужна функция сравнения элементов). (1)

node_t* find(node_t *head, const void *data, int (*comparator)(const void*, const void *));

• Напишите функцию pop_front, которая возвращает указатель на данные из элемента, который расположен в "голове" списка. При этом из списка сам элемент удаляется. (1)

void* pop_front(node_t **head);

• Напишите функцию pop_end, которая возвращает указатель на данные из элемента, который расположен в "хвосте" списка. При этом из списка сам элемент удаляется. (1)

void* pop_back(node_t **head);

• Напишите функцию insert, которая вставляет элемент перед указанным элементом списка (в качестве параметров указываются адреса обоих элементов). (2)

void insert(node_t **head, node_t *elem, node_t *before);

Задачи на работу с целым списком

Необходимо решить одну любую задачу.

- Напишите функцию copy, которая по указанному списку создает его копию (данные при этом не копируются). (1)

int copy(node_t *head, node_t **new_head);
// функция возвращает код ошибки, потому что она выделяет память

• Напишите функцию append, которая получает два списка а и b, добавляет список b в конец a. Список b при этом оказывается пустым. (1)

void append(node_t **head_a, node_t **head_b);

• Напишите функцию remove_duplicates, которая получает упорядоченный список и оставляет в нем лишь первые вхождения каждого элемента. Совпадение определяется с помощью функции сравнения элементов. При удалении элемента списка данные не удаляются. (2)

void remove_duplicates(node_t **head);

• Напишите функцию reverse, которая обращает список. Идеи реализации: o Использование pop_front и двух списков. (1) o Использование 3-х указателей на соседние элементы списка. (2) o Рекурсия. (2)

node_t* reverse(node_t *head);
// возвращается «новая» голова

Сортировка списка

node_t* sort(node_t *head, int (*comparator)(const void *, const void *));
// возвращается «новая» голова

Необходимо реализовать одну из двух сортировок.

- Сортировка вставками

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

void sorted_insert(node_t **head, node_t *element);

Напишите функцию sort, которая получает список и упорядочивает его по возрастанию, используя функцию sorted_insert. (3)

• Сортировка слиянием

Напишите функцию front_back_split, которая получает список и делит его на две половины. Если в списке нечетное число элементов, "серединный" элемент должен попасть в первую половину.

void front_back_split(node_t* head, node_t** back);

Напишите функцию sorted_merge, которая получает два упорядоченных списка и объединяет их в один.

node_t* sorted_merge(node_t **head_a, node_t **head_b);
// Списки становятся пустыми, элементы из них «переходят» в уорядоченный

Используя функции front_back_split и sorted_merge напишите функцию sort, которая реализует рекурсивный алгоритм сортировки слиянием. (4)

Лабораторная работа 11.

Цель работы – приобрести навыки реализации функций с переменным числом параметров.

Студенты должны получить и закрепить на практике следующие знания и умения:

1. Работа с типом va_list.

2. Работа со строками.

3. Перевод чисел из одной системы счисления в другую.

4. Организация корректной работы с буфером ограниченного объема

Общее задание

1. Исходный код лабораторной работы располагается в ветке lab_11. В этой ветке создается папка lab_11, в которой располагается исходный код программы.

2. Реализованные спецификаторы (см. условие задачи) сохраняются в файле format.txt в виде строки «d hx s» (кавычки не указываются).

3. Исходный код должен соответствовать правилам оформления исходного кода.

4. Решение задачи оформляется как многофайловый проект.

5. Для проверки правильности решения задачи реализуются только модульные тесты, в которых нужно сравнить поведение (спецификацию) своей функции и соответствующей стандартной.

6. Ответы на теоретические вопросы, связанные с защитой лабораторной работы, приводятся в отчете к лабораторной работе. Ответы пишутся «своими словами», при этом запрещается любое копирование ответов откуда бы ни было. Вопросы распределяются преподавателем (преподаватель волен варьировать количество вопросов, которых должно быть не менее трех). Для написания отчета используется wiki в GitLab.

Условие задачи
Реализовать собственную версию функции snprintf, обрабатывающую указанные спецификаторы типа. Функция должна называться my_snprintf. При реализации этой функции запрещается использовать любые стандартные функции для обработки строк. Реализуемые спецификаторы (%c, %d, %i, %x, %o, %s) и модификаторы (l и h) распределяются преподавателем.

Справка по функции (англ.): http://pubs.opengroup.org/onlinepubs/9699919799/functions/snprintf.html

Лабораторная работа 12.

Цель работы – приобрести навыки работы (создание и использование) со статическими и динамическими библиотеками.

Студенты должны получить и закрепить на практике следующие знания и умения:

1. Создание библиотек (разработка интерфейса, его реализация, сборка статической и динамической библиотеки).

2. Использование библиотек (вызов функций из библиотеки, различные способы компоновки).

3. Грамотная работа с ресурсами (динамическая память, файлы, описатели библиотек).

Общее задание

1. Исходный код лабораторной работы располагается в ветке lab_12. В этой ветке создается папка lab_12_1_X (где X – вариант функции-фильтра), в которой располагается решение первой задачи, и папка lab_12_2_Y (где Y – вариант заданный преподавателем) – для исходного кода второй задачи.

2. Исходный код должен соответствовать правилам оформления исходного кода.

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

4. Для проверки правильности решения задачи реализуются как модульные, так и функциональные тесты.

5. Ответы на теоретические вопросы, связанные с защитой лабораторной работы, приводятся в отчете к лабораторной работе. Ответы пишутся «своими словами», при этом запрещается любое копирование ответов откуда бы ни было. Вопросы распределяются преподавателем (преподаватель волен варьировать количество вопросов, которых должно быть не менее трех). Для написания отчета используется wiki в GitLab.

2. Индивидуальное задание

Задача 1

Реализовать лабораторную работу 7 с использованием библиотек разного типа. В библиотеку вынести функции ввода/вывода и обработки. Для динамических библиотек использовать два вида компоновки.
Реализацию функцию-фильтр придется изменить таким образом, чтобы выделение памяти выполняла вызывающая сторона.

Задача 2

Реализовать заданные преподавателем функции в виде динамической библиотеки. Язык реализации библиотеки – Си. Библиотеку использовать в скрипте на Python. Для организации взаимодействия между библиотекой на Си и Python использовать модуль ctypes.
Написание модуля расширения для библиотеки необязательно. Если модуль расширения будет написан, то это оценивается отдельно.

Вариант 1

1. Реализовать функцию циклического сдвига массива на k позиций влево.

2. Реализовать функцию, которая из одного массива помещает в другой элементы первого, которые являются полными квадратами.

Вариант 2

1. Реализовать функцию заполнения массива числами Фибоначчи.

2. Реализовать функцию, которая из одного массива помещает во второй массив первое вхождение каждого элемента первого массива.

Вариант 3

1. Реализовать функцию заполнения массива простыми числами.

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