Одномерные массивы.
Здесь и далее по умолчанию массив будет полагаться одномерным.
Подмассивом a[i..j] будет называться часть массивa a с индексами от i до j включительно.
Во всех задачах этого листка также по умолчанию предполагается что:
- массив содержит целые числа
- время работы пропорционально длине данного массива (или сумме длин массивов, если их несколько)
- размер используемой памяти не зависит от длин исходных массивов.
- начиная со второй задачи задания оформляются как отдельные функции.
Задачи
0.
a) Напишите функцию swap, которая меняет местами две целые величины.
(2)b) Напишите функцию
void swap(int *a, int i, int j), которая меняет местами элементы a[i] и a[j]. (1)1.
Выведите за один проход:
a) Все четные элементы массива
(1)b) Все элементы массивов, стоящие на четных местах (не используя операторов выбора)
(1)c) Все элементы массива в обратном порядке.
(1)d) Два наибольших элемента массива
(1)e) Два наибольших значения элементов массива
(1)f) Число элементов, больших предыдущего.
(1)g) Среднее арифметическое элементов массива.
(1)h) Число локальных экстремумов в массиве (элемент называется локальным экстремумом, если он больше или меньше обоих своих соседей). Начальный и конечный элементы не считаются.
(1)i) Число элементов, больших всех предыдущих. (начальный элемент полагаем подходящим всегда)
(2)j) Все ли элементы массива равны.
(2)2.
(2)Напишите функцию
int search(int *a, int n, int val), которая находит в массиве arr длины n элемент, значение которого равно val. Функция возвращает индекс найденного элемента или -1, если такого элемента в массиве нет. Попробуйте реализовать данный алгоритм без if внутри цикла.3.
a) Переверните заданный массив a.
(2)b) Переверните заданный подмассив a[i..j]
(2)4.
- Сдвиньте a по кругу на одно место вправо.
- Сдвиньте a по кругу на одно место влево.
- Сдвиньте подмассив a[i..j] по кругу на одно место вправо.
- В заданном массиве a[n] для заданного k | 0 < k < n поменяйте местами подмассивы a[0..k] и a[k+1..n-1]
5.
- Расположите все отрицательные элементы массива в его начале.
- Напишите функцию
int separate(int *a, int n), которая перестраивает массив a длины n следующим образом: Пусть в исходном массиве a[0] = x. Тогда в перестроенном массиве сперва должны идти элементы меньшие x (в любом порядке), затем x (это бывший arr[0], пусть его новый индекс будет равен k, т. е. в перестроенном массиве a[k] = x), затем все остальные (т .е. большие либо равные x также в любом порядке). Функция должна возвращать k. - (вариант задачи о голландском флаге) Расположите все элементы массива неотрицательных чисел a[n], следующим образом: сперва числа кратные трем, затем дающие остаток один при делении на три, а затем дающие остаток два при делении на три.
6.
Даны две последовательности: x[n] и y[k]. Выясните, можно ли получить вторую, путем вычеркивания некоторых элементов из первой.
7.
Дан массив a[n] и массив a1[n-1], полученный удалением из a одного элемента и перемешиванием остальных. Выведите удаленный элемент.