Операции с массивами: обработка данных - Программирование

Конспект

Характерные элементы двумерного массива (матрицы)

Главная диагональ матрицы — это совокупность её элементов, расположенных по диагонали от верхнего левого (первого) до нижнего правого (последнего) элемента. Эти элементы имеют равные значения индексов: [1,1], [2,2], ..., [n,n], где n — размер (порядок) матрицы.

Побочная диагональ матрицы — это совокупность её элементов, расположенных по диагонали от верхнего правого до нижнего левого элемента. Таким образом, побочная диагональ является “зеркально симметричной” по отношению к главной. Её элементы имеют следующие значения индексов: [1,n], [2,n-1], ..., [n,1], где n — размер (порядок) матрицы.

Верхняя матрица — это совокупность элементов, расположенных на главной диагонали и выше нее. Эти элементы имеют значения индексов: [i,j], где i меняется от 1 до n (размер матрицы), а j— меняется во вложенном цикле от i до n. Для верхней матрицы без главной диагонали i меняется от 1 до га (размер матрицы), a j — меняется во вложенном цикле от i+1 до n.

Нижняя матрица — это совокупность элементов, расположенных на главной диагонали и ниже нее. Эти элементы имеют значения индексов: [i,j], где i меняется от 1 до гn(размер матрицы), a j— меняется во вложенном цикле от 1 до i. Для нижней матрицы без главной диагонали i меняется от 2 до n (размер матрицы), a j — меняется во вложенном цикле от i-1 до n.

Заполнение массива

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

Пример:

Другой возможный вариант — указание значений элементов массива при его объявлении. Примеры:

1) обнуление одномерного массива:

2) присваивание начальных значений элементам двумерного массива:

Вывод массива на экран

Производится в цикле (для многомерного массива — во вложенных циклах) поэлементно путём вывода каждого элемента с клавиатуры (оператором write).

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

Пример:

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

Пример:

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

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

Производится аналогично обмену значений двух обычных переменных (обычно — при помощи дополнительной “буферной” переменной).

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

В цикле (для многомерного массива — во вложенных циклах) производится перебор элементов массива (полный или частичный — для фрагмента массива).

• При поиске максимума/минимума за предполагаемый максимум/минимум берется первый элемент массива либо константа, заведомо меньшая/большая любого элемента. Далее каждый очередной элемент массива сравнивается с предполагаемым максимумом/минимумом, и если этот элемент больше/ меньше предполагаемого максимума/минимума, то значение этого элемента запоминается в качестве нового предполагаемого максимума/минимума. Дополнительно при этом в отдельной переменной (переменных) может перезапоминаться индекс (индексы) очередного предполагаемого максимума/минимума.

Поиск максимума	Поиск минимума

Пример: поиск максимума в массиве (1,3,2,4,3,7,1).

1) первоначально:

2) i = 2: Mas[2] = 3 больше, чем Max:

3) i = 3: Mas[3] = 2 меньше, чем Max:

4) i = 4: Mas[4] = 4 больше, чем Мах:

5) i = 5: Mas[5] = 3 меньше, чем Max:

6) i = 6: Mas[6] = 7 больше, чем Max:

7) i = 7: Mas[7] = 1 меньше, чем Max:

Результат:

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

Вычисление суммы	Вычисление произведения

Пример: вычисление суммы элементов массива (1,2,3,4,5).

1) первоначально:

2) i = 1:

3) i = 2:

4) i = 3:

5) i = 4:

6) i = 5:

Результат:

• При вычислении среднего значения выполняется суммирование элементов массива, а затем полученная сумма делится на количество элементов в массиве.

• При определении максимума/минимума, суммы, произведения, среднего значения элементов, удовлетворяющих заданному условию (например, только положительных) дополнительно добавляется условный оператор с соответствующим условием, и требуемое действие (проверка и переприсваивание предполагаемого максимума/минимума, сложение, умножение) выполняется только при истинности этого условия. При вычислении среднего значения также предусматривается отдельная переменная-счётчик, которая увеличивается на 1 каждый раз, когда к сумме добавляется очередной удовлетворяющий условию элемент массива, и после вычисления суммы она делится на значение этого счётчика (количество вошедших в сумму элементов).

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

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

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

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

Пример 1: среднее арифметическое положительных элементов массива (1, -2, 3, -4, 6):

1) первоначально:

2) i = 1: Mas[1] = 1 — положительное число:

3) i = 2: Mas[2] = -2 — отрицательное число:

4) i = 3: Mas[3] = 3 — положительное число:

5) i = 4: Mas[4] = -4 — отрицательное число:

6) i = 5: Mas[5] = 6 — положительное число:

Результат:

Пример 2: минимум среди чётных положительных элементов массива (5, -4, -3, 6, 1, 4, 2) (известно, что значения элементов не превышают 100):

1) первоначально:

2) i = 1: Mas[1] = 5 — нечётное:

3) i = 2: Mas[2] = -4 — чётное, но отрицательное:

4) i = 3: Mas[3] = -3 — нечётное и отрицательное:

5) i = 4: Mas[4] = 6 — чётное, положительное, меньше чем Min:

6) i = 5: Mas[5] = 1 — нечётное:

7) i = 6: Mas[6] = 4 — чётное, положительное, меньше чем Min:

8) i = 7: Mas[7] = 2 — чётное, положительное, меньше чем Min:

Результат:

Пример 3: максимум среди нечётных положительных элементов массива (5, -4, -3, 7, 1, 3, 9), причём диапазон возможных значений элементов массива неизвестен:

1) первоначально:

2) i = 1: Mas[1] = 5 — нечётное, положительное, больше чем Мах:

3) i = 2: Mas[2] = -4 — чётное:

4) i = 3: Mas[3] = -3 — нечётное, но отрицательное:

5) i = 4: Mas[4] = 7 — нечётное, положительное, больше чем Мах:

6) i = 5: Mas[5] = 1 — нечётное, положительное, но меньше чем Мах:

7) i = 6: Mas[6] = 3 — нечётное, положительное, но меньше чем Мах:

8) i = 7: Mas[7] = 9 — чётное, положительное, больше чем Мах:

Результат:

Пример 4: минимум среди положительных элементов массива (5, -6, -3, 9, 1, 3, 6), кратных трем, причём диапазон возможных значений элементов массива неизвестен:

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

1) первоначально:

2) i = 1: Afas[1] = 5 — положительное, но не кратное 3:

3) i = 2: Mas[2] = 6 — отрицательное:

4) i = 3: Mas[3] = 3 — отрицательное:

5) i = 4: Mas[4] = 9 — положительное, кратное 3; Min равно “значению-заглушке” — нулю:

6) i = 5: Mas[5] = 1 — положительное, но не кратное 3:

7) i = 6: Mas[6] = 3 — положительное, кратное 3, меньше чем Min:

8) i = 7: Mas[7] = 6 — положительное, кратное 3, но больше чем Min:

Результат:

Разбор типовых задач

Задача 1. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100 — баллы учащихся выпускного класса за итоговый тест по информатике. Для получения положительной оценки за тест требовалось набрать не менее 20 баллов. Опишите на русском языке или на одном из языков программирования алгоритм, который позволяет найти и вывести минимальный балл среди учащихся, получивших за тест положительную оценку. Известно, что в классе хотя бы один учащийся получил за тест положительную оценку.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

Паскаль	Бейсик
Си	Естественный язык

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

Решение

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

Соответственно этому, в типовой алгоритм поиска минимума следует внести следующие изменения:

• поскольку в качестве предполагаемого минимума первоначально нельзя использовать первый элемент (он может оказаться не удовлетворяющим условию “20”), нужно в качестве первого значения предполагаемого минимума брать число, заведомо превышающее любое значение в массиве (в данном случае это может быть число 101);

• в оператор if, проверяющий, не является ли текущий элемент просматриваемого массива меньшим, чем предполагаемый минимум, надо добавить условие “текущий элемент больше или равен 20”.

Полный текст программы:

Пример для массива (80, 18, 43, 5, 50, 28, 30).

1) первоначально:

2) i = 1: Mas[1] = 80 — больше 20 и меньше, чем min:

3) i = 2: Mas[2] = 18 — меньше 20

4) i = 3: Mas[3] = 43 — больше 20 и меньше, чем min:

5) i = 4: Mas[4] = 5 — меньше 20

6) i = 5: Mas[5] = 50 — больше 20, но больше, чем min:

7) i = 6: Mas[6] = 28 — больше 20 и меньше, чем min:

8) i = 7: Mas[7] = 30 — больше 20, но больше, чем min:

Результат:

Задача 2. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от 0 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, который позволяет подсчитать и вывести среднее арифметическое элементов массива, имеющих нечетное значение. Гарантируется, что в исходном массиве хотя бы один элемент имеет нечетное значение.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

Паскаль	Бейсик
Си	Естественный язык

В качестве ответа вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Borland Pascal 7.0) или в виде блок-схемы. В этом случае вы должны использовать переменные, аналогичные переменным, используемым в алгоритме, записанном на естественном языке, с учетом синтаксиса и особенностей используемого вами языка программирования.

Решение

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

Полный текст программы:

Пример для массива (4, 65, 2, 3, 1).

1) первоначально:

2) i = 1: Mas[1] = 4 — чётное:

3) i = 2: Mas[2] = 65 — нечётное

4) i = 3: Mas[3] = 2 — чётное:

5) i = 4: Mas[4] = 3 — нечётное:

6) i = 5: Mas[5] = 1 — нечётное:

Результат:

Задача 3. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 1000. Опишите на одном из языков программирования алгоритм, позволяющий найти и вывести порядковый номер минимального значения среди нечетных положительных элементов массива.

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

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.

Паскаль	Алгоритмический язык
Бейсик	Си
Естественный язык

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

Решение

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

Способ 1

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

Пример для массива (333, 80, -43, 3, 44, 3, 68).

1) первоначально:

2) i = 1: Mas[1] = 333 — положительное, нечётное, меньше чем min:

3) i = 2: Mas[2] = 80 — положительное, но чётное:

4) i = 3: Mas[3] = -43 — отрицательное

5) i = 4: Mas[4] = 3 — положительное, нечётное, меньше чем min:

6) i = 5: Mas[5] = 44 — положительное, но чётное:

7) i = 6: Mas[6] = 3 — положительное, нечётное, равное min:

8) i = 7: Mas[7] = 68 — положительное, но чётное:

Результат:

Способ 2

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

Пример для массива (333, 80, -43, 3, 44, 3, 68).

1) первоначально:

2) i = 7: Mas[7] = 68 — положительное, но чётное:

3) i = 6: Mas[2] = 3 — положительное, нечётное, меньше чем min:

4) i = 5: Mas[5] = 44 — положительное, но чётное:

5) i = 4: Mas[4] = 3 — положительное, нечётное, равное min (но не меньшее!):

6) i = 3: Mas[3] = -43 — отрицательное

7) i = 2: Mas[2] = 80 — положительное, но чётное:

8) i = 1: Mas[1] = 333 — положительное, нечётное, но большее чем min:

Результат:

Задача 4. Дан массив, содержащий неотрицательные целые числа. Требуется определить и вывести на экран:

— максимальный чётный элемент, если количество чётных элементов не меньше, чем количество нечётных;

— максимальный нечётный элемент, если количество нечётных элементов больше, чем чётных.

Например, для массива (1, 2, 3, 4, 5) в качестве ответа нужно вывести число 5, так как нечётных чисел больше, чем чётных.

Напишите на изучаемом вами языке программирования программу для решения этой задачи. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но можно не использовать часть описанных переменных. В качестве ответа нужно записать фрагмент программы, который должен быть на месте многоточия.

Бейсик	Python
Алгоритмический язык	Паскаль
Си

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

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

Решение (способ 1)

Решение (способ 2)