Школа179: Oner Xaum/ОднМассивы ...

Одномерные массивы.

Здесь и далее по умолчанию массив будет полагаться одномерным.
Подмассивом a[i..j] будет называться часть массивa a с индексами от i до j включительно.

Во всех задачах этого листка также по умолчанию предполагается что:

• массив содержит целые числа
• время работы пропорционально длине данного массива (или сумме длин массивов, если их несколько)
• размер используемой памяти не зависит от длин исходных массивов.
• начиная со второй задачи задания оформляются как отдельные функции.

1.
Выведите за один проход:

1. Все четные элементы массива
2. Все элементы массивов, стоящие на четных местах (не используя операторов выбора)
3. Все элементы массива в обратном порядке.
4. Два наибольших элемента массива
5. Два наибольших значения элементов массива
6. Число элементов, больших предыдущего.
7. Среднее арифметическое элементов массива.
8. Число локальных экстремумов в массиве (элемент называется локальным экстремумом, если он больше или меньше обоих своих соседей). Начальный и конечный элементы не считаются.
9. Число элементов, больших всех предыдущих. (начальный элемент полагаем подходящим всегда)
10. Все ли элементы массива равны.

2.
Напишите функцию int search(int *arr, int n, int val), которая находит в массиве arr[n] элемент, значение которого равно val. Функция возвращает индекс найденного элемента или -1, если такого элемента в массиве нет. Попробуйте реализовать данный алгоритм без if внутри цикла.

3.

1. Переверните заданный массив a.
2. Переверните заданный головной подмассив a[0..j]
3. Переверните заданный хвостовой подмассив a[i..n-1]
4. Переверните заданный подмассив a[i..j]

4.

1. Сдвиньте a по кругу на одно место вправо.
2. Сдвиньте подмассив a[i..j] по кругу на одно место вправо.
3. Сдвиньте подмассив a[i..j] по кругу на одно место влево.
4. В заданном массиве a[n] для заданного k | 0 < k < n поменяйте местами подмассивы a[0..k] и a[k+1..n-1]

5.

1. Расположите все отрицательные элементы массива в его начале.
2. (задача о голландском флаге) Расположите все элементы массива a[n], меньшие a[n/2] в начале, а большие a[n/2] — в конце.

6.
Даны две последовательности: x[n] и y[k]. Выясните, можно ли получить вторую, путем вычеркивания некоторых элементов из первой.

7.
Дан массив a[n] и массив a1[n-1], полученный удалением из a одного элемента. Выведите удаленный элемент.