Теоретический материал (С++)

Массивы (часть 1)

Часто возникает необходимость хранить не одну переменную, а набор однотипных переменных. Например, список учащихся класса – это набор данных строкового типа, координаты вершин многоугольника или коэффициенты многочлена – это набор числовых данных. Для хранения наборов данных используются структуры данных. Основная структура данных – это массив.

Массив — это структура однотипных данных, занимающих непрерывную область памяти. Массив имеет размер — количество элементов в нем. Каждый элемент массива имеет свой номер (также называемый индексом), обращение к элементу массива осуществляется путем указания его индекса. В языке C++ элементы нумеруются, начиная с 0, поэтому последний элемент массива имеет номер на 1 меньше размера массива.

Массив в языке C++ задается следующим образом:

      тип_элементов идентификатор[размер];

где тип_элементов — произвольный тип данных языка C++, который будут иметь элементы массива, например, int, double и т.д.; идентификатор — имя массива, размер — число элементов в нем.

К элементу массива можно обращаться, как идентификатор[индекс]. Например, если было сделано объявление

     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;          // Счетчик в циклах
     
         cout<<"Введите количество чисел: ";
         cin>>n;         // Считываем размер массива
     
         int arr[n];     // Объявление массива (так делать нельзя), лучше вместо такого объявления массива использовать std::vector<int> arr(n);

     
                         // Считываем массив
         cout<<"Введите "<<n<<" целых чисел: ";
         for(i=0;i<n;++i)
             cin>>arr[i];
     
                         // Прибавляем по 1 к каждому элементу
         for(i=0;i<n;++i)
          arr[i]+=1;
     
                         // Выводим массив на экран
         for(i=0;i<n;++i)
             cout<<arr[i]<<" ";
                         // Переведем курсор на новую строку
         cout<<endl;
         return 0;
     }

В этом примере при помощи // обозначается начало комментария, весь текст после начала комментария и до конца строки компилятором игнорируется. Второй способ объявления комментария: в начале комментария поставить знаки /*, а в конце – */. Это позволяет делать комментарии, занимающие несколько строк. В языке C допустимы только такие комментарии.

Упражнения

В упражнениях подразумевается, что массив вводится, как в приведенном примере (сначала – количество элементов в массиве, потом – все элементы массива по одному). Все массивы – числовые типа int[].

1. (A) Выведите на экран все элементы массива с четными индексами (то есть A[0], A[2], A[4], ...).
2. (B) Выведите на экран все четные элементы массива (то есть те элементы, которые являются четными числами).
3. (C) Найдите количество положительных элементов в массиве. Программа должна считать массив и вывести единственное число – количество положительных элементов в массиве.
4. (D) Дан массив. Найдите количество элементов массива, которые больше предыдущего элемента в этом массиве.
5. (E) Массив содержит только ненулевые числа. Определите, есть ли в данном массиве два соседних элемента с одинаковыми знаками. Программа должна вывести YES, если есть два числа с одинаковыми знаками и NO иначе.
6. (F) Дан массив. Определите, сколько в этом массиве элементов, которые строго больше обоих своих соседей.
7. (G) Дан массив. Переставьте элементы массива в обратном порядке без использования дополнительного массива. Программа должна считать массив, поменять порядок его элементов, вывести результат на экран (просто вывести элементы массива в обратном порядке – недостаточно!).
8. (H) Переставьте соседние элементы массива (0-й элемент поменять с 1-м, 2-й с 3-м и т.д. Если элементов нечетное число, то последний элемент остается на своем месте)
9. (I) Циклически сдвиньте элементы массива вправо (0-й элемент становится 1-м, 1-й становится 2-м, ..., последний становится 0-м, то есть массив {3, 5, 7, 9} превращается в массив {9, 3, 5, 7}).
10. (J) Найдите значение наибольшего элемента в массиве.
11. (K) Дан массив, отсортированный по возрастанию (каждый элемент массива не меньше предыдущего элемента, например, {1, 2, 2, 3, 3, 3}). Найдите количество различных чисел в этом массиве.

Массивы (часть 2)

Передача массива в качестве параметра

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

     double Min (double A[], int n)

Соответственно, внутри функции main мы объявляем массив double A[n] и вызываем функцию Min, передав в качестве параметров массив A и его размер n:

     Min (A, n);

Упражнения

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

1. (A) Напишите функцию int Search (double A[], int n, double x), которая находит в массиве double A[n] элемент, значение которого равно x. Функция возвращает индекс найденного элемента или -1, если такого элемента в массиве нет. Программа получает на вход количество элементов в массиве n, затем n целых чисел – элементы массива, затем число x и должна вывести индекс найденного элемента или число -1, если данный элемент в массиве отсутствует.
2. (B) Напишите функцию int CountMax (double A[], int n), которая подсчитывает, сколько раз в массиве встречается значение, являющееся максимальным. Функция должна выполнять однократный просмотр массива. Программа получает на вход количество элементов в массиве n, затем n целых чисел – элементы массива и должна вывести единственное целое число – сколько раз в массиве встречается значение, равное максимальному.
3. (C) Дан массив, состоящий из различных целых чисел. Определите второй по величине элемент этого массива. Напишите для этого функцию double SecondMax (double A[], int n). Функция должна выполнять однократный просмотр массива.
4. (D) Напишите функцию double SecondMax (double A[], int n), которая находит второй по величине элемент в массиве – тот элемент, который будет наибольшим, если из массива удалить наибольший элемент, то есть для массивов {1, 2, 3, 4} и {1, 2, 3, 3} вторым по величине элементом будет 3. Функция должна выполнять однократный просмотр массива.
5. (E) Напишите функцию double SecondMaxValue (double A[], int n), которая находит второе по величине значение в массиве – значение элемента, который будет наибольшим, если из массива удалить наибольший элемент и все ему равные, то есть для массива {1, 4, 3, 4} вторым по величине значением будет 3.
6. (F) Даны два отсортированных массива: int A[n] и int B[m].

   Объедините их в один отсортированный массив int C[n+m], то есть если A={1, 4, 6, 7}, B={2, 3, 5}, то C={1, 2, 3, 4, 5, 6, 7}. Оформите алгоритм в виде функции void merge (int A[], int n, int B[], int m, int C[]). Время работы алгоритма должно быть порядка n+m действий.

   Формат входных данных: число n, затем n возрастающих чисел – элементы первого массива, число m, затем m возрастающих чисел – элементы второго массива. Программа должна вывести n+m чисел, полученных объединением двух массивов в порядке возрастания.

   Пример:

             Вход
             3
             1 5 7
             4
             2 4 4 5
             
             Выход
             1 2 4 4 5 5 7