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

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

Здесь и далее по умолчанию массив будет полагаться одномерным.
Подмассивом 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.

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

5.

1. Расположите все отрицательные элементы массива в его начале.
2. Напишите функцию int separate(int *a, int n), которая перестраивает массив a длины n следующим образом: Пусть в исходном массиве a[0] = x. Тогда в перестроенном массиве сперва должны идти элементы меньшие x (в любом порядке), затем x (это бывший arr[0], пусть его новый индекс будет равен k, т. е. в перестроенном массиве a[k] = x), затем все остальные (т .е. большие либо равные x также в любом порядке). Функция должна возвращать k.
3. (вариант задачи о голландском флаге) Расположите все элементы массива неотрицательных чисел a[n], следующим образом: сперва числа кратные трем, затем дающие остаток один при делении на три, а затем дающие остаток два при делении на три.

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

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