|
|
Учебник для 9 класса Информатика и ИКТ§ 4.7. Одномерные массивы целых чиселКлючевые слова:
До сих пор мы работали с простыми типами данных. При решении практических задач данные часто объединяются в различные структуры данных, например в массивы. В языках программирования массивы используются для реализации таких структур данных, как последовательности и таблицы.
Мы будем рассматривать одномерные массивы. Решение разнообразных задач, связанных с обработкой массивов, базируется на решении таких типовых задач, как:
4.7.1. Описание массиваПеред использованием в программе массив должен быть описан, т. е. должно быть указано имя массива, количество элементов массива и их тип. Это необходимо для того, чтобы выделить в памяти под массив блок ячеек нужного типа. Общий вид описания массива: var <имя_массива>: array [<мин_знач_индекса> .. <макс_знач_индекса>] of <тип__элементов>; Пример var a: array [1..10] of integer; Здесь описан массив а из десяти целочисленных значений. При выполнении этого оператора в памяти компьютера будет выделено десять ячеек целого типа. Небольшой массив с постоянными значениями может быть описан в разделе описания констант: const b: array [1..5] of integer = (1, 2, 3, 5, 7); В этом случае не просто выделяются последовательные ячейки памяти — в них сразу же заносятся соответствующие значения. 4.7.2. Заполнение массиваЗаполнять массив можно либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения. При этом может использоваться цикл с параметром. Например, для ввода с клавиатуры значений элементов описанного выше массива а используется следующий цикл с параметром: for i:=l to 10 do read (a[i1); Задавать значения элементов массива можно с помощью оператора присваивания. Например: for i:=l to 10 do a[i]:=i; В следующем фрагменте программы организовано заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99:
4.7.3. Вывод массиваВо многих случаях бывает полезно вывести значения элементов массива на экран. Так, если значения массива генерировались случайным образом, то необходимо знать, каков исходный массив. Также нужно знать, каким стал массив после обработки. Элементы массива можно вывести в строку, разделив их пробелом: for i:=1 to 10 do write (a[i], ' ); Более наглядным является следующий вариант вывода с комментариями: for i:=1 to 10 do writeln ('a[', i, ')=', a[i]); На основании рассмотренных примеров попытайтесь самостоятельно запишите программу, в которой осуществляется: заполнение случайным образом целочисленного массива а, состоящего из 10 элементов, значения которых изменяются в диапазоне от 0 до 99; вывод массива а на экран. 4.7.4. Вычисление суммы элементов массиваСуммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых:
Описанный процесс наглядно можно изобразить так:
Приведём основной фрагмент решения этой задачи:
Дополните созданную в п. 4.7.3 программу формирования массива так, чтобы вычислялась сумма элементов массива и результат суммирования выводился на экран. 4.7.5. Последовательный поиск в массивеВ программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера. Можно выделить следующие типовые задачи поиска:
Компьютер не может сравнить разом весь ряд объектов. На каждом шаге он может сравнивать только два объекта. Поэтому в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом. Рассмотрим подробно решение задач первого типа (нахождение наибольшего (наименьшего) элемента). Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
В итоге на доске будет записано самое большое значение просмотренного массива. Так как доступ к значению элемента массива осуществляется по его индексу, то при организации поиска наибольшего элемента в одномерном массиве правильнее искать его индекс. Обозначим искомый индекс imax. Тогда описанный выше алгоритм в сформированном нами массиве а на языке Паскаль можно записать так:
Самостоятельно запишите программу, в которой осуществляется формирование целочисленного массива а из 10 элементов, значения которых лежат в диапазоне от 0 до 99, и поиск наибольшего элемента этого массива. Если в массиве несколько элементов, равных максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы в ней находился последний из максимальных элементов. Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива? Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
Алгоритм поиска в сформированном нами массиве а значения, равного 50, может выглядеть так:
В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдёт последний из них. Запишите полный текст программы и выполните её на компьютере. Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующую программу:
Здесь выполнение алгоритма будет прервано в одном из двух случаев:
Запишите полный текст программы и выполните её на компьютере. Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент. Определите, количество каких элементов подсчитывается в следующем фрагменте программы.
Если требуется определить сумму значений элементов, то вводят переменную, к значению которой прибавляют значение найденного элемента массива. Определите, какому условию удовлетворяют элементы массива, значения которых суммируются в следующем фрагменте программы.
Запишите полные тексты двух последних программ и выполните их на компьютере. 4.7.6. Сортировка массиваПод сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке. Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют возрастающим. Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют убывающим. Цель сортировки — облегчить последующий поиск элементов: ис-кать нужный элемент в упорядоченном массиве легче. Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов1 реализации механизма этой операции — сортировку выбором. Сортировка выбором (например, по убыванию) осуществляется следующим образом:
Рассмотрим процесс сортировки выбором на примере массива а = {0, 1, 9, 2, 4, 3, 6, 5}.
В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из n элементов такая операция будет проводиться n—1 раз. Объясните почему. Приведём фрагмент программы, реализующий описанный алгоритм:
Здесь мы использовали один цикл внутри другого. Такая конструкция называется вложенным циклом. Запишите полный текст программы и выполните её на компьютере для рассмотренного в примере массива а. На сайте «Интерактивные демонстрации по программированию» (http://informatika.kspu.ru/flashprog/demos.php) вы сможете поработать с интерактивными наглядными пособиями для того, чтобы более полно представить процесс сортировки выбором и другими способами. Самое главноеМассив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элементов в массиве. В языках программирования массивы используются для реализации таких структур данных, как последовательности и таблицы. Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива: var <имя_массива>: array [<мин_знач_индекса> ..
Заполнять массив можно либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения. При заполнении массива и его выводе на экран используется цикл с параметром. Решение разнообразных задач, связанных с обработкой массивов, базируется на таких типовых задачах, как: суммирование элементов массива; поиск элемента с заданными свойствами; сортировка массива.
Вопросы и задания
|
|
|