5. Организация сложных циклов.

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

Использование операторов цикла при разработке программ подразумевает соблюдение нескольких простых правил:

1. внутренние циклы должны находиться в теле внешнего цикла полностью;

2) передача управления из тела внешнего цикла в тело внутреннего возможна только через начало внутреннего цикла (рис.2);

Рис.2. Варианты передачи управления из внешнего цикла во внутреннний: 1-правильно; 2 и 3-неправильно.

3) передача управления из тела внутреннего цикла в тело внешнего возможна в двух случаях:

а) после того, как вычисления, предусмотренные телом внутреннего цикла выполнены заданное число раз, - это так называемый нормальный выход во внешний цикл;

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

Рис.3 Варианты передачи управления из тела внутреннего цикла в тело внешнего: 1-нормальный выход; 2 и 3-выход "по условию".

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

Пример

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

Рассмотрим один из наиболее простых алгоритмов, разработанных для задач такого рода (рис.5).

Идея этого алгоритма заключается в том, что элементы исходного массива сравниваются попарно - сначала a₁ c a₂, потом a₂ c a₃, далее a₃ с a₄ и т.д. Если первый элемент в паре больше второго, то меняют их численные значения, в результате чего первый элемент получает значение второго, а второй - первого. В противном случае никаких замен в паре не производят, а переходят к сравнению элементов второй пары.

Таким образом, происходит как бы постепенное "проталкивание" наибольшего элемента в конец массива, причём функцию "толкача" в алгоритме выполняет внутренний цикл. Как только наибольший элемент массива займёт предназначенне ему последнее 10-е место, описанную процедуру повторяют с оставшимися неупорядоченными 9-ю элементами, в результате чего наибольший из оставшихся элемент займёт предпоследнее место в массиве и т.д.

Для получения искомого результата такую процедуру нужно выполнить девять раз, причем с каждым разом число повторений внутреннего цикла должно уменьшаться на 1.

Эту задачу решает внешний цикл. Его параметр, пробегая от повторения к повторению значения 9,8,7,...,1 служит не только счетчиком числа выполненных повторений, но, в то же время, и наибольшим значением параметра внутреннего цикла.

рис. 4

program sort;

var

i,k : integer ;

b : real ;

a : array [1..10] of real ;

begin

write(‘введите массив - ‘);

for i:=1 to 10 do readln(a[i]);

writeln(' исходный массив');

for i:=1 to 10 do writeln(a[i]:5:2);

for i:=9 downto 1 do

for k:=1 to i do if a[k]>a[k+1] then

begin

b:=a[k]; a[k]:=a[k+1]; a[k+1]:=b

end

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

for i:=1 to 10 do write(a[i]:5:2)

end.

Пример

Дана матрица В(20*20). Сформировать вектор С(20), каждый элемент которого есть произведение элементов столбца матрицы за исключением элемента, лежащего на главной диагонали. Индексацию строк и столбцов исходной матрицы начать с нуля, индексацию элементов вектора с 10.

Формирование нового массива (вектора) представляет собой запись значений его элементов в зарезервированные для них ячейки памяти. Численное значение каждого элемента вектора С формируется во внутреннем цикле алгоритма, а запись в ячейку - во внешнем после завершения очередного повторения тела внутреннего цикла.

program massiv;

var

b : array [0..19,0..19] of real ;

c : array [10..29] of real ;

p : real ;

m,n : integer ;

begin

for m:=0 to 19 do

for n:=0 to 19 do readln(b[m,n]);

for n:=0 to 19 do

begin

p:=1; for m:=0 to 19 do

if m<>n then { формирование произведения }

p:=pb[m,n]; { элементов столбца матрицы }

{ за исключением диагонального }

c[n+10]:=p; { запись сформированного }

{ элемента вектора в ячейку памяти }

end;

for n:=10 to 19 do writeln(c[n]:10:3)

end.

Пример

Дана матрица МАТ(5*5), состоящая из вещественных элементов. Поменять местами строки матрицы, содержащие максимальный и минимальный элементы.

program MinMax;

type

m = array [1..5] of real ;

var

mat : array [1..5] of m ;

str : m;

maxi,mini,i,j,i1,j1 : integer ;

begin

write(‘введите матрицу - ‘);

for i:=1 to 5 do for j:=1 to 5 do read(mat[i,j]);

i1:=1; j1:=1; { индексы минимального элемента }

i2:=1; j2:=1; { индексы максимального элемента }

for i:=1 to 5 do

for j:=1 to 5 do

if mat[i,j]>mat[i2,j2]

then

begin

i2:=i; j2:=j {запомнить индексы нового максимума }

end

else

if mat[i,j]<mat[i1,j1]

then

begin

i1:=i; j1:=j; { запомнить индексы нового минимума }

end;

str:=mat[i2]; { замена строки матрицы mat, }

mat[i2]:=mat[i1]; { содержащей максимальный }

mat[i1]:=str; { элемент, строкой с минималь- }

{ ным элементом и наоборот }

for i:=1 to 5 do

begin

for j:=1 to 5 do write(mat[i,j]);

writeln

end

Программа решает две основные задачи: поиск номеров строк, в которых располагаются наибольший и наименьший элементы матрицы, и обмен данными, содержащимися в этих строках.

Первая задача является разновидностью типовой задачи поиска максимума или минимума [2].

Отличие от типовой заключается в том, что определяются не сами максимальный и минимальный элементы матрицы, а их индексы. Для хранения индексов в процессе счёта используются переменные i1, j1 - для минимального элемента и i2, j2 - для максимального.

Для решения второй задачи используются три оператора присваивания в которых участвуют строки матрицы с максимальным и минимальным элементами и эквивалентный им вспомогательный одномерный массив str.

Рис. 5.