Массивы

Часто возникает необходимость хранить не одну переменную, а набор однотипных переменных. Например, список учащихся класса – это набор данных строкового типа, координаты вершин многоугольника или коэффициенты многочлена – это набор числовых данных. Для хранения наборов данных используются структуры данных. Основная структура данных – это массив.

Массив — это структура однотипных данных, занимающих непрерывную область памяти. Массив имеет размер — количество элементов в нем. Каждый элемент массива имеет свой номер (также называемый индексом), обращение к элементу массива осуществляется путем указания его индекса. В языке C++ элементы нумеруются начиная с 0, поэтому последний элемент массива имеет номер на 1 меньше размера массива.

Массив в языке C++ задается следующим образом:

     тип_элементов идентификатор[размер];

где тип_элементов — произвольный тип данных языка C++, который будут иметь элементы массива, например, int, double и т.д.; идентификатор — имя массива, размер — число элементов в нем.

По стандарту языков C и C++, размер массива должен быть константой, определенной на момент компиляции программы, то есть можно определить массив в виде int A[10 + 5], но нельзя это сделать в виде int A[n]. Однако, компилятор gcc, которым мы пользуемся, допускает объявления второго вида, но при этом нет никаких гарантий, что ваша программа будет откомпилирована каким-либо другим компилятором.

К элементу массива можно обращаться, как идентификатор[индекс]. Например, если было сделано объявление

 
double A[5];

то таким образом создается 5 элементов массива типа double: A[0], A[1], A[2], A[3], A[4].

Пример программы, которая создает массив типа int[], заданного пользователем размера, считывает с клавиатуры его элементы, затем прибавляет к каждому элементу массива число 1, затем выводит результат на экран:

#include <iostream>
using namespace std;
int main()
{
    int n;          // Размер массива
    int i;          // Счетчик в циклах
    cin >> n; // Считываем размер массива
    int A[n];       // Объявление массива
                    // Считываем массив
    for (i = 0; i < n; ++i)
    {
	cin >> A[i];
    }
                    // Прибавляем по 1 к каждому элементу
    for (i = 0; i < n; ++i)
    {
        A[i] += 1;
    }
                     // Выводим массив на экран
    for (i = 0; i < n; ++i)
    {
        cout << A[i] << " ";
    }
	             // Переведем курсор на новую строку
    cout << endl;
    return 0;
}

В этом примере при помощи // обозначается начало комментария, весь текст после начала комментария и до конца строки компилятором игнорируется. Второй способ объявления комментария: в начале комментария поставить знаки /*, а в конце – */. Это позволяет делать комментарии, занимающие несколько строк. В языке C допустимы только такие комментарии.

Упражнения

Во всех задачах этого листка (кроме X и Y) небходимо что-то сделать с заданным массивом. Массив вводится, как в примере выше: сначала размер массива, затем его элементы. Программа должна считать массив целиком, выполнить то, что требуется сделать с массивом, вывести результат на экран. Даже если для решения задачи массив не требуется, программа всё равно должна целиком считать массив и сохранить его в памяти.

Все массивы – числовые типа int[].

A: Четные индексы

Выведите все элементы массива с четными индексами (то есть A[0], A[2], A[4], ...).

Программа должна быть эффективной и не выполнять лишних действий!

Ввод	Вывод
5 1 2 3 4 5	1 3 5

B: Четные элементы

Выведите все четные элементы массива.

Ввод	Вывод
7 1 2 2 3 3 3 4	2 2 4

C: Количество положительных

Найдите количество положительных элементов в данном массиве.

Ввод	Вывод
5 1 -2 3 -4 5	3

D: Больше предыдущего

Дан массив. Выведите все элементы массива, которые больше предыдущего элемента.

Ввод	Вывод
5 1 5 2 4 3	5 4

E: Соседи одного знака

Дан массив. Если в нем есть два соседних элемента одного знака, выведите эти числа. Если соседних элементов одного знака нет - не выводите ничего. Если таких пар соседей несколько - выведите первую пару.

Примечание. В этой задаче нужно реализовать алгоритм линейного поиска: найти такую первую пару элементов, удовлетворяющую заданному условию. Алгоритм линейного поиска пишется при помощи цикла while, а не при помощи цикла for.

Ввод	Вывод
5 -1 2 3 -1 -2	2 3

F: Больше своих соседей

Дан массив. Определите, сколько в этом массиве элементов, которые больше двух своих соседей и выведите количество таких элементов.

Ввод	Вывод
5 1 0 1 0 1	1

G: Наибольший элемент

Выведите значение наибольшего элемента в массиве

Ввод	Вывод
5 1 2 3 2 1	3

H: Наименьший положительный

Выведите значение наименьшего из всех положительных элементов в массиве. Известно, что в массиве есть хотя бы один положительный элемент, а значения всех элементов массива по модулю не превосходят 1000.

Ввод	Вывод
5 5 -4 3 -2 1	1

I: Наименьший нечетный

Выведите значение наименьшего нечетного элемента массива, а если в массиве нет нечетных элементов - выведите число 0.

Ввод	Вывод
5 0 1 2 3 4	1
5 2 4 6 8 10	0

J: Шеренга

Петя перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю. Помогите ему это сделать.

Программа получает на вход число N – количество человек в классе. Затем невозрастающая последовательность из N чисел, означающих рост каждого человека в строю. После этого вводится число X – рост Пети. Все числа во входных данных натуральные и не превышают 200.

Выведите номер, под которым Петя должен встать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то он должен встать после них.

Примечание. Это тоже линейный поиск, поэтому необходимо использовать цикл while.

Ввод	Вывод
8 165 163 160 160 157 157 155 154 162	3
8 165 163 160 160 157 157 155 154 160	5

K: Количество различных элементов

Дан массив, упорядоченный по неубыванию элементов в нем. Определите, сколько в нем различных элементов.

Ввод	Вывод
6 1 2 2 3 3 3	3

L: Вывести в обратном порядке

Выведите элементы данного массива в обратном порядке, не изменяя сам массив.

Ввод	Вывод
5 1 2 3 4 5	5 4 3 2 1

M: Переставить в обратном порядке

Переставьте элементы данного массива в обратном порядке, затем выведите элементы данного массива.

Эта задача отличается от предыдущей тем, что вам нужно изменить значения элементов самого массива, поменяв местами A[0] c A[n-1], A[1] с A[n-2], а затем вывести элементы массива, начиная с A[0].

Ввод	Вывод
5 1 2 3 4 5	5 4 3 2 1

N: Переставить соседние

Переставьте соседние элементы массива (A[0] c A[1], A[2] c A[3] и т.д.). Если элементов нечетное число, то последний элемент остается на своем месте.

Ввод	Вывод
5 1 2 3 4 5	2 1 4 3 5

O: Циклический сдвиг вправо

Циклически сдвиньте элементы массива вправо (A[0] переходит на место A[1], A[1] на место A[2], ..., последний элемент переходит на место A[0]).

Используйте минимально возможное количество операций присваивания.

Ввод	Вывод
5 1 2 3 4 5	5 1 2 3 4

P: Переставить min и max

В массиве все элементы различны. Поменяйте местами минимальный и максимальный элемент этого массива.

Ввод	Вывод
5 3 4 5 2 1	3 4 1 2 5

Q: Удалить элемент

Дан массив из N элементов и номер элемента в массиве k. Удалите из массива элемент с индексом k, сдвинув влево все элементы, стоящие правее элемента с индексом k.

Программа получает на вход число N, затем N элементов массива, затем число k.

Программа должна вывести N-1 число – элементы массива после удаления k–го элемента.

Программа должна осуществлять сдвиг непосредственно в массиве, а не делать это при выводе элементов. Также нельзя использовать дополнительный массив.

Ввод	Вывод
7 7 6 5 4 3 2 1 2	7 6 4 3 2 1

R: Вставить элемент

Дан массив из N чисел, число k и значение C. Необходимо вставить в массив на позицию с индексом k элемент, равный C, сдвинув все элементы имевшие индекс не менее k вправо.

Посколько при этом количество элементов в массиве увеличивается, необходимо сразу же создавать массив размером N+1.

Вставку необходимо осуществлять уже в считанном массиве, не оставляя “свободного” места при считывании, не делая этого при выводе и не создавая дополнительного массива.

Ввод	Вывод
7 7 6 5 4 3 2 1 2 0	7 6 0 5 4 3 2 1

S: Количество совпадающих пар

Дан массив. Посчитайте, сколько в нем пар элементов, равных друг другу. Считается, что любые два элемента, равные друг другу образуют одну пару, которую необходимо посчитать.

Ввод	Вывод
5 1 2 3 2 3	2
5 1 1 1 1 1	10

T: Количество различных элементов - 2

Дан массив. Посчитайте, сколько в нем различных элементов, не изменяя самого массива.

Указание. Будем считать те элементы, которые встретились нам впервые. Чтобы проверить, встретился ли нам элемент A[i] впервые, необходимо проверить, встречается ли значение A[i] среди элементов с индексами, меньшими i. А это — линейный поиск, он пишется при помощи цикла while.

Ввод	Вывод
5 3 2 1 2 3	3

U: Уникальные элементы

Дан массив. Выведите те его элементы, которые встречаются в массиве только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в массиве.

Указание. Элемент является уникальным, если он больше нигде не встречается в массиве. Это тоже — линейный поиск.

Ввод	Вывод
6 1 2 2 3 3 3	1

V: Самое частое число

Дан массив. Не изменяя массива и не заводя дополнительного массива определите, какое число в этом массиве встречается чаще всего.

Если таких чисел несколько, выведите любое из них.

Ввод	Вывод
6 1 2 3 2 3 3	3

W: Сжатие массива

Массив заполнен целыми числами. Требуется “сжать” его, переместив все ненулевые элементы в левую часть массива, не меняя их порядок, а все нули - в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный массив использовать нельзя, задачу нужно выполнить за один проход по массиву. Распечатайте полученный массив.

Ввод	Вывод
8 4 0 5 0 3 0 0 5	4 5 3 5 0 0 0 0

X: Кегельбан

\(N\) кеглей выставили в один ряд, занумеровав их слева направо числами от \(1\) до \(N\). Затем по этому ряду бросили \(K\) шаров, при этом \(i\)-й шар сбил все кегли с номерами от \(l_i\) до \(r_i\) включительно. Определите, какие кегли остались стоять на месте.

Программа получает на вход количество кеглей \(N\) и количество бросков \(K\). Далее идет \(K\) пар чисел \(l_i\), \(r_i\), при этом \(1\le l_i\le r_i\le N\).

Программа должна вывести последовательность из \(N\) символов, где \(j\)-й символ есть “I”, если \(j\)-я кегля осталась стоять, или “.”, если \(j\)-я кегля была сбита.

Ввод	Вывод
10 3 8 10 2 5 3 6	I.....I...

Y: Ферзи

Известно, что на доске 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Вам дана расстановка 8 ферзей на доске, определите, есть ли среди них пара бьющих друг друга.

Программа получает на вход восемь пар чисел, каждое число от 1 до 8 - координаты 8 ферзей. Если ферзи не бьют друг друга, выведите слово NO, иначе выведите YES.

Ввод	Вывод
1 7 2 4 3 2 4 8 5 6 6 1 7 3 8 5	NO
1 8 2 7 3 6 4 5 5 4 6 3 7 2 8 1	YES

Z: Большой сдвиг

Дан массив из \(N\) (\(1 \le N \le 100000\)) целых чисел и число \(K\) (\(|K| < 100000 \)). Циклически сдвиньте массив на \(|K|\) элементов вправо, если \(K\) – положительное и влево, если отрицательное число.

Программа получает на вход массив из \(N\) элементов, затем число \(K\).

Решение должно иметь сложность \(O(N)\), то есть не должно зависеть от \(K\). Дополнительным массивом пользоваться нельзя.

Ввод	Вывод
5 5 3 7 4 6 3	7 4 6 5 3