Рассмотрим следующую постановку задачи: задан целочисленный одномерный массив a из n элементов; найти номер последнего минимального элемента среди положительных элементов, начиная с первого элемента, большего t; если нет элементов больших t, искать с начала массива.
Самое главное при решении этой задачи – не пытаться сделать всё сразу. Вообще при разработке программ никогда не надо пытаться решить всю задачу целиком в один присест. Надо разбивать исходную задачу на подзадачи и решать их последовательно. Однако это не означает, что надо вообще забывать об общей постановке задачи – в этом случае может получиться так, что разработанное решение одной из подзадач не будет пригодно для использования в общей программе.
В данной задаче необходимо рассматривать не все элементы массива, а только начиная с первого элемента, большего заданного числа t, или с начала массива, если элемента, больше t нет. Значит, первое, что надо сделать, – определить, с какого номера будет производиться поиск. Затем можно будет искать номер последнего минимального элемента среди положительных.
На данном этапе мы выделили в задаче две абстракции. Однако вторая часть тоже распадается на две подзадачи – сначала нужно найти положительный элемент, который можно будет использовать для инициализации переменной в алгоритме поиска минимума, или убедиться, что положительных элементов в массиве нет. После этого можно будет искать сам минимальный элемент.
Таким образом, всего мы выделили в задаче три абстракции:
Теперь надо объединить эти абстракции в единый алгоритм с помощью управляющих структур.
Наличие или отсутствие элемента, большего t, не влияет на поиск минимального элемента, а только лишь на номер элемента массива, с которого будет начинаться этот поиск. А вот при отсутствии положительных элементов искать минимальный положительный элемент бессмысленно. Поэтому получается следующая блок-схема.
Таким образом, мы выделили в задаче сначала две абстракции, затем одну из них разделили ещё на две. Теперь каждая из выделенных абстракций достаточно проста, и можно раскрывать их, используя конструкции, которые непосредственно будут кодироваться на языке Паскаль.
Алгоритм поиска элемента, удовлетворяющего условию, с досрочным выходом из цикла был рассмотрен на практическом занятии № 7. При необходимости найти в массиве последний элемент, удовлетворяющий условию, массив просматривают с конца – от n-го элемента к 1-ому.
При поиске экстремального элемента среди элементов, удовлетворяющих условию, обычно нельзя обойтись без поиска первого элемента, удовлетворяющего условию. Использовать для инициализации просто первый элемент массива, как это делается при поиске экстремального элемента без всяких условий, нельзя, т.к. это может привести к ошибке. Например, в данной задаче надо найти минимальный положительный элемент, и, если первый элемент массива окажется отрицательным, он будет меньше всех положительных и так и останется в качестве результата.
Очень часто пытаются подобрать значение для инициализации, которое не повлияло бы на конечный результат. В принципе, такой подход возможен, но только в том случае, когда программист на 100% уверен, что выбранное значение подходит для данного случая! Бывают ситуации, когда точно известно, что, исходя из сути задачи, числа могут быть только положительными. Например, надо найти максимальную длину последовательности одинаковых элементов в массиве. Тогда при поиске максимума в качестве начального значения можно задать 0 или -1. Однако и в этом случае числа либо должны формироваться программой, так чтобы они действительно были только положительными, либо проверяться при вводе.
Но, всё-таки, применять подобный подход можно лишь в исключительных случаях. Использование «магических» чисел – плохой стиль программирования. Вариант с поиском первого элемента, удовлетворяющего условию, гораздо надёжнее. Представьте, что обрабатывался массив целых чисел, и при поиске минимального положительного элемента вы задали в качестве начального значения максимальное целое число (такая системная константа существует). Однако потом тип элементов массива был изменён на вещественный. А максимальное значение переменной целого типа отнюдь не является максимальным значением переменной вещественного типа. Тогда инициализирующее значение может повлиять на результат, причём обнаружится это не сразу, а в самый неподходящий момент!
К тому же, с точки зрения эффективности программы мы ничего не теряем, поскольку можно (и нужно!) запомнить номер первого элемента, удовлетворяющего условию, и после его нахождения продолжать обработку со следующего элемента. Таким образом, мы избежим повторной обработки элементов массива. В одномерном массиве это сделать очень просто. С двумерным массивом дело, конечно, обстоит несколько сложнее. Можно запомнить индексы искомого элемента, но сначала придётся обработать часть строки, в которой находится искомый элемент, а затем в отдельном цикле – остальные строки. Хотя и это не такая уж невыполнимая задача. Можно, впрочем, слегка облегчить себе задачу, не много при этом потеряв, а именно – запомнить номер строки и обрабатывать строки матрицы, начиная с запомненной, целиком. Код будет чуть проще, а повторно будет обрабатываться только часть элементов одной строки.
Пытаться совместить поиск первого элемента, большего t, и поиск первого положительного элемента тоже не стоит, т.к. нам нужен первый положительный элемент, расположенный после элемента, большего t.
После того, как будет найден элемент, больший t, и затем положительный элемент, можно искать минимальный положительный элемент. Номер первого положительного элемента, расположенного после элемента, большего t, используется при инициализации переменных в алгоритме поиска минимума, а просмотр массива начинается со следующего элемента.
Алгоритм поиска экстремального элемента будет таким же, какой был рассмотрен на практическом занятии № 6. Единственное отличие – более сложное условие. Присваивать новое значение целевой переменной нужно при выполнении двух условий: элемент удовлетворяет заданному условию (в данном примере – положителен) и элемент больше/меньше целевой переменной.
Ещё одна проблема, которую надо решить при разработке алгоритма этой задачи – это поиск номера первого или последнего экстремального элемента. В данном случае нельзя, как при поиске последнего, например, положительного элемента, просматривать массив с конца, т.к. для поиска экстремального элемента надо просмотреть все элементы массива. Эта проблема решается знаком в операции сравнения. Если использовать операцию «строго больше/меньше», то при нахождении элемента, значение которого равно значению целевой переменной, переприсвоения происходить не будет, и запомненный номер элемента меняться не будет. Таким образом, сохранится номер первого экстремального элемента. Если же использовать операцию «больше/меньше или равно», то при нахождении элемента, значение которого равно значению целевой переменной, её значение, как и номер элемента изменятся. Таким образом, будет запоминаться номер последнего экстремального элемента.
Тестирование данной программы должно проводиться так же, как и разработка, – поэтапно. Поскольку в более или менее сложной программе бывает трудно локализовать место ошибки, представляется разумным тестировать части программы отдельно. Поэтому сначала мы пишем первую часть программы – поиск номера элемента, большего t, и тестируем именно её. Затем добавляем поиск первого положительного элемента и тоже тестируем эту часть отдельно, причём сначала независимо от поиска номера элемента, большего t, а затем тестируем эти две части вместе. И, наконец, добавляем поиск минимального положительного элемента и тестируем всю программу целиком.