Во всех задачах этого листка на проверку нужно сдать только тело одной или нескольких функций,
описание которых дано в условии задачи. При проверке к вашим функциям будет добавлена функция
main.
Даны два натуральных числа \(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 по ссылке и изменяющая их.
Даны два целых числа \(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 — переменная
для записи остатка.
Рассмотрим пример функции 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 внутри цикла.
Напишите функцию void reverse(int * a, int n),
которая разворачивает элементы массива в обратном порядке.
Дан массив из \(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 для этого.
Напишите две функции 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}.
Сдайте на проверку сразу две функции.
Дан массив. Переставьте его минимальный элемент в начало, второй по величине в конец, третий по величине в начало за минимальным, четвёртый по величине — в конец перед максимальным и т.д.
Например, из массива {7, 8, 4, 7, 6, 5, 2} получится массив {2, 5, 7, 8, 7, 6, 4}.
Предполагается решение за \(O(n^2)\). Оформите решение в виде функции void bell(int * a, int n),
используйте функции из предыдущей задачи.
Массив заполнен целыми числами. Требуется “сжать” его, переместив все ненулевые элементы в левую часть массива, не меняя их порядок, а все нули в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный массив использовать нельзя, задачу нужно выполнить за один проход по массиву.
Решение оформите в виде функции int compress(int * a, int n).
Функция возвращает количество ненулевых элементов в начале массива.
Например, массив {4, 0, 5, 0, 3, 0, 0, 5} должен быть превращён в массив {4, 5, 3, 5, 0, 0, 0, 0}, а функция возвращает 4.
Двумерные массивы в языках C и C++ можно представлять, как массив одномерных массивов, то есть массив указателей
на тип int (или другой). Получается структура данных типа «указатель на указатель», записываемая как
int **. Чтобы выделить память под хранение двумерного массива, вам необходимо сначала выделить
память для хранения масива указателей (типа int *), затем циклом выделить память под хранение
каждой строки (это уже будет просто массив типа int).
В этой задаче вам надо число \(n\), и вам нужно создать треугольник Паскаля из \(n\) строк. В \(i\)-й строке будет \(i+1\) элемент, значение \(a[i][j]\) должно быть равно \(C_i^j\).
Порядок действий:
int *.
int,
записать полученный адрес в a[i].
a[i], используя соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}\).
Решение оформите в виде функции int ** pascal(int n).
Создайте двумерный массив размером \(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\)).
| Ввод | Вывод |
|---|---|
3 2 1 |
0 0 0 |
4 2 2 |
1 0 0 1 |