Печатать книгуПечатать книгу

§ 11. Структурированный тип данных массив

Сайт: Профильное обучение
Курс: Информатика. 10 класс (Повышенный уровень)
Книга: § 11. Структурированный тип данных массив
Напечатано:: Гость
Дата: Понедельник, 29 Апрель 2024, 05:11

Оглавление

11.1. Понятие массива

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

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

Массив является структурированным (составным) типом данных. Это означает, что величина, описанная как массив, состоит из конечного числа других величин. Так, например, можно создать массивы из 10 целых или 100 вещественных чисел. Тип элементов массива называют базовым типом. Все элементы массива упорядочены по индексам (номерам элементов), определяющим местоположение элемента в массиве. В языке С++ элементы массива всегда нумеруются с нуля.

Массиву присваивается имя, посредством которого можно ссылаться на него как на единое целое. Элементы, образующие массив, упорядочены так, что каждому элементу соответствует номер (индекс), определяющий его место в общей последовательности (примеры 11.1—11.3). Индексы могут быть выражением, значение которого принадлежит любому простому  типу, кроме вещественного. Индексы должны быть неотрицательными. Доступ к каждому отдельному элементу осуществляется обращением к имени массива с указанием индекса нужного элемента, индекс элемента записывается после имени в квадратных скобках (пример 11.4).

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

Впервые тип данных массив появился в языке Фортран (создан в период с 1954 по 1957 г. в корпорации IBM). Уже первые версии языка поддерживали трехмерные массивы (в 1980 г. максимальная размерность массива была увеличена до 7). Массивы были необходимы для создания математических библиотек, в частности содержащих процедуры решения систем линейных уравнений.

Пример 11.1. В 10 А классе 25 учащихся. Известен рост каждого в сантиметрах. Для хранения значений роста можно использовать массив А, состоящий из 25 целых чисел.

Индекс каждого элемента — порядковый номер учащегося из списка в классном журнале. Поскольку элементы массива нумеруются от нуля, то запись а[5] — рост ученика, который в журнале записан под номером 6.

Пример 11.2. Каждый день в декабре измеряли температуру воздуха. Для хранения значений температуры можно использовать массив t, состоящий из 31 вещественного числа.

Индекс элемента — номер дня в декабре со сдвигом на 1. Запись t[15] — температура воздуха 16 декабря.

Пример 11.3. В 10 Б классе 27 учащихся. В классном журнале указаны фамилия и имя каждого учащегося. Для хранения списка учащихся можно использовать массив s, состоящий из 27 строк.

Индекс каждого элемента — порядковый номер ученика из списка в классном журнале. Тогда запись s[5] — фамилия и имя учащегося под № 6.

Пример 11.4. Обращение к элементу массива: а[3], t[i], s[n-1].

Язык программирования С++ поддерживает работу с массивами, которые достались ему в наследство от языка С. Однако работа с такими массивами требует глубокого понимания того, как они размещаются в памяти компьютера. В качестве альтернативы рекомендуется использовать шаблоны классов, которые описаны в стандартной библиотеке: array<> и vector<>. 

11.2. Описание массивов

Мы будем рассматривать работу с массивом, используя тип данных vector, реализованный в стандартной библиотеке. Этот тип данных, как и уже знакомый вам тип данных string, является шаблонным классом, поэтому многие команды для работы будут одинаковыми.

Для работы с типом данных vector необходимо подключить одноименную библиотеку:

#include <vector>

Для создания вектора используется следующая команда:

vector <тип элементов> имя_массива (количество элементов);

Имя массива является идентификатором и задается по тем же правилам, что и имена любых других переменных.

Тип элементов задает значение базового типа для данного массива. Базовый тип может быть любым из известных вам типов (примеры 11.5–11.7).

Размер массива — количество элементов в нем.

Все элементы вектора после описания получают значение нуля. Если необходимо другое значение, его можно указать вторым параметром (пример 11.8).

Понятие вектора широко применяется в физике и математике. Так, например, в физике вектор рассматривается как структура, имеющая одновременно величину (модуль) и направление. Многомерные векторы используются в квантовой механике. В геометрии под векторами понимают направленные отрезки. Арифметическим вектором называют упорядоченную совокупность из n чисел. Вектор может рассматриваться как последовательность (кортеж) однородных элементов. Именно в таком виде вектор понимается в программировании.

Пример 11.5. Опишем массив, рассмотренный в примере 11.1. Размер описанного массива 25 элементов.

   vector <int> a(25);    

Пример 11.6. Опишем массив, рассмотренный в примере 11.2. Размер описанного массива  — 31 элемент.

  vector <double> t(31);  

Пример 11.7. Опишем массив, рассмотренный в примере 11.3.

  vector <string> s(27);  

Пример 11.8. Опишем массив, всем элементам которого вначале присваивается значение –1:

  vector <int> a(25, -1);  

11.3. Операции над массивами

Массивы, описанные типом данных vector, можно использовать в операциях присваивания. В результате выполнения этой команды все элементы одного массива будут переписаны во второй (пример 11.9). Если в описании векторы имеют разный размер, то он будет преобразован, поскольку векторы являются динамическими структурами, которые могут изменять свой размер во время выполнения программы.

Векторы можно сравнивать. При сравнении используют операции сравнения «==» и «!=». Векторы равны, если они содержат одинаковые элементы на тех же позициях, иначе они не равны.

Другие операции для массива как для типа данных не определены.

Операции, выполняемые с элементами массива, соответствуют операциям, выполняемым над базовым типом. Если, например, описан массив из чисел типа int, то с элементами такого массива можно выполнять такие же операции, как и с целыми числами. Элементы массива называют индексированными переменными. Они могут использоваться так же, как и простые переменные (пример 11.10). 

Пример 11.9. Пусть массивы a и b описаны следующим образом:

   vector <int> a(25), b(30);  

В результате выполнения команды:

   a = b;   

размер массива a будет увеличен до 30 элементов, все элементы в массиве a будут иметь те же значения, что и в массиве b.

В результате выполнения команды:

  b = a;   

размер массива b будет уменьшен до 25 элементов, все элементы в массиве b будут иметь те же значения, что и в массиве a. Значения последних 5 элементов, которые исходно были в векторе b, будут потеряны.

Пример 11.10. Операции над индексированными переменными:

  a[3] = 25 % 7;

  sr = (t[0] + T[29]) / 2;

  b[k] = a[k] * 2;

  sum = sum + a[i];

  if (s[i] < 0) …

  n = s[i].length();

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

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

1) определение элементов массива как констант;

2)  ввод элементов массива с клавиатуры;

3) использование случайных чисел для определения значений;

4) использование функций (собственных или стандартных) для определения значений;

5) ввод элементов массива из текстового файла.

Элементам массива можно задать значения при описании (примеры 11.11, 11.12). В этом случае количество элементов не задается, а определяется автоматически.

При вводе элементов массива с клавиатуры каждый элемент должен вводится отдельно. Если количество вводимых элементов определено, то можно воспользоваться циклом for (пример 11.13).

При описании вектора его размер может быть задан переменной. Важно, чтобы значение этой переменной было определено до описания вектора. Это значение может быть задано с помощью команды присваивания или введено с клавиатуры (пример 11.14).

При вводе строк нужно помнить, что  пробел используется как разделитель. Если использовать для ввода команду cin, то элементами массива могут быть только отдельные слова строки ( пример 11.15). Если нужно, чтобы элементами массива были строки с пробелами, то для ввода необходима команда getline (пример 11.16).

Иногда бывает удобно задавать элементы массива случайным образом. Для этого используется функция rand(), которая генерирует случайное целое число из промежутка [0; 32768). Если элементы массива должны принадлежать отрезку [a; b], то можно определить значение элемента массива как a[i]= rand() % (b – a + 1) + a; (пример 11.17).

Вещественное случайное число в промежутке [0, 32.768) можно получить так: a[i]= 1. * rand() / 1000;

Выводить элементы массива можно в строку (пример 11.18) или в столбец (пример 11.19). Если элементы массива выводятся в строку, то между ними нужно выводить символ-разделитель (чаще всего используют пробел), иначе все числа будут распечатаны подряд как одно число с большим количеством цифр. Выводить элементы массива можно не только в прямом порядке, но и в обратном (пример 11.20).

Пример 11.21. Написать программу, которая сформирует массив из n четных чисел из отрезка [20, 70] случайным образом. Записать числа из массива в текстовый файл. Вывести на экран k-й элемент массива.

Этапы выполнения задания

I. Исходные данные: количество элементов n и массив a.

II Результат: искомый элемент.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Генерация массива.

2.1. Для того чтобы элементы массива были только четными, необходимо каждый полученный элемент умножать на 2. 
2.2. Поскольку элементы умножаются на два, границы исходного отрезка нужно уменьшить в два раза. 
2.3. Вывод массива по элементам.

3. Ввод значения k и вывод результата.

IV. Описание переменных:

n, k – int, a – vector <int>.

Пример 11.22. Написать программу, которая прочитает из текстового файла список фамилий учащихся, запишет их в массив и выведет из списка фамилии с номерами от k1 до k2.

Этапы выполнения задания

I. Исходные данные: массив s и количество учащихся n, номера фамилий – k1 и k2.

II. Результат: список заданных фамилий.

III. Алгоритм решения задачи.

Ввод исходных данных.
2. Вывод результата.

IV. Описание переменных:

n, k1, k2 – int, a – vector <string>.

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

Пример 11.11. Описание числового массива, элементы которого являются константами.

vector <int> simple_numb = {2, 3, 5, 7, 11};

Пример 11.12. Описание массива, элементы которого являются строковыми константами.

vector <string> c_rgb = {"red", "green", "blue"};

 Пример 11.13. Ввести элементы массива a с клавиатуры.

vector <int> a(10);

cout << "vvedi 10 chisel" << endl;

 for (int i = 0; i < 10; i++)

  cin >> a[i];

 Пример 11.14. Ввести заданное количество элементов массива a.

int n;

cout << "kol-vo chisel" << endl;

cin >> n;

vector <int> a(n);

cout << "vvedi chisla" << endl;

for (int i = 0; i < n; i++)

  cin >> a[i];

Пример 11.15. Ввод массива строк (без пробелов):

int n;

cout << "kol-vo elementov" << endl;

cin >> n;

vector <string> s(n);

cout << "vvedi slova " << endl;

for (int i = 0; i < n; i++)

  cin >> s[i];

Пример 11.16. Ввод массива строк (с пробелами): 

int n;

cout << "kol-vo elementov" << endl;

cin >> n;

cin.ignore();

vector <string> s(n);

cout << "vvedi stroki" << endl;

for (int i = 0; i < n; i++)

  getline (cin,  s[i]);

Пример 11.17. Случайным образом задать n элементов массива А. Каждый элемент — число из отрезка [-20; 20].

int n;

cout << "kol-vo elementov" << endl;

cin >> n;

vector <int> a(n);

for (int i = 0; i < n; i++)

  a[i] = rand() % 41 - 20; 

 Пример 11.18. Вывод элементов массива в строку (через пробел):

for (int i = 0; i < n; i++)

  cout << a[i] << " "; 

cout << endl;

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

Пример 11.19. Вывод элементов массива в столбец (по одному в строке):

for (int i = 0; i < n; i++)

  cout << a[i] << endl;

Пример 11.20. Вывод элементов массива в строку (в обратном порядке):

for (int i = n - 1; i >= 0; i--)

  cout << a[i] << " ";

cout << endl;

Пример 11.21.

V. Программа:

#include <iostream>

#include <fstream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  ofstream fout("output.txt");

  for (int i = 0; i < n; i++){

    a[i] = 2 * (rand() % 26 + 10);

    fout << a[i] << " ";

  }

  int k;

  cout << "k = ";

  cin >> k;

  cout << a[k];

  return 0;

}

VI.Тестирование:

Пример 11.22.

V. Программа:

#include <iostream>

#include <fstream>

#include <vector>

#include <windows.h>

 

using namespace std;

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  ifstream fin("input.txt");

  int n;

  fin >> n;

  fin.ignore();

  vector <string> s(n);

  for (int i = 0; i < n; i++)

    fin >> s[i];

  int k1, k2;

  cout << "k1 = ";

  cin >> k1;

  cout << "k2 = ";

  cin >> k2;

  for (int i = k1; i <= k2; i++)

    cout << s[i] << endl;

  return 0;

}


VI. Тестирование:

11.5. Решение задач с использованием массивов

Операции, выполняемые с элементами массива, соответствуют операциям, которые выполняются над базовым типом элементов массива (пример 11.23).

Пример 11.24. Задан одномерный массив из целых чисел. Найти сумму и произведение элементов этого массива.

Этапы выполнения задания

I. Исходные данные: массив a и количество элементов n.

II. Результат: s — сумма элементов и p — произведение элементов массива.

III. Алгоритм решения задачи.

1. Ввод исходных данных. Массив вводится поэлементно с клавиатуры. 
2. Определение начального значения для суммы (s = 0) и для произведения (p = 1).
3. В цикле добавляем очередной элемент массива к сумме и к произведению.
4. Вывод результата.

IV. Описание переменных: n, s, p — int, a – vector <int>.

Пример 11.25. Отметки по информатике за первую четверть для всех учащихся 10 Б класса записаны в текстовом файле (первое число в файле указывает количество учащихся). Успеваемость в классе будем считать хорошей, если средний балл больше 7, плохой — если средний балл ниже 4, в остальных случаях успеваемость средняя. Определить успеваемость класса по заданным отметкам.

Этапы выполнения задания

I. Исходные данные: массив a для хранения отметок и количество учащихся n.

II. Результат — одно из слов: «хорошая», «средняя», «плохая» в зависимости от значения среднего балла.

III. Алгоритм решения задачи.

1. Ввод исходных данных. Сначала вводим количество учащихся в классе, затем массив отметок.
2. Для определения успеваемости нужно вычислить средний балл (переменная sr). Средний балл определяется как сумма (переменная s) всех отметок, деленная на количество учащихся в классе. Начальное значение для суммы  – s = 0.
3. В цикле добавляем очередной элемент массива к сумме.
4. Делим полученную сумму на количество учащихся в классе.
5. Проверяем значение среднего балла и выводим результат.

IV. Описание переменных: n, s, p – int, sr – double, a – vector <int>.

Пример 11.26. Задано натуральное число n (1 < n < 5000). Определить, является ли это число простым.

Этапы выполнения задания

I. Исходные данные: n — натуральное число.

II. Результат: вывод сообщения «простое» или «составное».

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. Известно, что число n является простым, если оно не делится ни на одно простое число, не большее чем . Максимальное число по условию — 5000, begin mathsize 16px style square root of 5000 space almost equal to space 70 comma 7107 end style. Создадим массив констант s_n из простых чисел, не больших 71. 
3. В цикле будем делить число n на каждое из чисел не больших  begin mathsize 16px style square root of straight n end style, хранящихся в массиве констант. Если число n не разделилось ни на одно из них, то число n — простое, иначе — составное. 
4. Проверяем, с каким условием закончил работу цикл: число является простым, если последний просмотренный элемент массива больше  begin mathsize 16px style square root of straight n end style (число ни на что не разделилось). 
5. Вывод результата.

IV. Описание переменных: n, — int, s_n – vector <int>.

Пример 11.23. Операции над базовым типом.

  • Если базовым типом элементов массива является тип int, то для элементов допустимы следующие операции: +, –, *, /, %.
  • Если в массиве хранятся числа типа double, то допустимыми будут операции +, –, *, /.
  • Если в массиве хранятся строки, то для каждого его элемента доступны строковые функции.

Пример 11.24.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "vvedi n=";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  int s = 0;

  int p = 1;

  for (int i = 0; i < n; i++) {

    s += a[i];

    p *= a[i];

  }

  cout << "proizvedenie=" << p;

  cout << " summa=" << s << endl;

  return 0;

}

VI. Тестирование.

Пример 11.25.

V. Программа:

#include <iostream>

#include <fstream>

#include <vector>

 

using namespace std;

 

int main()

{

  ifstream fin("input.txt");

  setlocale(0, "");

  int n;

  fin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    fin >> a[i];

  int s = 0;

  for (int i = 0; i < n; i++)

    s += a[i];

  double sr = 1. * s / n;

  cout << "sr = " << sr << endl;

  if (sr > 7)

    cout << "хорошая" << endl;

  else

    if (sr < 4)

      cout << "плохая" << endl;

    else

      cout << "средняя" << endl;

  return 0;

}

VI. Тестирование.

Пример 11.26.

Условие s_n[i] <= sqrt(n) проверяется долго за счет вызова функции sqrt(n) и перехода к вычислениям с вещественным типом данных. Это условие обычно заменяют эквивалентным: s_n[i]*s_n[i] <= n.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  vector <int> s_n = {2, 3, 5, 7, 11, 
  13, 17, 19, 23, 29, 31, 37, 41, 43, 
  47, 53, 59, 61, 67, 71};

  int n;

  cout << "n = ";

  cin >> n;

  int i = 0;

  while (s_n[i] * s_n[i] <= n

         && n % s_n[i])

    i++;

  if (s_n[i] * s_n[i] > n)

    cout << "prostoe" << endl;

  else

    cout << "sostavnoe" << endl;

  return 0;

}

VI. Тестирование.

Анализ результатов. Проверить правильность вычислений можно на калькуляторе или посмотреть в таблице простых чисел [1].

[1] Технические таблицы — http://tehtab.ru/guide/guidemathematics/guidemathematicsfigurestables/simplefigures/

Вопросы к параграфу

1. Что такое массив?

2. Как описываются массивы?

3. Что такое размер массива?

4. Какие операции допустимы для массивов?

5. Какие способы задания значений элементам массива вы знаете?

6. Как можно вывести массив?

7. Какие операции допустимы для элементов массива вещественных чисел?

Упражнения

    

1. Напишите программу, которая запишет массив из n случайных чисел из отрезка [–10; 10] в текстовый файл. Выведите: первый элемент; последний элемент; элемент, стоящий на среднем месте.

2. Запишите в массив n строк, прочитав их из текстового файла. Выведите элементы массива в обратном порядке.

3. Для получения вещественных случайных чисел можно по отдельности получать целую и дробную части, а затем находить их сумму. Например, получить число из промежутка [0; 1) с тремя цифрами после запятой можно с помощью команды:

double x = 1. * rand() % 1000  / 1000;

Напишите программу, которая сгенерирует массив из 100 вещественных чисел и запишет их в текстовый файл. Найдите среднее арифметическое этих чисел.

4. Для массива, описанного в примере 11.6, задайте значения случайными вещественными числами из интервала (–20; 10) с одним знаком после запятой. Запишите полученные данные в текстовый файл. Выведите в другой текстовый файл значения температур для указанного диапазона дат. Вывод для диапазона дат от 1 декабря до 8 декабря может быть таким:

5. Для задачи из примера 11.24 выполните следующие задания:

1. Заполните таблицу.

N

n

a

S

P

1

3

-2 -3 -5

 

 

2

5

1 2 3 4 5

 

 

3

10

1 -3 -2 3 4 3 2 4 3 2

 

 

2. Добавьте в таблицу свои значения n и a.
3.Попытайтесь подобрать такие значения элементов массива, чтобы S = P, для n = 2 и n = 5.
4. Для n = 10 ввели все элементы массива, равные 9. Какой результат получили? Почему? Что нужно исправить в программе для получения правильного результата?

6. Напишите программы, которые для заданного массива вычислят: 

    1. .begin mathsize 16px style square root of open vertical bar a subscript 0 space asterisk times space a subscript 1 space asterisk times... asterisk times a subscript n space – space 1 end subscript close vertical bar end root end style
    2. a0 + 2a1 + 3a2 + ... + nan – 1.
    3. a0*a1 + a1 * a2 + a2 * a3 + ... + an  – 2 * an  – 1.
    4. a0 – a1 + a2 – a3 +... + (–1)n - 1an  – 1.
    5. a0 – 2a1 + 4a2 – 8a3 ... + (–2)nan  – 1.
    6. –a0 + a1 – 2a2 + 6a3 – 24a4 ... + (n – 1)!(–1)nan – 1.

7. В ходе хоккейного матча удалялись игроки обеих команд. Для каждого удаленного игрока известно время его отсутствия на поле. Напишите программу, которая определит, какая из команд провела больше времени на скамейке штрафников.

8. Для задачи из примера 11.26 выполните следующие задания.

1. Введите число 5557. Почему появилась ошибка?
2. Дополните массив констант простыми числами так, чтобы программа могла выдавать ответ для чисел, меньших 10000. (Для этого можно воспользоваться самой программой или таблицей простых чисел.)