Программирование на C++

Цель занятия: освоить передачу массивов в функции, адресную арифметику, изменение массива на месте и обработку статических матриц.

Необходимые темы и конструкции C++:

• статические одномерные и двумерные массивы
• указатели, разыменование и nullptr
• связь имени массива с указателем на первый элемент
• передача массива в функцию, const-корректность
• адресная арифметика и диапазон, заданный указателем и длиной

Структура проекта

Разместите решение в следующих файлах:

• main.cpp
• array_tasks.h
• array_tasks.cpp

Общие требования

• Соблюдайте указанные сигнатуры функций: ввод и вывод организуйте в main.
• Проверьте каждую функцию не менее чем на трёх наборах данных, включая граничный случай.
• Не используйте средства, которые не перечислены в разделе необходимых тем, если условие прямо их не разрешает.

Основные задания

1. Вывод элементов массива на консоль Создать два шаблона функций

   template<typename T>
   void output_array(const T* array, size_t size)
   {
       // TODO: определение шаблона  
   }
   
   template<typename T>
   void output_array(const T* begin, const T* end)
   {
       // TODO: определение шаблона  
   } 
     

   Оба шаблона должны выводить на консоль элементы массива.

   Пример работы. Исходный код

   int integers[] = {1,2,3,4,5};
   double doubles[] = {1.2, 2.3, 3.4, 4.5, 5.6};
   output_array(integers, 5);
   output_array(doubles, doubles + 5);
     

   Вывод

       1, 2, 3, 4, 5,
       1.2, 2.3, 3.4, 4.5, 5.6,  

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

2. Статистика массива

   Для непустого массива целых чисел вычислить сумму, минимальный и максимальный элементы. Сумму вернуть из функции, минимум и максимум записать через ссылки.

   Требуемая сигнатура:

   long long statistics(const int* data, int size, int& minimum, int& maximum);

   Требования:

   • Не изменяйте исходный массив.
   • В цикле используйте указатель, а не индекс.

   Входные данные / вызов	Результат
   [4, -2, 7, 7, 1]	sum=17; min=-2; max=7

3. Разворот и циклический сдвиг

   Сначала развернуть массив на месте. Затем реализовать циклический сдвиг вправо на одну позицию. Обе операции оформите отдельными функциями.

   Требуемая сигнатура:

   void reverse(int* data, int size);
   void rotate_right(int* data, int size);

   Требования:

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

   Входные данные / вызов	Результат
   [1, 2, 3, 4]	reverse -> [4, 3, 2, 1] rotate_right -> [1, 4, 3, 2]

4. Вывод элементов матрицы на консоль
   Создать шаблон функции

   template<typename T, size_t COLS>
   void output_matrix(const T matrix[][COLS], size_t rows)
   {
       // TODO: определение шаблона  
   }      
       

   Пример работы.

   Исходный код

   int matrix[][3] = 
     {
       {1,2,3},
       {4,5,6},
       {7,8,9}
     };
   output_matrix(matrix, 3);      
   

   Вывод

   1, 2, 3,
   4, 5, 6,
   7, 8, 9,      
       

   Указания:

   • Матрицу передавайте как двумерный статический массив с известным числом столбцов.
   • не пользуемся индексами, пользуемся указателями, арифметикой указателей и операцией разыменования.
   • не пользуемся вложенными циклами, пользуемся шаблоном output_array

5. Строки матрицы

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

   Требуемая сигнатура:

   constexpr int COLS = 4;
   int row_sum(const int matrix[][COLS], int row);
   int row_with_max_sum(const int matrix[][COLS], int rows);

   Требования:

   • Матрицу передавайте как двумерный статический массив с известным числом столбцов.

   Входные данные / вызов	Результат
   [[1,2,3,4], [9,0,0,0], [-1,5,8,0]]	row=2; sum=12

Домашнее задание

1. Удаление всех вхождений

   Удалить из массива все элементы, равные заданному значению. Физический размер массива не меняется; функция возвращает новый логический размер, а оставшиеся элементы сдвигаются к началу.

   Требуемая сигнатура:

   int remove_all(int* data, int size, int value);

   Требования:

   • Время работы — \(O(n)\), один проход по исходным элементам.

   Входные данные / вызов	Результат
   [2, 5, 2, 7, 2], value=2	size=2; [5, 7]

2. Слияние упорядоченных массивов

   Даны два массива, упорядоченных по неубыванию. Записать все их элементы в третий массив, сохраняя порядок.

   Требуемая сигнатура:

   void merge(const int* first, int first_size, const int* second, int second_size, int* result);

   Требования:

   • Используйте два указателя; время работы — \(O(n+m)\).
   • Размер результирующего массива должен быть не меньше суммы размеров исходных.

   Входные данные / вызов	Результат
   [1,4,8], [2,2,9]	[1,2,2,4,8,9]

3. Седловая точка

   Найти элементы матрицы, которые одновременно являются минимальными в своей строке и максимальными в своём столбце. Вывести их координаты и значения.

   Требуемая сигнатура:

   constexpr int COLS = 5;
   void print_saddle_points(const int matrix[][COLS], int rows);

   Требования:

   • Если седловых точек нет, вывести соответствующее сообщение.
   • Дополнительную матрицу не создавать.