Массивы и векторы

Упражнения

Во всех задачах этого листка (кроме 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: Ближайшее число

Дан массив целых чисел и некоторое число. Найдите в данном массиве элемент, ближайший к заданному.

В первой строке заданы элементы массива (целые числа, не превосходящие по модулю 1000).

Во второй строке дано одно целое число \(x\), не превосходящее по модулю 1000.

Выведите значение элемента массива, ближайшее к \(x\). Если таких чисел несколько, выведите последнее из них.

5
3 8 4 7 9
5

4

5
1 2 4 5 6
3

4

3
1 2 3
2

2

K: Шеренга

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

Программа получает на вход число 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

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

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

6
1 2 2 3 3 3

3

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

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

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: Удалить элемент

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

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

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

Для хранения массива необходимо использовать вектор, его размер необходимо уменьшить на 1 после удаления элемента.

7
7 6 5 4 3 2 1
2

7 6 4 3 2 1

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

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

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

7
7 6 5 4 3 2 1
2 0

7 6 0 5 4 3 2 1

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

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

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

5
1 2 3 4 5

5 1 2 3 4

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

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

5
1 2 3 2 3

2

5
1 1 1 1 1

10

S: Два ближайших

Дан массив целых чисел. Найдите в нем два ближайших элемента (то есть два элемента с минимальной абсолютной разностью).

Программа получает на вход число \(N\), в следующей строке заданы \(N\) элементов массива через пробел.

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

6
7 0 4 2 5 9

2 4

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

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

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

5
3 2 1 2 3

3

U: Медиана

В массиве — нечетное число элементов, при этом все элементы различны. Найдите медиану массива: элемент, который стоял бы ровно посередине массива, если массив упорядочить.

При решении этой задачи нельзя модифицировать данный массив (в том числе и сортировать его), использовать вспомогательные массивы.

Программа получает на вход нечетное число \(N\), в следующей строке заданы \(N\) элементов массива через пробел.

Программа должна вывести единственное число — значение медианного элемента в массиве.

7
6 1 9 2 3 4 8

4

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

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

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

6
1 2 2 3 3 3

1

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

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

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

6
1 2 3 2 3 3

3

X: Числа \(k\)-боначчи

Назовем последовательность чисел последовательностью \(k\)-боначчи, если каждый элемент этой последовательности является суммой \(k\) предыдущих членов последовательности. В частности, последовательность \(2\)-боначчи является последовательностью Фибоначчи.

Более формально, \(i-й\) элемент последовательности \(k_i\) равен 1, если \(0\le i\le k - 1\) и равен сумме \(k\) предыдущих членов последовательности \(k_{i-1} + k_{i-2} + ... + k_{i-k}\) при \(i\ge k\).

Даны два числа \(k\) и \(n\) (\(k\ge 2\), \(n\ge0\)). Вычислите \(n\)-й член последовательности \(k\)-боначчи \(k_n\).

3 6

17

100 0

1

Y: Кузнечики

\(N\) кузнечиков стоят в ряд. Для каждого кузнечика задана числовая характеристика — длина его прыжка. Если длина прыжка кузнечика равна \(l\), то он за один прыжок перепрыгивает через \(l\) других кузнечиков.

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

В первой строке входных данных содержится количество кузнечиков \(N\). Во второй строке содержатся \(N\) натуральных чисел — расстановка кузнечиков (длины их прыжков). В третьей строке входных данных задано число секунд \(t\). Опеределите и выведите на экран расстановку кузнечиков через \(t\) секунд. Все длины прыжков — натуральные числа, меньшие, чем число кузнечиков в ряду.

В этой задаче нельзя использовать методы, изменяющие количество элементов в массиве.

5
1 2 3 4 2
2

4 1 2 2 3

Z: Ферзи

Известно, что на доске 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

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

Дан массив из \(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