Одномерные массивы.
Здесь и далее по умолчанию массив будет полагаться одномерным; подмассивом a[i..j] я будет называться часть массивa a с индексами от i до j включительно.
Во всех задачах этого листка также по умолчанию предполагается что:
- массив содержит целые числа
- время работы пропорционально длине данного массива (или сумме длин массивов, если их несколько)
- используемая память не зависит от длины массива. (длин массивов)
1.
Выведите за один проход:
- Все четные элементы массива
- Все элементы массивов, стоящие на четных местах (не используя операторов выбора)
- Все элементы массива в обратном порядке.
- Два наибольших элемента массива
- Два наибольших значения элементов массива
- Число элементов, больших предыдущего.
- Среднее арифметическое элементов массива.
- Число локальных экстремумов в массиве (элемент называется локальным экстремумом, если он больше обоих своих соседей или меньше обоих своих соседей). Первый и последний не считаются.
- Число элементов, больших всех предыдущих.
- Все ли элементы массива равны.
2.
Напишите функцию int search(int *v, int n, int val), которая находит в массиве a[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] — в конце.
6.
Даны две последовательности: x[n] и y[k]. Выясните, можно ли получить вторую, путем вычеркивания некоторых элементов из первой.
7.
Дан массив a[n] и массив a1[n-1], полученный удалением из a одного элемента. Выведите удаленный элемент.