Программирование на ЭВМ

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

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

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

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

1. Инициализация цикла.
2. Пока есть элементы делай

    Начало

1. Сравнить эталон с очередным элементом последовательности
2. Перейти к следующему элементу.

    Конец.

    Анализируем п.1. Нужно задать номер того элемента, с которого начнется сравнение, и определить эталон. Если в качестве эталонной переменной MIN выберем x₁, то можно начать цикл с элемента номер 2. Тогда

1. I:=2; MIN:=X[1];

    Условие п.2. означает, что текущий номер  элемента I не превысил заданную длину последовательности: I≤N.

    Шаг 2.1. – условный оператор. Его особенность – в отсутствии действий после иначе, поэтому можем записать укороченную форму оператора

    2.1.  IF X[I]<MIN

          THEN MIN:=X[I];

    Шаг 2.2. – в увеличении индекса I на 1:

    2.2.  I:=I+1;

    Объединяя шаги детализации, получим алгоритм:

    Ввод (последовательность Х);

    I:=2; MIN:=X[1];

    WHILE I<=N DO

          BEGIN

           IF X[I]<MIN

           THEN MIN:=X[I];

           I:=I+1;

          END;

    Вывод (MIN);

2. Для отыскания номера минимального элемента тоже можно провести аналогию с яблоками в ящике, разделенном на ячейки. Каждая ячейка имеет номер, и нас интересует, в которой лежит самое маленькое яблоко. Понятно, что для определения номера мы все равно должны искать минимальный элемент по алгоритму А. Добавим к этому запоминание номера ячейки, из которой берется яблоко, меньшее эталона. Тогда параллельно с изменением рамки будет меняться запоминаемый номер. В конце концов он окажется равным номеру ячейки с наименьшим яблоком.

    Поэтому алгоритм в задаче B имеет такую же структуру, что и в задаче А. Процесс отыскания минимума и его номера можно совместить в одном цикле. Как только в результате сравнения пришли к выводу, что нужно изменить эталон, то есть предположили, что новое значение может быть минимальным, нужно тут же зафиксировать номер этого элемента, следуя тому же предположению. Следовательно, в алгоритме появится новая переменная NOM – номер минимального элемента. При этом на шаге инициализации цикла нужно не забыть присвоить NOM начальное значение 1 на случай, если выбранный в качестве эталона первый элемент и окажется минимальным. Поэтому алгоритм будет иметь вид:

    Ввод (последовательность Х);

    I:=2; MIN:=X[1]; NOM:=1;

    WHILE I<=N DO

          BEGIN

           IF X[I]<MIN

           THEN

         BEGIN

      MIN:=X[I];

      NOM:=I;

              END;

           I:=I+1;

          END;

    Вывод (NOM);

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

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

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

Номер элемента	1	2	3	4	5	6	7	8
Последовательность	21	4	22	11	5	23	9	12

 

    По  алгоритму В:

          MIN:=2; NOM:=1; - начальные значения.

          MIN:=1; NOM:=4; - эти значения останутся до конца.

    Таким образом, алгоритм В решает задачу отыскания  минимального (первого по порядку  следования) элемента и его номера. Если мы хотим определить последний по порядку следования элемент и его номер, то в сравнении текущего элемента с эталоном должны изменить условие, а именно: MIN>=X[I].Тогда переприсваивание будет происходить и в случае равенства. 

4. Пусть задана последовательность x₁ , x₂ , x₃ , …,x_N и переменная P, которая называется поисковой. Известно, что все элементы последовательности имеют разные значения. Требуется определить номер элемента, значение которого равно значению переменной P. Так как сравнение вещественных величин на равенство не имеет смысла, будем считать, что массив X и переменная P – целые (они могут быть и литерными).

    Одна  из особенностей задачи состоит в  том, что в последовательности может  не оказаться элемента со значением  P. Эту ситуацию нужно обязательно предусмотреть при конструировании алгоритма.

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

    D1. Неупорядоченная последовательность

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

    Основой алгоритма является, таким образом, цикл.

1. Инициализация цикла.
2. Пока есть элементы делай

          Начало 

                2.1. Сравнить очередной элемент с поисковой переменной

      Конец

1. При инициализации цикла, как обычно, задаем исходное значение 1 индексу I элемента. Результат работы алгоритма – номер К найденного элемента. Вспомним, что наш алгоритм должен однозначно реагировать на ситуацию, когда искомого значения в последовательности нет. Резонно в этом случае считать К=0. Сделать это присваивание нужно до входа в цикл, иначе придется обременять алгоритм дополнительными проверками. Итак, шаг 1:
1. I:=1; K:=0;
2. Условие 2 – сравнение текущего номера с длиной последовательности: I<=N

    2.1 На основе сравнения мы должны сделать выбор: продолжать сравнение или закончить цикл. Запишем

         если X[I]= то

         начало

      2.1.1. запомнить номер элемента

      2.1.2. закончить цикл

    конец

                иначе 

      2.1.3. перейти к следующему сравнению

    Поясним п.п. 2.1.1, 2.1.2 и 2.1.3.

    2.1.1. K:=I

    2.1.2. Так как цикл будет работать только при I ≤ N, достаточно присвоить I значение, большее N, и цикл завершится, например:

    2.1.2 I:=N+1;

    2.1.3. I:=I+1;

    В итоге получаем алгоритм на псевдокоде.

    Ввод (последовательность X);

    I:=1; 

    K:=0;

    WHILE I<=N DO

          BEGIN

                IF   X[I]=P  

        THEN

                      BEGIN

                    K:=I; I:=N+1;

                      END;

              ELSE I:=I+1;

          END;

    Вывод (К);

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

    D2. Упорядоченная последовательность

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

    Идея  алгоритма: выбираем элемент Х_с из середины последовательности и сравниваем с поисковым значением P. Если он не равен Р, то выясним, справа или слева от выбранного элемента находится искомый:

    если X_c < P, то справа,

    если X_c > P, то слева.

    Соответствующий промежуток снова делим пополам  и так далее. То есть получим не что иное, как метод дихотомии.

    Пусть А – индекс наименьшего, а В  – индекс наибольшего элемента последовательности (а затем и выделяемой ее части). Основа алгоритма – цикл, который выполняется неопределенное число раз. В этом цикле производим деление интервала индексов [A,B] пополам, получаем индекс С и сравниваем элемент с номером С с поисковой переменной Р. В зависимости от результата сравнения перевычисляем А или В. Повторяем действия до тех пор, пока А и В не совпадут. Затем делаем проверку X[A]=P и по ее исходу формируем результат.

1. Инициализация цикла
2. Пока А и В не совпадают делай

    начало

          2.1. вычислить С

          2.2. сравнить X[C] с поисковой переменной P

    конец

3. Проверить совпадение выделенного элемента с поисковым значением.
1. A:=1; B:=N – присвоение начальных значений.
2. Так как А – индекс меньшего элемента, В – большего, то их несовпадение будет означать, что А<В .

    2.1. Так как А+В может быть нечетным  числом, то для вычисления С  нужно воспользоваться либо операцией  деления нацело DIV, либо функцией выделения целой части INT.

    C:=(A+B) DIV 2

    2.2. Сравнение производим с помощью условного оператора