Практика программирования (Бейсик, Си, Паскаль)

       

Поиск


Алгоритмические и математические аспекты поиска достаточно сложны и их исследованию посвящены многочисленные работы. Наиболее полно эти вопросы рассматриваются в ранее упоминавшейся трилогии Д. Кнута. Мы же ограничимся самыми простыми алгоритмами и программами, позволяющими понять суть проблемы и познакомиться с некоторыми подходами к повышению эффективности поиска.

В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).

Последовательный поиск

Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.

Классический алгоритм последовательного поиска включает следующие шаги:

  • S1 Остановить начальный индекс равным 1 (j = 1).

  • S2:Проверить условие q = a[j]. Если оно выполняется, то сообщить, что искомое значение находится в массиве а на j-ом месте и прервать работу. В противном случае продолжить работу.

  • S3:Увеличить индекс j на 1.

  • S4:Проверить условие j < n + 1. Если оно выполняется, то вернуться к шагу S2. В противном случае сообщить, что значение q в массиве а не содержится.

    Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это — очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15—20%.




    Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится q. Теперь цикл повторяется до тех пор, пока не будет встречен элемент а [ j ], равный q, и необходимость в проверке j < n + 1 отпадает. Конечно, перед возвратом из процедуры надо удостовериться в том, что найденный индекс j не равен n + l. Но такая проверка выполняется за пределами цикла.



    Для программистов, имеющих дело с языком ассемблера, известен и более простой прием, не требующий расширения исходного массива. Очевидно, цикл поиска можно организовать как в прямом (j меняется от 1 до n), так и в обратном (j меняется от n до i) направлении. Обратный цикл на ассемблере реализуется с помощью команды LOOP, организующей возврат в начало цикла с одновременным вычитанием 1 из счетчика сх. Цикл повторяется до тех пор, пока содержимое регистра сх не станет равным 0. Таким образом, дополнительного сравнения (j < n + 1) здесь не требуется.

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

    Функция ssearch.bas

    FUNCTION SSEARCH(Q,A(),N)

    FOR J=0 TO N-l

    IF Q=A(J) THEN SSEARCH=J: EXIT FUNCTION

    NEXT J

    SSEARCH=-1

    END FUNCTION

    Функция ssearch.c

    int ssearch(int q, int *a, int n)

    }

    register int j;

    for(j=0; j<n; j++)

    if(q==a[j]) return j;

    return -1;

    }

    Функция ssearch.pas

    function ssearch(q:integer;a:array of integer;n:integer):integer;

    var

    j:integer; begin

    for j:=0 to n-1 do

    if q=a[j] then

    begin

    ssearch:=j;

    exit;

    end;

    ssearch:=-l;

    end;

    Бинарный поиск

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



    Исключим тривиальный случай, когда искомое значение g выходит за пределы интервала [а[1],а[n]]. Обозначим через left и right индексы элементов массива, определяющие текущий диапазон поиска. В начальный момент left = 1 и right = n. Сравним значение q с величиной среднего элемента a [mid] в диапазоне поиска (mid = (left + right)/2). Если значение q строго меньше a [mid], то заменим правую границу диапазона поиска на mid - 1. Если значение q строго больше a [mid], то заменим левую границу диапазона поиска на mid + 1. Если оба строгие неравенства не выполнены, то имеет место равенство q = a [mid], и в этом случае процедура поиска завершена успешно.

    Поиск следует продолжать до тех пор, пока значение индекса left не превосходит значения индекса right. А нарушиться это условие может только в случае, когда диапазон поиска сведен к минимальному (right = left + l) и имеют место неравенства:

    a[left] < q < a[right]

    Это означает, что значение q в массиве а не содержится.

    Функция bsearch.bas

    FUNCTION BSEARCH(Q,A() ,N) LEFT=0: RIGHT=N-1

    WHILE LEFT <= RIGHT

    MIDDLE=(LEFT+RIGHT)\2

    IF Q < A(MIDDLE) THEN RIGHT=MIDDLE-1: GOTO M

    IF Q > A(MIDDLE) THEN LEFT=MIDDLE+1: GOTO M

    BSERACH=MIDDLE : EXIT FUNCTION M:WEND

    BSEARCH=-1 END FUNCTION

    Функция bsearch.c

    int bsearch(int q,int *a,int n)

    {

    register int left,right,mid;

    left=0; right=n-l;

    for(;left <= right;)

    {

    mid=(left+right)12;

    if(q < a[mid]) right=mid-l;

    else if(q > a[mid]) left=mid+l;

    else

    return mid; }

    return -1; }

    Функция bsearch.pas

    function bsearch(q:integer;a:array of integer;n:integer):integer;

    var

    left,right,mid:integer;

    begin

    left:=0; right:=n-l;

    until left <= right do

    begin

    mid:=(left+right) div 2;

    if q < a[mid] then right=mid-l

    else if q > a[mid] then left=mid+l

    else

    begin

    bsearch:=mid;

    exit;

    end;

    end;

    bsearch:=-l;

    end;

    Идея бинарного поиска может быть с успехом реализована в игре с отгадыванием задуманного целого числа из заранее установленного диапазона [O,N]. В ответ на число, предложенное угадывающим, его партнер может дать один из трех ответов:



  • это число меньше загаданного;


  • это число больше загаданного;


  • это число равно загаданному.

    Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log2N шагов.

    Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.

    Программа 4_02.bas

    'Программа угадывания задуманного числа в интервале [0,100]

    DEFINT A-Z

    CLS

    LEFT=0: RIGHT=100:

    DO

    MIDDLE=(LEFT+RIGHT)\2

    PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";

    INPUT "",A$

    IF RIGHT-LEFT <= 1 THEN

    IF A$="Y" OR A$="y" THEN

    PRINT "Вы задумали ";RIGHT: END

    ELSE

    PRINT "Вы задумали ";LEFT: END

    END IF

    END IF

    IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE

    LOOP

    END

    Программа 4_02.с

    /* Программа угадывания задуманного числа в интервале [0,100] */

    #include <stdio.h>

    #include <conio.h>

    main ()

    {

    int left=0, right=100, middle, ok;

    char ch;

    clrscr();

    for (;;)

    {

    middle={left+right)/2;

    printf("\n Задуманное Вами число больше, чем % d (Y/N) - ", middle);

    ch=getche();

    if(right-left <= 1)

    if (ch=='Y' || ch == 'y') { ok=right; break; }

    else { ok=left; break;}

    if(ch=='Y' II ch== 'y') left=middle+l;

    else right=middle; }

    printf("\пВы задумали %d",ok); getch(); }

    Программа 4_02.pas

    { Программа угадывания задуманного числа в интервале [0,100] }

    uses Crt;

    var

    ch: char;

    left, right, middle, ok: byte;

    begin

    left:=0;

    right:=100;

    clrscr;

    repeat

    middle := (left + right) div 2;

    write('Задуманное Вами число больше, чем ',middle,' (Y/N) - ');

    ch:=readkey;

    writeln(ch);

    if (right-left <= 1) then

    if (ch='Y') or (ch = 'y') then begin ok:=right;

    break;

    end else begin ok:=left;

    break;

    end; if(ch='Y') or (ch='y') then left := middle + 1

    else right := middle;

    until false;

    writeln('Вы задумали ',ok);

    readln;

    end.




    Содержание раздела