Авторы:

Забавникова Евгения Александровна, учитель информатики МАОУ "Лицей №29" г.Тамбова

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

Массивы бывают:

• статические (размер известен при компиляции программы)
• динамические (размер определяется при выполнении программы).

Динамические массивы изучаются только в классах с информационно-технологическим профилем.

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

Под одномерным массивом подразумевают массив, для индексации элементов которого используют один индекс. Чтобы работать с массивом, необходимо знать, как реализовать в языке программирования следующие пункты:

1. Объявление массива.
2. Формирование массива и вывод массива на экран.
3. Поэлементная работа с массивом.

Рассмотрим их более подробно.

 1. Объявление массива

Объявление массива в С++ производится следующим образом: указывается тип данных, к которым принадлежат элементы массива; имя массива;  размерность массива.

Например:

int A[10];

char V[8];

bool mas[5];

В первом примере мы объявили массив из 10 целочисленных элементов с именем А, во втором – массив для 8 элементов символьного типа с именем V, в третьем – массив с именем mas из 5 логических элементов (компилятор языка программирования C++, различает строчные и прописные буквы).

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

Объявить массив можно через константу:

const int N=10;

int A[N];

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

Обращение к элементу массива выполняется через имя массива с индексом элемента в квадратных скобках. При этом следует помнить, что индексация элементов в С++ начинается с нуля. Таким образом, первым элементом означенного выше массива является А[0] , а последним, десятым – элемент A[9]. Эта особенность языка С++ очень важна с учетом того, что при компиляции и выполнении программ проверка на предмет выхода за пределы массива не выполняется. Язык С++ – это язык профессионалов и требует профессионального отношения, поэтому какие ошибки ложатся на плечи программистов. Выход за пределы массива опасная ошибка для вашей операционной системы.

Важной особенностью языка С++ является то, что ячейки памяти, в которые заносятся значения элементов массива, размещены рядом, т.е. являются смежными.

Еще одна особенностью С++ заключается в том, что имя массива (без индексов) является указателем на первый элемент массива. В рассмотренном выше примере имя массива А является указателем (адресом) на первый элемент массива A[0]. Адрес этого элемента можно получить, как и для обычной переменной, с помощью команды &A[0]. Однако профессионалы предпочитают использовать более простой синтаксис, основанный на имени массива. Зная, что элементы располагаются в смежных ячейках, и зная адрес первого элемента и количество элементов в массиве, получаем доступ ко всему массиву. Тема «Указатели в С++» является сложной и ее следует разбирать в классах, информационно-технологической направленности и до изучения одномерных и двумерных массивов. Это позволит на другом уровне производить обработку элементов массива.

 2. Формирование массива

Чтобы заполнить массив элементов, необходимо обращение к каждому элементу.  Это удобно выполнить, используя циклические конструкции while или for. Индексная переменная i пробегает значения от начального до конечного в цикле, позволяя обрабатывать все элементы массива.

Циклические конструкции:

i = 0;

while ( i < N )

  {

  // обработать A[i]

  i ++;

  }

for( i = 0; i < N; i++ )

  {

  // обработать A[i]

  }

Можно предложить три способа формирования массива:

• Заполнение элементов массива алгебраическим способом.

Рассмотрим фрагмент программы формирования массива:

main()

{

  const int N = 10;

  int A[N];

  int i;

  for ( i = 0; i < N; i++ )

    A[i] = 2*i;

}

Определите, чему будут равны элементы массива.

• Ввод с клавиатуры.

Рассмотрим фрагмент программы:

for ( i = 0; i < N; i++ )

  {

  cout << "A[" << i << "]=";

  cin >> A[i];

  cout <<endl;

  }

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

• С помощью датчика случайных чисел.

Приведен код программы, в которой формируется массив из 10 целочисленных элементов с помощью датчика случайных чисел в интервале [-10, 10], а потом эти значения выводятся в строчку на экране (на вывод каждого элемента массива отводится 5 знакомест).

#include <iostream>

#include <iomanip>

#include <locale.h>

#include <cstdlib>

#include <ctime>

using namespace std;

int random(int a) {

  return rand() % a;

}

int main()

{

              const int N = 10;

              int a[N], i;

              setlocale(LC_ALL, “Rus”);

              cout << “Элементы массива:”<< endl;

              srand(time(NULL));

    for (i = 0; i < N; i++)

                  { a[i]=random(21)-10;  cout << setw(5) << a[i]; }

  return 0;

}

В этой программе используется функция, возвращающая случайное число в основную программу. Для генерации случайных чисел используется функция rand() из стандартной библиотеки <cstdlib>, поэтому ее необходимо подключать в начале программы. Для начального значения при расчетах в датчике случайных чисел используется функция srand(),  тоже из этой же библиотеки. Чтобы на всех компьютерах генерировались разные числа, за начальное число в функции srand() взято время с процессора. Для этого нам нужен  #include <ctime>. Include <iomanip>  служит для управления потоками ввода-вывода.  Функция setw(5) позволяет выводить элементы массива с  определенным интервалом, т.е. на вывод числа отводится 5 знакомест.

Команда return 0 является формальным подтверждением того, что работа программы завершена корректно.

3. Поэлементная работа с массивом

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

Обработка элементов массива

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

1. Поиск заданного элемента массива.
2. Поиск максимального и минимального элементов массива.
3. Поиск полной или частичной суммы (произведения, количества) элементов массива.
4. Работа с несколькими массивами.
5. Рекурсия элементов массива.
6. Циклический сдвиг элементов влево и вправо.
7. Удаление одного или нескольких элементов массива.
8. Вставка одного или нескольких элементов массива.
9. Сортировка элементов массива.
10. Алгоритмы быстрой сортировки.
11. Двоичный поиск.

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

Рассмотрим методику преподавания темы: «Удаление и вставка элементов массива» с подборкой задач  по этой теме.

Удаление элементов из одномерного массива

Задача 1: Удалить из массива элемент с номером k.

Алгоритм:

1. Первые (k – 1) элементы оставить без изменения.
2. Сдвинуть все элементы, начиная с (k – 1)-го на один элемент влево.
3. Последнему элементу присвоить значение 0.
4. Вывести новый массив без последнего элемента.

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

Задача 2: Удалить из массива максимальный элемент, если все элементы разные.

Примечание:

Необходимо найти номер максимального элемента и решение задачи сводится к рассмотренной выше.

Задача 3: Удалить все максимальные элементы.

Примечание:

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

Система задач по этой теме:

1. Удалить первый отрицательный элемент, если такого элемента, то вывести об этом сообщение.
2. Удалить все отрицательные элементы.
3. Удалить все элементы, большие данного числа А (А вводить с клавиатуры).
4. Удалить все четные элементы, стоящие на нечетных местах.
5. Удалить все повторяющиеся элементы, оставив только их первые вхождения, т.е. получить массив различных элементов.
6. Удалить все элементы, кратные 3 или 5.

Вставка элементов в одномерный массив

Задача 1: Вставить число 100 после элемента с номером k.

Алгоритм:

1. Первые (k – 1) элементы оставить без изменения.
2. Все элементы, начиная с k-го, необходимо сдвинуть на один вправо.
3. На место k-го элемента записываем значение x, то есть после (k – 1) элемента массива.

Важно! Необходимо выделять память при описании массива на один  больше.

Задача 2: Вставить число 100 перед пятым элементом массива.

Примечание:

Эта вставка отличается от предыдущей тем, что сдвигать вправо надо элементы не с k-го, а с  (k-1)-го элемента.

Задача 3: Вставит число 100 после всех элементов массива, кратных 3.

Примечание:

На сколько элементов может увеличиться массив? (Надо резервировать массив на 2*N элементов).

Лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. Номер последнего элемента можно будет знать (если знать, сколько элементов вставлено на данный момент), при этом просмотр будет последовательным от (N-1)-го до 0-го.

Система задач по этой теме:

1. Вставить элемент после первого отрицательного элемента.
2. Вставить элемент перед последним отрицательным элементом.
3. Вставить два элемента: первый – после максимального элемента, второй – перед максимальным элементом (удобнее всего применить именно такой порядок вставки).
4. Вставить по одному элементу перед всеми элементами, кратными заданному числу.
5. Вставить по одному элементу перед всеми отрицательными элементами.
6. Вставить число А перед всеми элементами, большими А, а число В – после всех элементов, меньших его.

В качестве контроля знаний провести следующую контрольную работу. Она рассчитана на 2 часа.

Контрольная работа по теме:

«Вставка и удаление элементов массива»

1 вариант.

Дан массив целых чисел (n=10), заполненный случайными числами в диапазоне [-5, 5].

1. Удалить из него первый элемент, равный цифре 5.
2. Удалить из него все элементы, кратные 3.
3. Вставить число k после первого элемента, кратного своему номеру (k – вводится с клавиатуры).
4. Вставить число m между всеми соседними элементами, которые образуют пару элементов с одинаковыми знаками.
5. Поменять местами первый положительный и последний отрицательный элементы.

2 вариант.

Дан массив целых чисел (n=10), заполненный случайными числами в диапазоне [-20, 20].

1. Удалить из него первый однозначный элемент (т.е. первый элемент меньший 10).
2. Удалить из него все элементы, в которых последняя цифра четная, а само число делится на нее.
3. Вставить число k перед первым элементом, в котором есть цифра 1 (k – вводится с клавиатуры).
4. Вставить число m после всех элементов кратных 3.
5. Переставить первые три и последние три элемента местами, сохраняя их следование.

3 вариант.

Дан массив целых чисел (n=10), заполненный случайными числами в диапазоне [0, 30].

1. Удалить из него первый элемент, в котором последняя цифра четная.
2. Удалить из него все элементы, которые состоят из одинаковых цифр (включая однозначные числа).
3. Вставить число k после первого элемента, равного числу А (k и А – вводятся с клавиатуры).
4. Вставить число k перед всеми элементами, в которых есть цифра 1 (k – вводится с клавиатуры).
5. Переставить первые два и последние два элемента местами, сохраняя их следование.

4 вариант.

Дан массив целых чисел (n=10), заполненный случайными числами в диапазоне [-40, 40].

1. Удалить из него первый элемент, в котором последняя цифра кратна 3.
2. Удалить из него все элементы, первая цифра которых четная.
3. Вставить число k перед первым элементом, в котором есть цифра 7 (k – вводится с клавиатуры).
4. Вставить число m после всех элементов, кратных своему номеру.
5. Поменять местами первый четный и последний нечетный элементы.