2025/26, 9-профиль, задание 7 - Функции, указатели

A: Сократите дробь

Даны два натуральных числа \(n\) и \(m\). Сократите дробь \(\frac{n}{m}\), то есть найдите других числа \(p\) и \(q\) таких, что \(\frac{n}{m}=\frac{p}{q}\) и дробь \(\frac{p}{q}\) — несократимая.

Решение оформите в виде функции void reduce_fraction(int & n, int & m), получающей значения n и m по ссылке и изменяющей их.

B: Деление с остатком

Даны два целых числа \(a\) и \(b\). Найдите их целочисленное частное \(q\) и остаток от деления \(r\) в соответствии с тем, как это принято в языке Python и описано в книге «Конкретная математика», а именно \((q=\lfloor a/b\rfloor)\), \(r=a - qb\).

Решение оформите в виде функции void div_mod(int a, int b, int & q, int & r), где a — делимое, b — делитель, q — переменная для записи частного, r — переменная для записи остатка.

C: Линейный поиск

Рассмотрим пример функции int find(int * a, int n, int key), которая осуществляет поиск элемента, равного key в данном массиве a из n элементов.

int find(int * a, int n, int key)
{
    for (int i = 0; i < n; ++i)
        if (a[i] == key)
            return i;
    return -1;
}

Теперь реализуйте аналогичную функцию при помощи цикла while, не используя if, break, return внутри цикла.

D: Разворот массива

Напишите функцию void reverse(int * a, int n), которая разворачивает элементы массива в обратном порядке.

E: Циклический сдвиг

Дан массив из \(n\) (\(1 \le n \le 100000\)) целых чисел и число \(k\) (\(|k| \le 100000 \)). Циклически сдвиньте массив на \(|k|\) элементов вправо, если \(k\) — положительное и влево, если отрицательное число. То есть все элементы переходят в элементы, индексы которых отличаются на \(k\) с учётом зацикливания: элемент с индексом \(0\) переходит в индекс \(k\), элемент с индексом \(1\) переходит в индекс \(k+1\), а в индекс \(0\) перейдёт элемент с индексом \(n - k\).

При этом число \(k\) может быть и отрицательным, может быть больше \(n\) и т.д.

Решение оформите в виде функции void shift(int * a, int n, int k).

Решение должно иметь сложность \(O(n)\), то есть не должно зависеть от \(k\). Дополнительным массивом пользоваться нельзя.

Примечания

Указание. Нужно развернуть весь массив, а потом развернуть первые его \(k\) элементов и последние \(n - k\) элементов. Используйте функцию reverse для этого.

F: Подвинуть в начало, подвинуть в конец

Напишите две функции void move_front(int * a, int n) и void move_back(int * a, int n), переставляющие минимальный элемент масива на первую и на последнюю позицию в массиве соответственно, не меняя порядка следования других элементов. Порядок следования остальных элементов массива не должен меняться. Если в массиве несколько равных минимальных элементов, то функция move_front передвигает первый минимальный элемент, а функция move_back — последний.

То есть если исходный массив был {1, 2, 3, 0, 4, 0, 5, 0, 6, 7}, то функция move_front получит массив {0, 1, 2, 3, 4, 0, 5, 0, 6, 7}, а функция move_back получит массив {1, 2, 3, 0, 4, 0, 5, 6, 7, 0}.

Сдайте на проверку сразу две функции.

G: Колокол

Дан массив. Переставьте его минимальный элемент в начало, второй по величине  в конец, третий по величине  в начало за минимальным, четвёртый по величине — в конец перед максимальным и т.д.

Например, из массива {7, 8, 4, 7, 6, 5, 2} получится массив {2, 5, 7, 8, 7, 6, 4}.

Предполагается решение за \(O(n^2)\). Оформите решение в виде функции void bell(int * a, int n), используйте функции из предыдущей задачи.

H: Сжатие массива

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

Решение оформите в виде функции int compress(int * a, int n). Функция возвращает количество ненулевых элементов в начале массива.

Например, массив {4, 0, 5, 0, 3, 0, 0, 5} должен быть превращён в массив {4, 5, 3, 5, 0, 0, 0, 0}, а функция возвращает 4.

I: Треугольник Паскаля

Двумерные массивы в языках C и C++ можно представлять, как массив одномерных массивов, то есть массив указателей на тип int (или другой). Получается структура данных типа «указатель на указатель», записываемая как int **. Чтобы выделить память под хранение двумерного массива, вам необходимо сначала выделить память для хранения масива указателей (типа int *), затем циклом выделить память под хранение каждой строки (это уже будет просто массив типа int).

В этой задаче вам надо число \(n\), и вам нужно создать треугольник Паскаля из \(n\) строк. В \(i\)-й строке будет \(i+1\) элемент, значение \(a[i][j]\) должно быть равно \(C_i^j\).

Порядок действий:

  1. Выделить память для хранения \(n\) элементов типа int *.
  2. Пройтись по полученному массиву, выделить память для хранения \(i+1\) элемента типа int, записать полученный адрес в a[i].
  3. Заполнить значения массива a[i], используя соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}\).

Решение оформите в виде функции int ** pascal(int n).

J: Однородный квадрат

Создайте двумерный массив размером \(n\times n\) и заполните его нулями и единицами так, чтобы в любом квадрате размером \(k\times k\) было ровно \(s\) единиц.

Решение оформите в виде функции int ** square(int n, int k, int s). Ограничения: (\(1\le n\le 100\), \(1\le k\le n\), \(0\le s\le k^2\)).

Пример полученного массива для вызова square(3, 2, 1):

0 0 0
0 1 0
0 0 0

Пример полученного массива для вызова square(4, 2, 2):

1 0 0 1
0 1 1 0
1 0 0 1
0 1 1 0