Задача 8. Задача поиска элемента в упорядоченном массиве.

Решение

1. Выбирается средний элемент массива и сравнивается с заданным числом b.

После чего могут представиться два возможных случая.

Случай 1. Выбранный средний элемент меньше числа b, тогда нет смысла рассматривать левую часть массива (там равного элемента уже точно не будет), а остается искать равный элемент среди второй, правой половины элементов.

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

Таким образом, сразу сокращается число испытаний вдвое.

2. С той половиной массива, в которой установлено, что может быть равный элемент, проделывается та же процедура деления.

3. Процесс такого деления продолжается. Наконец наступает такой момент, что в выбранной части массива остается один элемент (т.е. номера элементов слева и справа станут равными), тогда он является искомым, либо (если он не равен заданному числу) такого элемента вообще нет в массиве.

Рассмотрим несколько частных примеров, чтобы уразуметь математику этого вопроса.

 

1. Пусть задан массив из 10 упорядоченных по неубыванию чисел:

 

23 34 45 48     56  63 67 72 78 89

 1   2  3   4   5    6   7   8   9  10

 

Надо найти элемент этого массива, равный числу 78.

 

Пусть p - номер элемента левой границы массива, q - номер элемента правой границы массива, s - номер среднего элемента.

Устанавливаем средний элемент. Им будет элемент под номером  (знак "\" - знак целочисленного деления), т. е. 56.

Сравниваем этот элемент с числом 78: 56 < 78.

Значит искомый элемент находится справа от 56.

Рассматриваем правую половину заданного массива, т.е. элементы, находящиеся справа от 56:

                                   63 67 72 78 89

                                     6   7  8        9  10

 

Тогда, p = 6, q = 10.

Выбираем и в нём средний элемент. Им будет элемент под номером

s = (p + q)\2 = (6 + 10)=8, равный 72.

Сравниваем: 72 < 78

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

 

                                                               78 89

                                                                9  10

p = 9, q = 10.

Находим среди них средний элемент. Им будет элемент под номером

s = (p + q)\2 = (9 + 10)\2 = 9.

Сравниваем: 78 < 78.

Условие не выполняется. Значит надо брать элементы массива слева от числа 78.

Тогда, p = 9, q = 9. Номера левой и правой границ стали равны, цикл заканчивается, искомым элементом будет элемент под номером 9, равный 78.

В самом деле: 78 = 78.

Еще один пример. Задан массив из 15 элементов:

7 9 11 12 15 18 20 24 34 42 45 67 78 89 98

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Надо найти элемент массива, равный числу 9.

p = 1, q = 15, s = (p + q)\2 = (1 + 15)\2 = 8.

Средним является элемент под номером 8, равный 24.

Сравниваем: 24 < 9.

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

7 9  11 12 15 18 20 24

1 2 3 4 5 6 7 8

 

p = 1, q = 8, s =(p + q)\2 = (1 + 8)\2 = 4.

Средним элементом будет элемент под номером 4, равный 12.

Сравниваем: 12 < 9.

Условие не выполняется. Снова надо рассматривать левую часть оставшихся элементов, т.е. элементы, расположенные слева от 12 (включая 12):

7 9 11 12

1 2 3 4

p = 1, q = 4, s = (p + q)\2 = (1 + 4)\2 = 2.

Средним элементом будет элемент под номером 2, равный 9.

Сравниваем: 9 < 9.

Условие не выполняется.

Рассматриваем элементы слева от 9 (включая 9):

7 9

1 2

p = 1, q = 2, s = (p + q)\2 = (1 + 2)\2 = 1.

Средним является элемент под номером 1, равный 7.

Сравниваем: 7 < 9.

Условие выполняется, значит надо рассматривать элемент справа от 7, т.е. 9.

9

2

p = 2, q = 2, p = q, цикл заканчивается, искомый элемент под номером 2, равный 9.

 

Алгоритм

 

Первоначально в качестве границ - левой и правой берутся значения 1 и n. Пусть p и q обозначают левую и правую границы, тогда p:= 1, а q:= n; далее производится деление и шаг за шагом границы сближаются. Процесс деления должен продолжаться до совпадения границ, когда p = q (т. е. цикл выполняется пока Границы сближаются следующим образом: пусть s - номер среднего элемента, значение s - это целая часть среднего арифметического границ p и q

если  тогда надо изменить прежнюю нижнюю границу на  а верхняя граница (q) остается без изменения (выбирается правая часть массива), иначе, оставить без изменения нижнюю границу (p), а верхнюю заменить на s

Теперь можно записать этот алгоритм в виде последовательности операторов:

 

p:= 1; q:= n;

while p < q do

Begin

s:= (p + q) div 2;

if a[s] < b then p:= s + 1 else q:= s

end;

 

Может случиться, что элемента массива, равного заданному числу b в массиве нет. Это обстоятельство надо учесть и добавить следующие операторы

 

if a[p] = b then writeln('Число ', b, ' входит в масс. и равно ', p, '-му элементу')

            else writeln('Такого элемента в массиве нет')

 

Program Problem 8;

uses WinCrt;

const

   n = 20;

type

   t = array [1..n] of integer;

var

   a          : t;

   p, q, s, b, i: integer;

begin

  writeln('Вводите элементы упорядоченного по неубыванию массива');

  for i:= 1 to n do

     begin

        write(' Введите ', i, '- й элемент '); readln(a[i])

     end;

  writeln;

  write(' Введите число b '); readln(b);

  p:= 1; q:= n;

  while p < q do

      begin

         s:= (p + q) div 2;

         if a[s] < b then p:= s + 1

                          else q:= s

      end;

     if a[p ]= b

    then writeln(' Число ', b, ' равно ', p, '- му элементу ')

    else writeln('Такого элемента в массиве нет')

end.

Задача 9. Поиск " среднего " элемента массива

Решение

Program Problem9; {Поиск "среднего" элемента массива}

uses WinCrt;

const

       n = 20;

type

       t = array [1..n] of integer;

var

       x: t;

       m, i: integer;

{---------------------------------------------------------------------------------------}

Procedure create(n: integer; var x: t);

     var

         i: integer;

     begin

         randomize;

         writeln('Заданный массив целых чисел');

             for i:= 1 to n do

              begin

                x[i]:= random(201)-100;

                 write(x[i], ' ')

              end;

         writeln

       end;

{----------------------------------------------------------------------------------------}

  Procedure exchange(l, r: integer);

        var

            p: integer;

        begin

            p:= x[l]; x[l]:= x[r]; x[r]:= p

        end;

{----------------------------------------------------------------------------------------}

   Procedure middle(k: integer; var x: t; var m: integer);

       var

           l, r: integer;

       begin

           l:= 1; r:= k;

             repeat

               while (x[l] <= x[r]) and (l < r) do r:= r - 1;

                   exchange(l, r);  { Процедура обмена }

               while (x[l] <= x[r]) and (l < r) do l:= l + 1;

                   exchange(l, r)

             until l = r;

          m:= l

       end;

{---------------------------------------------------------------------------------------}

 begin

   create(n, x);

   middl e (n, x, m);

   write('Измененный массив со средним элементом ', x[m]);

   writeln(' на ', m, '-ом месте');

   for i:= 1 to n do write(x[i], ' ');

   writeln

end.

 

Задача 10. Составить программу, которая создает два массива чисел с помощью функции случайных чисел, упорядочивает их с помощью рекурсивной процедуры быстрой сортировки, а затем объединяет их в один упорядоченный массив, также с использованием рекурсивной процедуры.

Решение

Program Problem 10;

uses WinCrt;

const

       n = 10; m =15;

type

       t = array [1..n] of integer;

       u = array [1..m] of integer;

       f = array [1..n+m] of integer;

var

       a: t; b: u; c: f;

       i, p, q: integer;

{----------------------------------------------------------------------------------------}

 Procedure fast(q, p: integer;   var a: t);

     var

         s, l, r: integer;

     begin

         l:= q;

         r:= p;

         s:= a[l];

           repeat

             while (a[r] >= s) and (l < r) do r:= r - 1;

                 a[l]:= a[r];

             while (a[l] <= s) and (l < r) do l:= l + 1;

                 a[r]:= a[l]

           until l = r;

         a[l]:= s;

         if q < l - 1 then fast(q, l - 1, a);

         if l + 1 < p then fast(l + 1, p, a)

     end;

{----------------------------------------------------------------------------------------}

 Procedure fast1(q, p: integer; var b: u);

    var

        s, l, r: integer;

    begin

        l:= q;

        r:= p;

        s:= b[l];

          repeat

             while (b[r] >= s) and (l < r) do r:= r - 1;

                 b[l]:= b[r];

             while (b[l] <= s) and (l < r) do l:= l + 1;

                 b[r]:= b[l]

            until l = r;

          b[l]:= s;

          if q < l - 1 then fast1(q, l - 1, b);

          if l + 1 < p then fast1(l + 1, p, b)

       end;

{----------------------------------------------------------------------------------------}

   Procedure new(n, m, q, p, k: integer; var c: f);

        label 1, 2;

        begin

          if k = n + m + 1 then goto 1;

          if p = n then begin q:= q + 1; c[k]:= b[q]; goto 2 end;

          if q = m then begin p:= p + 1; c[k]:= a[p]; goto 2 end;

          if a[p + 1] < b[q + 1]

              then begin p:= p + 1; c[k]:= a[p]; goto 2 end

              else begin q:= q + 1; c[k]:= b[q] end;

          2: new(n, m, q, p, k + 1, c);

   1: end;

{----------------------------------------------------------------------------------------}

begin

     randomize;

      for i:= 1 to n do a[i]:= random(201)-100;

      for i:= 1 to m do b[i]:= random(201)-100;

        fast(1, n, a);

        writeln('Заданный упорядоченный 1-й массив');

      for i:= 1 to n do write(a[i], ' ');

         writeln;

         fast1(1, m, b);

         writeln(' Заданный упорядоченный 2- й массив ');

      for i:= 1 to m do write(b[i], ' ');

        writeln;

        new(n, m, 0, 0, 1, c);

         writeln('Новый упорядоченный объединенный массив');

       for i:=1 to n + m do write(c[i], ' ');

    writeln

 end.

 

Задача 11. Рекурсивная процедура "быстрой" сортировки элементов массива.

 

Решение

Procedure fast(q, p: integer; var a: t);

var

    s, l, r: integer;

begin

    l:= q; r:= p;

    s:= a[l];

          repeat

        while (a[r] >= s) and (l < r) do r:= r - 1;

            a[l]:= a[r];

        while (a[l] <= s) and (l < r) do l:= l + 1;

            a[r]:= a[l]

       until l = r;

     a[l]:= s;

     if q < l - 1 then fast(q, l - 1, a);

     if l + 1 < p then fast(l + 1, p, a)

end;