Обработка массива —Перестановка

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

´В задачах из таблицы массив задан (под словом "задан" будем понимать, что массив описан и значения его элементов определены).

Задачи, в которых требуется поменять местами элементы массива.
Перестановка элементов массива в обратном порядке(.pas)
	Метод решения: 1.Решаем путем перестановки элементов массива попарно - первый с последним, второй с предпоследним, и т.д. Значит, i-ый элемент меняем местами с (n-i+1)-ым 2. Количество таких перестановок в два раза меньше количества элементов. for i:=1 to n div 2  do                      begin                              c:=a[i];                              a[i]:=a[n+1-i];                               a[n+1-i]:=c;                       end;
Перестановка соседних элементов массива (.pas)
	Метод решения: 1.Решаем путем перестановки элементов массива попарно - первый со вторым, третий с четвёртым т.е. элемент с нечетным номером с элементом, имеющим четный номер и т.д. Значит, (2*i-1)-ый элемент меняем местами с (2*i)-ым 2. Количество таких перестановок в два раза меньше количества элементов. for i:=1 to n div 2 do begin          k:=x[2*i-1];          x[2*i-1]:=x[2*i];          x[2*i]:=k; end;
Обмен половин массива(.pas)
	Метод решения: 1.Решаем путем перестановки элементов массива попарно - i-ый c( i+k)-ым, где k=n div 2. 2. Количество таких перестановок в два раза меньше количества элементов. k:=n div 2; for i:=1 to n div 2 do                             begin                             c:=a[i];                             a[i]:=a[k+i];                             a[k+i]:=c;   end;
Перестановка максимального и минимального элементов массива.(.pas)
	Метод решения: 1.Находим номер наибольшего и наименьшего элементов массива. 2. Меняет наибольший и наименьший элементы местами. imax:=1; imin:=1; for i:=2 to n do          if a[i]>a[imax] then imax:=i                   else if a[i]c:=a[imin]; a[imin]:=a[imax]; a[imax]:=c;
Задачи циклической перестановки.
Циклический сдвиг элементов массива на один элемент вправо, последний элемент при этом должен оказаться на первом месте.(.pas)
	c:=a[n]; for i:=n downto 2 do a[i]:=a[i-1]; a[1]:=c;
Циклический сдвиг элементов массива на один элемент влево, первый элемент при этом должен оказаться на последнем месте.(.pas)
	c:=a[1]; for i:=2 to n do a[i-1]:=a[i]; a[n]:=c;
Задачи сортировки элементов массива.
Сортировка «пузырьком» (.pas)
	Метод решения: - Сравниваются пары соседних элементов массива и, если значения элементов в паре стоят в неправильном порядке (правый меньше левого), то меняем их местами. В результате одного такого прохода по массиву самый большой элемент окажется на последней позиции. - Всю процедуру повторяем столько раз, сколько элементов нужно поставить на нужное место то есть n-1. for k:=n-1 downto 1 do for i:=1 to k do                   if a[i+1]                                                      c:=a[i];                                                       a[i]:=a[i+1];                                                       a[i+1]:=c;                                              end;
Сортировка выбором(.pas)
	Метод решения: В неупорядоченной последовательности выбирается минимальный (максимальный) элемент и записывается на первое место. Этот элемент исключается из дальнейшей обработки. Оставшаяся последовательность элементов принимается за исходную. И процесс повторяется до тех пор, пока все элементы не будут выбраны. for k:=1 to n do                  begin                  min := a[k];                  imin := k;                  for j := k+1 to n do                                   if a[j] < min then begin                                                                     min:= a[j];                                                                     imin:=j                                                              end;                  a[imin] := a[k];                  a[k] :=min; end;
Сортировка методом прямого включения(.pas)
	Метод решения: При сортировке из неупорядоченной последовательности элементов поочередно выбирается каждый элемент, сравнивается с уже упорядоченными элементами и помещается на соответствующее место в списке упорядоченных элементов. for k := 2 to n do                  begin                           w := a[k];                           j := k-1;                           while (j > 0) and (w <= a[j]) do                                                                     begin                                                                     a[j+1] := a[j];                                                                     j:=j-1;                                                                     end;                             a[j+1] := w;                  end;