Некоторые приёмы программирования

Некоторые приёмы программирования

Наиболее часто используемые приёмы программирования, применяемые студентами на практических занятиях, рассматриваются на примерах обработки числового массива A с количеством элементов N. Ниже представлены фрагменты программ на языке Pascal для каждого из предложенных приемов.

Вычисление суммы и произведения элементов массива:

………

S:=0;                                       / / сумма

P:=1;                                      / / произведение

FOR I:=1 TO N DO BEGIN

S:= S+A[I];

P:= P*A[I]; END;

……..

Нахождение максимального (минимального) элемента массива (на примере нахождения максимального элемента):

…………

IMAX:=1;

FOR I:=2 TO N DO IF A[I]>A[IMAX]

THEN

IMAX:=I;

…………

Здесь IMAX – номер максимального элемента;

A[IMAX] – максимальный элемент.

Удаление заданного (К-го) элемента массива:

………..

FOR I:=K TO N-1 DO A[I]:=A[I+1];

N:=N-1;

………..

Вставка нового элемента (M) на заданное (К-е) место в массив:

…………

N:=N+1;

FOR I:=N DOWNTO K+1 DO A[I]:=A[I-1];

A[K]:=M;

………..

Сортировка массива

1.      Метод обмена («метод пузырька»):

Суть данного метода заключается в сравнении соседних элементов массива, начиная с первой и до последней пары. Если предыдущий элемент пары больше последующего (при сортировке по возрастанию), то соседи меняются местами. Для полной сортировки необходимо сделать N-1 таких «проходов» по массиву.

..............

FOR J:= 1 TO N-1 DO FOR I:= 1 TO N-1 DO

IF A[I] > A[I+1] THEN

BEGIN

BUF:= A[I]; A[I]:= A[I+1]; A[I+1]:= BUF;

END;

……….

Здесь BUF – буферная переменная для перестановки;

Метод обмена можно ускорить двумя способами:

а) уменьшать на каждом проходе количество сравниваемых пар:

..............

FOR J:= 1 TO N-1 DO         // или    FOR J:=N-1 DOWNTO 1 DO FOR I:= 1 TO N-J DO                 //                FOR I:=1 TO J DO

IF A[I] > A[I+1] THEN

……….

END;

BEGIN BUF:= A[I];

A[I]:= A[I+1]; A[I+1]:= BUF;

б) прекращать сортировку при окончании перестановок:

……….… K:=N; REPEAT

PORYADOK:=TRUE; K:= K-1;

FOR I:= 1 TO K DO IF A[I] > A[I+1]

THEN BEGIN

BUF:= A[I]; A[I]:= A[I+1]; A[I+1]:= BUF;

PORYADOK:=FALSE; END;

UNTIL PORYADOK;

…………

2.      Метод выбора:

Суть метода выбора: при сортировке по возрастанию находится минимальный элемент в диапазоне от первого до последнего и меняется местами с первым. Далее находится минимальный элемент от второго до последнего и меняется со вторым и т.д.

………..

FOR I:= 1 TO N-1 DO BEGIN

MIN:= A[I]; IMIN:=I;

FOR J:= I+1 TO N DO IF A[J] < MIN

THEN BEGIN

MIN:= A[J]; IMIN:= J;

END; A[IMIN]:= A[I]; A[I]:= MIN; END;

…………

3.      Метод вставки:

Считается, что массив разделён на две части: отсортированную (в начале массива) и неотсортированную (в остальной части массива). В самом начале отсортированная часть состоит из первого элемента. Первый элемент из неотсортированной части (его номер – I) вставляется в отсортированную часть без изменения порядка (в позицию J):

……..

FOR I:= 2 TO N DO BEGIN

BUF:= A[I]; J:= 1;

WHILE BUF > A[J] DO J:= J+1;

FOR K:= I DOWNTO J+1 DO A[K]:= A[K-1];

A[J]:=BUF;

END;

………