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