📘 Тема 1.6. Необходимый материал#

Шпаргалка по массивам и строкам.

1. Зачем нужны массивы#

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

Массив — набор элементов одного типа, которые лежат в памяти подряд и доступны по номеру.

Итерируемые объекты — структуры, элементы которых можно перебирать в цикле:

Термины:

2. Объявление и инициализация#

тип имя[размер];

int a[100];                     // 100 целых чисел, значения не заданы
int b[5] = {10, 20, 30, 40, 50};
int c[5] = {0};                 // все элементы равны 0
int d[] = {3, 1, 4};            // размер 3 вычисляется сам
bool used[26] = {false};        // 26 флажков, все false

Важно

Размер массива должен быть константой. В олимпиадных задачах массив обычно объявляют с запасом по максимальному ограничению: если N ≤ 1000, пишут int a[1000]; (или чуть больше), а реально используют первые n элементов.

Предупреждение

Локальный массив без инициализации (int a[100]; внутри main) содержит «мусор». Если массив используется как счётчики, обязательно пишите = {0}.

3. Индексация#

• Первый элемент — a[0].
• Последний элемент массива из n элементов — a[n - 1].

int arr[5] = {10, 20, 30, 40, 50};
cout << arr[0] << endl;     // 10
cout << arr[4] << endl;     // 50
arr[2] = 99;                // теперь {10, 20, 99, 40, 50}

Почему с нуля? Индекс — это смещение от начала массива. Первый элемент лежит в самом начале, его смещение равно 0.

Внимание

arr[5] для массива из пяти элементов — выход за границы. Компилятор это не проверяет: программа может выдать мусор, испортить соседние переменные или упасть.

4. Заполнение и вывод#

С клавиатуры#

int n;
cin >> n;
int a[1000];
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

По формуле#

int a[10];
for (int i = 0; i < 10; i++) {
    a[i] = i + 1;           // 1, 2, ..., 10
}

Случайными числами#

#include <cstdlib>          // rand, srand
#include <ctime>            // time

srand(time(0));             // без этого rand() каждый раз даёт одно и то же
for (int i = 0; i < 10; i++) {
    a[i] = rand() % 100 + 1;    // от 1 до 100
}

Заметка

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

Вывод#

for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
}
cout << endl;

5. Шаблоны обработки массива#

Минимум и максимум#

int mn = a[0];
int mx = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] < mn) mn = a[i];
    if (a[i] > mx) mx = a[i];
}

Важно

Начинайте с первого элемента массива, а не с нуля. Для массива {-5, -10, -3} начальное mx = 0 даст ответ 0, хотя максимум равен −3.

Среднее значение#

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}
double average = (double)sum / n;

Без (double) получится целочисленное деление: 61 / 6 = 10, а не 10.1667.

Сравнение с соседями#

// локальные максимумы: первый и последний элементы не проверяем
int cnt = 0;
for (int i = 1; i < n - 1; i++) {
    if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
        cnt++;
    }
}

Самая длинная серия одинаковых#

int best = 1, current = 1;
for (int i = 1; i < n; i++) {
    if (a[i] == a[i - 1]) current++;
    else current = 1;
    if (current > best) best = current;
}

Предупреждение

При обращении к a[i - 1] цикл начинается с i = 1, при обращении к a[i + 1] — заканчивается на i < n - 1. Иначе будет выход за границы.

6. Массив через указатель#

Имя массива — это адрес его первого элемента. Поэтому a[i] и *(a + i) — одно и то же.

int arr[5] = {10, 20, 30, 40, 50};
int* ptr = arr;             // указатель на arr[0]

cout << *ptr << endl;       // 10
cout << *(ptr + 3) << endl; // 40

Размер массива, объявленного в той же функции, можно узнать через sizeof:

int arr[] = {10, 5, 8, 20, 3, 15};
int size = sizeof(arr) / sizeof(arr[0]);    // 6

7. Символы и ASCII#

Каждому символу соответствует числовой код по таблице ASCII.

Цифры и буквы идут подряд, поэтому с символами можно работать как с числами:

char ch = 'A';
cout << (int)ch << endl;        // 65
cout << (char)97 << endl;       // a

int d = '7' - '0';              // 7 — символ-цифра в число
char c = '0' + 5;               // '5' — число в символ-цифру
int idx = 'c' - 'a';            // 2 — номер буквы в алфавите
char letter = 'a' + 3;          // 'd'

Подсчёт букв массивом#

int cnt[26] = {0};
for (int i = 0; i < s.size(); i++) {
    cnt[s[i] - 'a']++;          // для строчных латинских букв
}

Совет

Приём c - 'a' превращает букву в индекс от 0 до 25. Так массив cnt[26] становится «таблицей частот» букв, а bool used[26] — набором отметок «буква уже встречалась».

8. Строки string#

string — строка из символов. Нужен #include <string>.

string s;
cin >> s;                       // одно слово (до пробела)
getline(cin, s);                // вся строка, вместе с пробелами

Перебор символов#

for (int i = 0; i < s.size(); i++) {
    cout << s[i] << " ";
}

Поиск подстроки#

if (s.find("ab") != string::npos) {
    cout << "found" << endl;
}

Важно

Если подстрока не найдена, find возвращает специальное значение string::npos. Сравнивайте именно с ним, а не с -1.

Предупреждение

• substr(start, len) — второй аргумент это длина, а не конечная позиция.
• cin >> s читает только до пробела. Для строки с пробелами нужен getline(cin, s).
• Если перед getline был cin >> n, в потоке остался перевод строки. Пропустите его: cin.ignore();.
• s.size() возвращает беззнаковое число. Для пустой строки s.size() - 1 — это не −1, а огромное число. Пишите i + 1 < s.size() или приводите к int.

9. Строки char[]#

Строка в стиле языка C — массив символов, который заканчивается нулевым символом '\0'. Функции для неё лежат в <cstring>.

char s[100] = "Hello";      // H e l l o \0

Заметка

string удобнее и безопаснее: он сам знает свою длину и сам выделяет память. char[] нужно знать, чтобы читать чужой код, но в своих решениях используйте string.

10. Пример: палиндром#

Два индекса идут навстречу друг другу с краёв строки и сравнивают символы.

bool isPalindrome(const string& s) {
    int left = 0;
    int right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

const string& s — передача по ссылке: строка не копируется, а const запрещает её менять.

11. Пример: пары соседних символов#

Задача «Инопланетный геном»: сколько пар соседних букв первой строки встречаются во второй строке.

string s1, s2;
cin >> s1 >> s2;

int ans = 0;
for (int i = 0; i + 1 < s1.size(); i++) {
    string pair = s1.substr(i, 2);
    if (s2.find(pair) != string::npos) {
        ans++;
    }
}
cout << ans << endl;

Для s1 = "ABBACAB" и s2 = "BCABB": пары первой строки AB, BB, BA, AC, CA, AB, из них во второй встречаются AB, BB, CA, AB — ответ 4.

12. Типичные ошибки#

13. Шаблон программы#

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    int a[1000];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // обработка массива

    // вывод ответа

    return 0;
}