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

                                     169

   Решение. Например, для массива a={16,1,5,3,8,4,7,1,3,2} и k=4 существует
много перестановок элементов массива, удовлетворяющих заданным условиям.
Примерами выходных данных могут быть:
   1) a={1,1,2,3,3,4,5,7,8,16};
   2) a={1,3,4,1,3,2,7,8,5,16};
   3) a={2,1,3,3,1,4,7,8,5,16}.
   Первый результат получен сортировкой массива. Методы сортировки будут
рассмотрены в следующей главе. Второй результат получен с помощью
вспомогательного массива, в начало которого выписывались элементы, меньшие k,
при просмотре исходного массива от первых элементов к последним, а в конец -
элементы, большие k. Это решение представлено следующим фрагментом
программы:
   i:=1; {индекс начальных элементов выходного массива}
   j:=n; {индекс последних элементов выходного массива}
   for m:=1 to n do {просматриваем все элементы исходного массива}
       if a[m]>k
       then begin b[j]:=a[m]; j:=j-1 end
       else begin b[i]:=a[m]; i:=i+1 end;
   {переписываем результат в исходный массив}
   a:=b.
   Недостатком           представленного  решения   является    нерациональное
использование оперативной памяти - использование вспомогательного массива.
Третье решение получено без помощи вспомогательного массива. Здесь
используется следующая идея. Массив начинает просматриваться с начала до
обнаружения элемента, большего k, затем просмотр массива идет с конца до
нахождения элемента, меньшего или равного k, найденные элементы меняются
местами. После обмена просмотр возобновляется с начала массива от элемента,
следующего за обмененным. Это решение приведено ниже:
    i:=1; {индекс начальных элементов исходного массива}
   j:=n; {индекс конечных элементов исходного массива}
   while i<=j do
       if a[i]>k
       then if a[j]<=k
               then begin r:=a[i];
                             a[i]:=a[j];
                             a[j]:=r;
                             i:=i+1;
                             j:=j-1
                       end
               else j:=j-1
       else i:=i+1.
   Для задач с несколькими возможными ответами рекомендуется выбирать такой
алгоритм, который приводит к результату быстрее и не использует больших
объемов дополнительной памяти. В данном случае это третий алгоритм, в котором
затраты памяти сводятся к одной вспомогательной переменной r, а результат
получается за один просмотр массива.