Конспект лекций по программированию для начинающих. Гладков В.П. - 168 стр.

                                      170

    Упражнения:
    1. Задан одномерный массив. Преобразуйте его так, чтобы все элементы,
меньшие или равные k, разместились в конце массива, а большие k в начале.
    2. Осуществите сжатие одномерного массива а длины n, удалив из него каждый
i-й элемент. Конец массива после сжатия заполните нулями.

                   11.6.4. Решение задач четвертого класса
    Поиск элемента в массиве является наиболее часто встречающимся
алгоритмом. Задача заключается в поиске среди элементов одномерного массива
элемента, равного заданному «аргументу поиска» a. Существует много вариантов
решения этой задачи.
    Вариант 1 (линейный поиск). Если нет дополнительной информации о
разыскиваемых данных, то остается простой последовательный просмотр массива с
увеличением шаг за шагом той его части, где искомого элемента не обнаружено.
Такой метод называется линейным поиском. Исходными данными для решения
задачи является массив чисел. В результате получаем либо номер элемента,
совпадающего с А, либо ответ: «Такого элемента нет». Решение этой задачи может
закончиться по двум причинам: 1) перебрали все элементы массива и не нашли
нужного элемента; 2) в процессе перебора обнаружился элемент, совпавший с А. В
этом случае перебор прекращается и формируется ответ.
    Первую причину окончания можно определить, проверив условие: i > n, где i -
текущий элемент массива, n - количество элементов в массиве.
    Вторая причина имеет два значения: «найдено» или «не найдено», поэтому ее
можно изображать логическим значением, где true соответствует найдено, а false -
не найдено.
    Таким образом, условие окончания поиска может быть записано в виде (i>n) or
f, что соответствует фразе русского языка: «Просмотрены все элементы или не
найдено». Просмотр элементов массива в цикле будет выполняться в случае
ложности приведенного условия. Найдем его отрицание, воспользовавшись
законом де Моргана: отрицание дизъюнкции равно конъюнкции отрицаний.
     not((i>n) or f) = not(i>n) and not f = (i<=n) and not f.
    Программа на алгоритмическом языке Паскаль.
    program POISK;
    { линейный поиск элемента в одномерном массиве }
    const nn=12; { константа задает максимальный размер массива }
    type mas1=array[1..nn] of integer; { тип массива }
    var        b : mas1; { исходный массив }
               n : integer; { размер массива }
               a : integer; { число для поиска }
               i : integer; { индекс массива }
               f : Boolean; { истина, если искомый элемент найден }
    begin
       write('Введите размер массива от 1 до ',nn);
       repeat { вводим n до тех пор, }
                       readln(n); { пока оно не попадет }