Часто возникает необходимость хранить не одну переменную, а набор однотипных переменных. Например, список учащихся класса – это набор данных строкового типа, координаты вершин многоугольника или коэффициенты многочлена – это набор числовых данных. Для хранения наборов данных используются структуры данных. Основная структура данных – это массив.
Массив — это структура однотипных данных, занимающих непрерывную область памяти. Массив имеет размер — количество элементов в нем. Каждый элемент массива имеет свой номер (также называемый индексом), обращение к элементу массива осуществляется путем указания его индекса. В языке 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 допустимы только
такие комментарии.
Массивы можно передавать функции в качестве параметра. Но при этом
размер создаваемого массива может быть неопределен на момент компиляции
программы, поэтому функция не может знать размер полученного массива.
Поэтому в функции нужно передавать два параметра - указатель на начала массива
(например, для массива целых чисел это int *, и количество элементов
в массиве.
Например, функция поиска наименьшего значения в массиве int A[n]
может быть объявлена так:
int Min (int * A, int n)
{
int result;
// Вычисляем ответ
return result;
}
Соответственно, внутри функции main мы объявляем массив int A[n] и вызываем
функцию Min, передав в качестве параметров массив A и его размер n:
int main()
{
int n, i;
cin >> n;
int A[n];
for (i = 0; i < n; ++i)
{
cin >> A[i];
}
cout << Min(A, n) << endl;
return 0;
}
Выведите элементы данного массива в обратном порядке, не изменяя сам массив.
| Ввод | Вывод |
|---|---|
5 |
5 4 3 2 1 |
В массиве все элементы различны. Поменяйте местами минимальный и максимальный элемент этого массива.
| Ввод | Вывод |
|---|---|
5 |
3 4 1 2 5 |
Петя перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю. Помогите ему это сделать.
Программа получает на вход число N – количество человек в классе. Затем невозрастающая последовательность из N чисел, означающих рост каждого человека в строю. После этого вводится число X – рост Пети. Все числа во входных данных натуральные и не превышают 200.
Выведите номер, под которым Петя должен встать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то он должен встать после них.
Примечание. Это тоже линейный поиск, поэтому необходимо использовать цикл while.
| Ввод | Вывод |
|---|---|
8 |
3 |
8 |
5 |
Дан массив чисел, число \(a\) и натуральное число \(k\) . Выведите индекс \(k\)-го по счету появления в массиве числа \(a\). Если число \(a\) встречается в массиве менее \(k\) раз, выведите число -1.
Решение оформите в виде функции int KthAppearance(int * A, int n, int a, int k).
Задача должна решаться за однократный проход по массиву
| Ввод | Вывод |
|---|---|
10 |
5 |
4 |
-1 |
Дан массив. Определите, есть ли в нем два противоположных (то есть дающих в сумме 0) числа.
Если такие числа есть в массиве, выведите их индексы в порядке возрастания. Если таких чисел в массиве нет, выведите одно число 0.
| Ввод | Вывод |
|---|---|
5 |
1 3 |
Дан массив целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный массив на экран.
Вспомогательным массивом пользоваться нельзя.
| Ввод | Вывод |
|---|---|
5 |
1 2 3 4 4 |
Дан массив. Посчитайте, сколько в нем различных элементов, не изменяя самого массива.
Указание. Будем считать те элементы, которые встретились нам впервые. Чтобы проверить,
встретился ли нам элемент A[i] впервые, необходимо проверить, встречается
ли значение A[i] среди элементов с индексами, меньшими i.
А это — линейный поиск, он пишется при помощи цикла while.
| Ввод | Вывод |
|---|---|
5 |
3 |
Дан массив. Выведите те его элементы, которые встречаются в массиве только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в массиве.
Указание. Элемент является уникальным, если он больше нигде не встречается в массиве. Это тоже — линейный поиск.
| Ввод | Вывод |
|---|---|
6 |
1 |
Дан массив. Не изменяя массива и не заводя дополнительного массива определите, какое число в этом массиве встречается чаще всего.
Если таких чисел несколько, выведите любое из них.
| Ввод | Вывод |
|---|---|
6 |
3 |
Однажды неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.
В первой строке входных данных записано число \(N\) (\(1 \le N \le 1000\)) — количество личных дел. Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов) и номера класса (целое число от 1 до 11).
Нужно вывести список всех учащихся, сначала выводя номер класса, затем — фамилию учащегося. Список должен быть отсортирован по классу, а затем по фамилии.
| Ввод | Вывод |
|---|---|
3 |
9 Petrov |
После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал \(N\) машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.
В первой строке записано число сотрудников \(N\), во второй строке записаны \(N\) чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. В третьей строке записаны \(N\) чисел — тарифы за проезд одного километра в такси.
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.
| Ввод | Вывод |
|---|---|
3 |
1700 |
В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников сможет одновременно пойти покататься.
Первая строка входных данных содержит количество коньков \(N\). Во второй строке записаны \(N\) чисел — размеры коньков. В третьей строке записано количество школьнико \(M\). В четвертой строке записаны \(M\) чисел — размеры ног школьников.
Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.
| Ввод | Вывод |
|---|---|
4 |
2 |
В супермаркете проводится беспрецедентная акция: “Покупая два любых товара, третий получаешь бесплатно*”, а внизу мелким шрифтом приписано “* — из трех выбранных вами товаров оплачиваются два наиболее дорогих”.
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Программа получает на вход число \(N\) (\(1\le N\le 1000\)), а затем \(N\) чисел — стоимости выбранных Васей товаров. Все стоимости — натуральные числа, не превышающие 10000.
Выведите одно число — сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).
| Ввод | Вывод | Пояснение |
|---|---|---|
6 |
19 |
Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок. |
5 |
51 |
Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка. |
Дан массив, заполненный целыми числами, не превосходящими по модулю \(10^6\). Найдите в этом списке два числа, произведение которых максимально. Выведите эти числа.
Количество чисел в массиве не превосходит 100000. Решение должно иметь сложность \(O(n)\). Стандартной сортировкой пользоваться нельзя.
| Ввод | Вывод |
|---|---|
5 |
5 5 |
5 |
-5 -4 |
Даны два массива int A[n] и int B[m] упорядоченных по неубыванию.
Объедините их в один упорядоченный массив int C[n+m]. Решение оформите в виде
функции void merge (int * A, int n, int * B, int m, int * C). Алгоритм
должен иметь сложность \(O(n+m)\).
Программа получает на вход число \(n\), затем последовательность из \(n\) неубывающих чисел — элементы первого массива, затем число \(m\), затем последовательность из \(m\) неубывающих чисел — элементы второго массива.
Программа должна вывести \(n+m\) чисел, полученных объединением двух массивов в порядке неубывания.
| Ввод | Вывод |
|---|---|
3 |
1 2 4 4 5 5 7 |
\(N\) человек, пронумерованных числами от 1 до \(N\) стоят в кругу. Они начинают считаться, каждый \(K\)-й по счету человек выбывает из круга, после чего счет продолжается со следующего за ним человека.
Определите номер человека, который останется в кругу последним.
Программа получает на вход числа \(N\) и \(K\), не превосходящие 100 и должна вывести одно число от 1 до \(N\).
| Ввод | Вывод |
|---|---|
5 7 |
4 |
В этом примере люди выбывают в таком порядке: 2, 5, 1, 3, остался номер 4.
Дан массив из \(N\) (\(1 \le N \le 100000\)) целых чисел и число \(K\) (\(|K| < 100000 \)). Циклически сдвиньте массив на \(|K|\) элементов вправо, если \(K\) – положительное и влево, если отрицательное число.
Программа получает на вход массив из \(N\) элементов, затем число \(K\).
Решение должно иметь сложность \(O(N)\), то есть не должно зависеть от \(K\). Дополнительным массивом пользоваться нельзя.
| Ввод | Вывод |
|---|---|
5 |
7 4 6 5 3 |
В данном списке из \(N\) целых чисел (\(N\le10^6\)), не превосходящих по модулю\(10^6\) найдите три числа, произведение которых максимально.
Решение должно иметь сложность \(O(N)\).
Выведите три искомых числа в любом порядке.
Тесты к этой задаче закрытые.
| Ввод | Вывод |
|---|---|
9 |
9 10 9 |
3 |
-5 –30000 -12 |