Занятие 5 и 6. Массивы в C++. Генерация псевдослучайных чисел в C++. Сортировка массивов в C++

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

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

Индекс начального элемента — 0, следующего за ним — 1 и т. д. Индекс последнего элемента в массиве — на единицу меньше, чем размер массива. В памяти все элементы массива располагаются последовательно (т.е. между соседними элементами массива не может размещаться какая-то посторонняя переменная или, например, элементы другого массива).

Создается массив по следующей схеме:

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

Где тип — это тип элементов массива, имя — это допустимый и уникальный в данной области видимости идентификатор, а размер — это положительный литерал, переменная или конcтанта целого типа.

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

int mas1[4];
int mas2[] = {3,-7,9,1200,-713};
float mas3[400];
const int n = 173;
double mas4[n];

Массив объявленный как char mas[128]; будет занимать в памяти — 128 байт (столько же заняли бы 128 разных переменных типа char, каждая из которых занимает по байту). При этом размер массива не может быть сколь угодно большим (например, если массив объявлен не как глобальный, то его максимально допустимый размер зависит от доступного стека).

Массив mas3 из примера выше займет в памяти 1600 байт. Подумайте над тем, сколько места в памяти займут остальные из объявленных в примере массивов.

В неинициализированном массиве (по аналогии с неинициализированной переменной) будут храниться заранее неизвестные значения (какой-то «мусор», ранее записанный другими программами или даже вашей программой в выделяемую для объявленного массива память).

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

Например, чтобы вывести значения первого и последнего элементов массива mas1 надо написать в программе:

cout << mas1[0];
cout << mas1[3];

А чтобы присвоить новые значения (10, 20, 30, 40) всем элементам массива, потребуется написать в программе:

mas1[0] = 10;
mas1[1] = 20;
mas1[2] = 30;
mas1[3] = 40;

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

for(int i=0; i<4; i++) {
 mas1[i] = (i+1) * 10;
}

А после этого не сложно вывести все элементы массива на экран:

for(int i=0; i<4; i++) {
 cout << mas1[i] << '  ';
}

Размер каждого создаваемого массива правильнее хранить в отдельной константе, ведь если придётся изменить программу, то размер достаточно будет отредактировать в одном месте (там, где инициализируется контанта), не придётся править параметр каждого цикла, обрабатывающего массив.

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

#include <iostream>
using namespace std;
int main() {
 cout << "Укажите размер массива: ";
 int n;
 cin >> n;
 const int dim = n;
 int arr[dim];
 for(int i=0; i<dim; i++) {
  arr[i] = i+1;
 }
 for(int i=dim-1; i>=0; i--) {
  cout << arr[i] << ' ';
 }
 return 0;
}

Задачи

  1. Создайте массив из всех чётных чисел от 2 до 20 и выведите элементы массива на экран сначала в строку, отделяя один элемент от другого пробелом, а затем в столбик (отделяя один элемент от другого началом новой строки). Перед созданием массива подумайте, какого он будет размера.
    2 4 6 … 18 20
    2
    4
    6

    20
  2. Создайте массив из 6 целых чисел, введенных пользователем с клавиатуры, выведите его на экран в строку в обратном порядке (сначала последнее введенное число, потом предпоследнее и т.д.).
  3. Создайте массив из 10-ти первых чисел Фибоначчи и выведите его на экран. Напоминаем, что первый и второй члены последовательности равны единицам, а каждый следующий — сумме двух предыдущих.

Генерация псевдослучайных чисел в C++

В стандартной библиотеке C++ (в заголовочном файле cstdlib) существует функция rand(), которая при каждом вызове возвращает псевдослучайное целое число в диапазоне от 0 до константы RAND_MAX (обычно она равна 32767, но её значение зависит от настроек среды и, соответсвенно, может изменяться, самый простой способ избавиться от сомнений — вывести значение этой константы на экран).

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

#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
 cout << "Выводим 2 случайных значения от 0 до " << RAND_MAX << endl;
 cout << rand() << ' ' << rand();
 return 0;
}

Функция rand(), на самом деле, выбирает числа из последовательности значений, вычисленных по специальному алгоритму, где базой для построения этой последовательности является некоторый числовой аргумент (обычно называемый seed — «зерно» с англ.).

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

Иметь одинаковые наборы при каждом запуске удобно, например, в процессе тестирования. Но для реальной программы нужно, чтобы последовательность псевдослучайных чисел менялась даже при двух последовательных запусках программы. Для её перемещивания существует функция srand(seed), где seed — это некоторое значение типа unsigned int. Соответсвенно, если в качестве аргумента мы в эту функцию будем передавать разные значения при каждом запуске программы, то и наборы получаемые с помощью rand() — будут разными.

Традиционно в качестве аргумента для функции srand() используют текущее значение времени в формате UNIXTIME (количество секунд, прошедших с 1 января 1970 года).

Его можно получить с помощью функции time(NULL), которая также является частью стандартной библиотеки и описана в заголовочном файле ctime.

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

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
 cout << "Выводим 2 случайных значения от 0 до " << RAND_MAX << endl;
 srand(time(NULL));
 cout << rand() << ' ' << rand();
 return 0;
}

Отметим, что перемешивать последовательность псевдослучайных чисел нет смысла чаще одного раза в процессе исполнения программы.

В реальных задачах требуется получать числа из определенных промежутков (не от 0 до RAND_MAX).

Проблема решается с использованием пары арифметических опреаций. Для того, чтобы сузить проиежток до [0;n−1] достаточно применить к значению функции rand() операцию остатка от деления на n (оператор «%»). То есть выражение rand()%n будет всегда возвращать псевдослучайное число из отрезка от 0 до n−1 (заметим, что целых чисел там ровно n штук), при это распределение получаемых значений по классам вычетов будет доастаточно равномерным (а если RAND_MAX+1 кратно n, то полностью равномерным).

Когда требуется получить промежуток начинающийся не от 0, то результат функции просто сдвигают в положительном или отрицательном направлении, соответственно, прибавляя или вычитая нужное значение. То есть выражение rand()%n+a будет всегда возвращать псевдослучайное число из отрезка [a;a+n−1] (в нём тоже ровно n целых чисел).

Итак, чтобы получить псевдослучайное число из нужного отрезка, нужно сузить значение функции rand() до длины этого отрезхка и сдвинуть на значение левого конца отрезка.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
 int a, b;
 cout << "Введите левый конец отрезка ";
 cin >> a;
 cout << "Введите правый конец отрезка ";
 cin >> b;
 srand(time(NULL));
 int rnd = rand()%(b-a+1)+a;
 cout << "Псевдослучайное число из отрезка [" << a << ';' << b <<"]: " << rnd;
 return 0;
}

Создаем и выводим на экран массив из 20 случайных целых чисел из отрезка [0;9]:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
	int n = 20;
	short mas[n];
	srand(time(NULL));
	for (int i=0; i<n; i++) {
		mas[i] = rand()%10;
		cout << mas[i] << " ";
	}
}

Задачи

  1. Создайте массив из 15 случайных целых чисел из отрезка [0;9]. Выведите массив на экран. Подсчитайте сколько в массиве чётных элементов и выведете это количество на экран на отдельной строке.
  2. Создайте массив из 8 случайных целых чисел из отрезка [1;10]. Выведите массив на экран в строку. Замените каждый элемент с нечётным индексом на ноль. Снова выведете массив на экран на отдельной строке.
  3. Пользователь должен указать с клавиатуры натуральное число большее двух, а программа должна создать массив указанного размера из случайных целых чисел из [-5;5] и вывести его на экран в строку. Если пользователь введёт неподходящее число, то программа должна требовать повторного ввода до тех пор, пока не будет указано корректное значение.
  4. Создайте 2 массива из 5 случайных целых чисел из отрезка [0;5] каждый, выведите массивы на экран в двух отдельных строках. Посчитайте среднее арифметическое элементов каждого массива и сообщите, для какого из массивов это значение оказалось больше (либо сообщите, что их средние арифметические равны).
  5. Создайте два массива из 10 целых случайных чисел из отрезка [1;9] и третий массив из 10 действительных чисел. Каждый элемент с i-ым индексом третьего массива должен равняться отношению элемента из первого массива с i-ым индексом к элементу из второго массива с i-ым индексом. Вывести все три массива на экран (каждый на отдельной строке).
  6. Создайте массив из 4 случайных целых чисел из отрезка [10;99], выведите его на экран в строку. Определить и вывести на экран сообщение о том, является ли массив строго возрастающей последовательностью.
  7. Создайте массив из 12 случайных целых чисел из отрезка [-15;15]. Определите какой элемент является в этом массиве максимальным и сообщите индекс его последнего вхождения в массив.
  8. Создать массив из 20 случайных целых чисел из отрезка [0;13] и вывести его на экран. Создать второй массив нужного размера только из чётных элементов первого массива, если они там есть, и вывести его на экран.
  9. Создайте массив из 11 случайных целых чисел из отрезка [-1;1], выведите массив на экран в строку. Определите какой элемент встречается в массиве чаще всего и выведите об этом сообщение на экран. Если два каких-то элемента встречаются одинаковое количество раз, то не выводите ничего.
  10. Программа должна создать массив размера 12 из случайных целых чисел из [-6;6] и вывести его на экран в строку. После этого программа должна определить и сообщить пользователю о том, сумма модулей какой половины массива больше: левой или правой, либо сообщить, что эти суммы модулей равны.
  11. Программа должна создать массив из 14 случайных целых чисел из отрезка [-10;10] таким образом, чтобы отрицательных и положительных элементов там было поровну и не было нулей. При этом порядок следования элементов должен быть случаен (т. е. не подходит вариант, когда в массиве постоянно выпадает сначала 7 положительных, а потом 7 отрицательных чисел или же когда элементы постоянно чередуются через один и пр.). Вывести полученный массив на экран.

Сортировка массива

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

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

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

Сортировка массива выбором

Рассмотрим пример сортировки по возрастанию. То есть на начальной позиции в массиве должен стоять минимальный элемент, на следующей — больший или равный и т. д., на последнем месте должен стоять наибольший элемент.

Суть алгоритма такова. Во всём отыскиваем минимальный элемент, меняем его местами с начальным. Затем в оставшейся части массива (т. е. среди всех элементов кроме начального) снова отыскиваем минимальный элемент, меняем его местами уже со вторым элементом в массиве. И так далее.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
	int n = 13;
	int a[n];
	
	srand(time(NULL));
	
	for (int i=0; i<n; i++) {
		a[i] = rand()%90+10;
		cout << a[i] << " ";
	}
	
	for (int i=0; i<n; i++) {
		int min=a[i], imin = i;
		for (int j=i+1; j<n; j++) {
			if(a[j]<min) {
				min = a[j];
				imin = j;
			}
			
		}
		if (imin != i) {
			int t = a[i];
			a[i] = a[imin];
			a[imin] = t;
		}		
	}

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

Сортировка методом пузырька

Суть алгоритма такова. Если пройдёмся по любому массиву установив правильный порядок в каждой паре соседних элементов, то после того прохода на последнем месте массива гарантированно будет стоять нужный элемент (самый большой для сортировки по возрастанию или самый маленький для сортировки по убыванию). Если ещё раз пройтись по массиву с такими же преобразованиями, то и на предпоследнем месте гарантированно окажется нужный элемент. И так далее.

Пример:

2 9 1 4 3 5 2 → порядок правильный, не будет перестановки

2 9 1 4 3 5 2 → 2 1 9 4 3 5 2

2 1 9 4 3 5 2 → 2 1 4 9 3 5 2

2 1 4 9 3 5 2 → 2 1 4 3 9 5 2

2 1 4 3 9 5 2 → 2 1 4 3 5 9 2

2 1 4 3 5 9 2 → 2 1 4 3 5 2 9

Код:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
	int n = 13;
	int a[n];
	
	srand(time(NULL));
	
	for (int i=0; i<n; i++) {
		a[i] = rand()%90+10;
		cout << a[i] << " ";
	}
	
	for (int i=n-1; i>=2; i--) {
		bool sorted = true;
		for (int j=0; j<i; j++) {
			if (a[j] > a[j+1]) {
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				sorted = false;
			}
		}
		if(sorted) {
			break;
		}		
	}

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