Массивы: Заполнение и сортировка


Знакомимся с массивами

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

          Итак, массив - это набор однородных данных (чисел, символов, слов), имеющий имя и последовательную нумерацию его элементов. Например, список учащихся - массив, учащийся 1 - такой-то, учащийся 5 - такой-то, учащийся 18 - такой-то; или алфавит - буква 1 - "А", буква 5 - "Д", буква 15 - "Н", буква 7 - "Ё". Как физически представляется массив в компьютере, я рассказывать не буду, а вот как формально - расскажу. Вот это и надо усвоить.

          Если нам нужен массив, то мы должны определить его параметры - имя, размерность и тип данных в нём - оператором DIM в бейсике (DIM - от англ. "dimension"). Например, нам нужен массив COUNT, состоящий из 20 целых чисел. пишем DIM COUNT(20) OF INTEGER. Или тот же COUNT, но состоящий из 47 строковых переменных. Пишем DIM COUNT$(47) OF STRING - после имени массива со строками, как и после имени строковой переменной, ставится символ "$". В паскале массив задаётся следующим образом - имя_массива:Array[0..количество_элементов] of тип - и пишется в разделе оглашения пременных Var.

          Перейдём к конкретному примеру. Допустим, у нас есть таблица средних температур на каждый день какого-то года. Каждая температура каждого дня записывается в переменных Day1, Day2, Day3, ... , Day365. Надо найти среднюю годовую температуру. Можно записать так: Sred:= (Day1 + Day2 + Day 3 + ... + Day365) / 365;, а можно занести все данные в массив размерностью 365, а затем, вычислив сумму всех температур, разделить её на 365. Так же легче? Ну вот. Единственный минус паскаля - размерность массива задаётся ещё до программы, её никак не изменить в течении самой программы, а в бейсике можно занести в переменную желаемую размерность массива, а затем тут же завести массив этой размерности.

          Индекс в массивах в разных языках обозначается по-разному. Так, в бейсике индекс переменной в массиве обозначается круглыми скобками "()", а в паскале - квадратными - "[]". Итак, что мы имеем по массивам:

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

!

Оператор DIM для каждого конкретного массива должен задаваться только один раз в программе до первого к нему обращения.

          Массив можно сравнить с улицей одноэтажных домов - в каждом доме, имеющем свой номер, живёт семья, имеющая свою фамилию. И что надо знать, чтобы найти какую-то семью? Конечно - её адрес! Посмотрим, как это выглядит в программе. Допустим, все фамилии - это массив FAM$, индексы - это номера домов. В 5-м доме живёт семья Ивановых - их адрес тогда будет FAM$(5)="Ивановы" или Fam[5]:='Ивановы';. Ах да, чуть не забыл! В бейсике тип массива можно не воодить - будет стандартный числовой тип. Например, DIM A(15) создаст массив A из 15 чисел.

!

На самом деле, нумерация элементов массива начинается с нуля, но нам привычнее и удобнее начинать нумерацию с единицы. Это, в общем-то не незаконно - можно начать нумерацию и с 5-го и с 10-го и хоть-с-какого элемента. В принципе, можно задать номер самого первого элемента в каждом массиве (только в бейсике) - оператором OPTION BASE n, где n будет номером первого элемента в каждом массиве.

Вверх

Заполнение одномерных массивов и вывод их на экран

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

          Разберёмся по порядку. Первая строка запрашивает размер нового массива после очистки экрана. Затем создаёт новый массив MASS размерностью в N элементов - то есть, сколько мы ввели. Затем, в цикле запрашивает у нас каждый элемент. Мы заполнили массив, и в памяти хранятся все введённые элементы с именами MASS(1), MASS(2), MASS(3), ... , MASS(N). После этого печатается пустая строка, чтобы поставить границу между набором массива и выводом его на экран. Потом в цикле каждый элемент массива выводится на экран в одну строку. В цикле ввода массива можно поставить оператор присваивания MASS(I)=INT(RND(100)) к примеру - если вам не хочется набирать все элементы - компьютер просто заполнит весь массив произвольно.

          Как я уже сказал, главное - понять. Если Вы поняли, то смело идите дальше.

Вверх

Простейшие сортировки

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

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

Первый способ - это сортировка выбором.

          Допустим, дан числовой массив размерностью N, и нам надо отсортировать его элементы по возрастанию. Так вот, суть этого способа в следующем: Находим максимальный элемент и ставим его на своё место - на последнее, после чего уменьшаем рассматриваемый массив на 1, так как один элемент уже на своём месте. Повторяем это дело ещё раз, затем ещё раз, и ещё... И так - N-1 раз.

          Рассмотрим конкретный пример. Пусть нам дан массив из пяти элементов: 8 4 9 6 7. Теперь пошли обрабатывать:

  • 8 4 7 6 9
  • 6 4 7 8 (9)
  • 6 4 7 (8) (9)
  • 4 6 (7) (8) (9)

          Второй способ сортировки - это метод обмена или "пузырька". Программа попарно сравнивает элементы массива, и, в случае, если они расположены не по возрастанию, меняет их местами. Максимум (N-1) в квадрате перестановок - в "самом плохом" случае - когда все элементы расположены по убыванию.

          Например, у нас есть массив из четырёх элементов с тем самым "самым плохим случаем": 4 3 2 1. Смотрим:

  • 3 4 2 1
  • 3 2 4 1
  • 3 2 1 4
  • 2 3 1 4
  • 2 1 3 4
  • 1 2 3 4

          Попытайтесь реализовать эти способы сортировки.

Вверх

Двумерные массивы

          До сих пор мы рассматривали одномерные массивы - в которых как бы в ряд стояли элементы одинакового типа. А что же такое двумерные массивы? Вернёмся к нашей улице с домиками. В каждом домике - по семье. Домики одноэтажные. Теперь представим, что домики не одноэтажные, а у каждого по несколько этажей. Это и будет подобием двумерного массива, наш адрес будет теперь состоять из двух индексов - номера дома и этажа. Также можно сравнить двумерные массивы с местами в театре - каждое имеет свой ряд и своё место. Двумерные массивы также часто называют таблицами и матрицами. Итак, как я уже сказал, каждый элемент двумерного массива иммет два индекса - строка и столбец. Записываются они через запятую, объявляются так же. Посмотрим, как будет выглядеть массив S размерностью 5 на 3:

DIM S(4,3) \ Var S:Array[0..5,0..3] of Integer;

S (1,1)
S (1,2)
S (1,3)
S (1,4)
S (1,5)
S (2,1)
S (2,2)
S (2,3)
S (2,4)
S (2,5)
S (3,1)
S (3,2)
S (3,3)
S (3,4)
S (3,5)

          Дальше - всё так же, как и с обычными одномерными массивами, только немного посложнее... Заполнять их тоже легко.

Вверх

Заполнение двумерных массивов и вывод их на экран

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

Рассмотрим пример заполнения двумерного массива X(3,5) целыми произвольными числами от 1 до 20, а затем вывода его на экран в виде таблицы.
          Как всегда, разбираем по строкам. Сначала - название программы Massiv, затем объявление массива целых чисел X, размерностью 3x5 и двух целых переменных-счётчиков - i и j (почему-то все привыкли создавать переменные для счётчиков именно с этими именами). Потом, уже в теле программы, инициализация генератора случайных чисел, затем в двойном цикле, после присвоения каждому элементу произвольного числа, печатается это же число на экран - после того, как напечаталась строка элементов, печатается пустая строка, после которой - новая строка элементов массива. Таким образом, печатаются три строки по пять элементов в каждой - произвольное число от 1 до 20. И, наконец, оператор ReadLn, который не даёт программе самой завершить себя (можно также писать Repeat Until KeyPressed;).

          Итак, с массивами мы вроде разобрались, давайте перейдём к подпрограммам.

Вверх


Подпрограммы


А что же это?

          Иногда в определённых местах нужно выполнять одну и ту же последовательность каких-то операторов, с разными исходными данными. Для этого мы используем подпрограммы (от англ. "subroutine").

          Подпрограммы уменьшают объём текста программы, существенно ускоряют процесс её работы, а также и облегчают работу программисту, которому не очень-то хочется набирать одну последовательность операторов несколько раз, которые могут собирать программу модульно, то есть, из законченных кусочков - подпрограмм. Это позволяет создавать большие программы группе программистов.

          Рассмотрим подпрограмму вычисления такого выражения: Z=N!/(M!*(N-M)!). Переменные N и M, а также выражение (N-M) снабжены восклицательным знаком, что означает факториал (произведение всех чисел до данного включительно, если кто не знает). В выражении нам три раза придётся обратиться к подпрограмме вычисления факториала, производя при этом одни и те же действия с разными числами. В подпрограмме описывается вычисление факториала, а затем три раза в самой программе производятся разные операции с разными значениями, получившимися в этой подпрограмме. Давайте посмотрим:

          Как всегда, разбираем построчно. Начало стандартное - очистка экрана и запрос исходных данных. Потом начинается самое интересное. Идёт обращение к подпрограмме FACT, которая вычисляет факториал. Переменная K является параметром подпрограммы FACT. В основной программе мы присваиваем переменной K значение переменной N, для которой вычисляем первый факториал. Обращение к подпрограмме осуществляется оператором GOSUB, после которого указывается имя подпрограммы, к которой нужно перейти (у нас это FACT). Подпрограмма выполняет все действия в ней и находит факториал, после чего оператор RETURN возвращает интерпритатор к основной программе.

!

Оператор RETURN передаёт управление в основную программу на оператор, следующий за обращением к подпрограмме GOSUB.

          Результатом подпрограммы стала переменная P, в которой хранится значение факториала. Запоминаем первое полученное значение (N-факториал) в переменной X1. Это необходимо сделать, т.к. подпрограмма будет выполняться ещё два раза, и каждый раз переменная P будет меняться. Затем повторяем действия для переменных M и (N-M), соответственно. Причём, в последнем случае полученное значение факториала запоминать уже не надо, т.к. больше обращений к подпрограмме не будет. Всё! Осталось только вывести значение выражения на экран и завершить программу.

!

Привыкайте выполнять самостоятельные куски программ в виде подпрограмм. Программирование с использованием подпрограмм - это хороший стиль! О хорошем стиле мы с Вами ещё поговорим.

          Скажу ещё пару слов о подпрограммах в русском QBasic'е. Я показал Вам самый простой способ написания и использования подпрограмм, Но если Вы чувствуете в себе силы, то попробуйте самостоятельно разобраться с такими мощными инструментами бейсика по написанию подпрограмм, как DECLARE SUB и CALL SUB. Не пожалеете!

          С массивами и подпрограммами, кажется, разобрались. Идём дальше!.

Перейти к решению задач
Вверх
Hosted by uCoz