Файл: Митяков Информатика Часть 1.pdf

56 

Таким образом, перед началом цикла суммирования в памяти ЭВМ будет сле-

дующая картина: 

0 1 

3 

-2 

0 

5 

Внутри  тела  цикла  необходимо  поставить  оператор  присваивания 

s=s+x(i). В этом случае работа алгоритма в динамике имеет вид: 

i 

1 2 3 4 5 

s 

1 4 2 2 7 

Таким образом, по окончании цикла в ячейке s содержится сумма элемен-

тов массива  x. 

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

элементов  массива.  В  этом  случае  в  тело  цикла  необходимо  дополнительно 

вставить блок разветвления, определяющий условие положительности элемен-

та, а работа алгоритма имеет вид: 

i 

1 2  3  4  5 

s 

1 4  4  4  9 

Аналогично устроена работа алгоритмов по нахождению произведения и 

количества элементов массива. 

Для нахождения произведения необходимо ввести дополнительную ячей-

ку p, в которую до начала цикла записать с помощью оператора присваивания 

единицу: p=1. Внутри тела цикла должен быть блок нахождения произведения 

p=p*x(i).  По  окончании  цикла  в  ячейке  p  содержится  произведение  элементов 

массива.  Для  нахождения  количества  элементов  (например,  положительных) 

необходимо до цикла записать в ячейку k ноль: k=0. В теле цикла, наряду с ус-

ловием положительности, содержится блок k=k+1, подсчитывающий число по-

ложительных элементов. 

Рассмотрим  полностью  решение  задачи  о  нахождении  суммы  положи-

тельных элементов массива x(5) (фрагменты блок-схем ввода и вывода массива 

даны в сокращении). 

57 

Блок-схема 

Программа на Фортране 

DIMENSION x(5) 
WRITE(*,*)’Введите массив x(5)’ 
DO i=1,5 

READ(*,*) x(i) 

END DO 
WRITE(*,*)’Массив x(5)’ 
DO i=1,5 

WRITE(*,*) x(i) 

END DO 
s=0 
DO i=1,5 

IF(x(i).GT.0) THEN 

s=s+x(i) 

END IF 

END DO 
WRITE(*,*) ’s=’,s 
END 

Перестановка элементов массива 

Для перестановки местами элементов массива необходимо ввести проме-

жуточную ячейку «c» и выполнить действия, аналогичные замене старого теле-
визора на новый. Если Вы приобрели новый телевизор (в коробке) и Вам необ-
ходимо установить его на тумбочку, а старый - в коробку, то вам понадобится 
стол (ячейка «с»).  

То  же  самое  нужно  сделать,  если  нужно  поменять  местами,  например, 

элементы  x

1

  и  x

5

  массива.  Последовательность    действий    представлена    на    

рис. 10. 

Рис. 11. Иллюстрация алгоритма перестановки элементов 

i=1

i=i+1 

i 

≤ 5 

да 

нет 

s=s+x

i

x

i 

> 0 

да 

нет 

x(5)

Вывод массива 

Ввод массива 

s=0

конец 

s

Рекорд 

Sony

1

2 

3

x

1

x

5

c 

58 

Для перестановки местами элементов массива необходимо ввести проме-

жуточную ячейку c. Если нужно поменять местами, например, элементы x

1

 и x

5

массива, то выполняется следующая последовательность действий: 

c = x(1) 
x(1) = x(5) 
x(5) = c 
Во  многих  задачах  требуется  поменять  местами  максимальный  (мини-

мальный) элемент массива с другим элементом. В этом случае при нахождении 

максимума (минимума) запоминают его индекс, а затем используют его в алго-

ритме замены. 

Нахождение максимального (минимального) 

элемента массива 

Пусть требуется найти максимальный элемент массива x(5). Для этого не-

обходимо  использовать  цикл  и  алгоритм  «взвешивания».  Понадобится  также 

дополнительная  ячейка  xmax,  фиксирующая  максимальный  элемент  и  ячейка 

imax, фиксирующая его индекс. Последняя ячейка нужна только в том случае, 

если в дальнейшем потребуется менять местами максимальный элемент масси-

ва с другим. 

Алгоритм  нахождения  максимального  элемента  сводится  к  следующему 

(рис. 12). Представьте, что у Вас есть мешок с яблоками (массив x(5)), из кото-

рого  нужно  выбрать  яблоко  максимального  веса.  В  вашем  распоряжении  есть 

двуплечные весы без гирь. Левая чаша весов - ячейка xmax, где должен оказать-

ся максимальный элемент. Правая чаша весов предназначена для текущего эле-

мента массива xi . 

Рис. 12. Иллюстрация алгоритма нахождения максимального элемента массива 

xmax

x(i)

59 

До  начала  цикла  взвешивания  нужно  в  ячейку  xmax  записать  очень  ма-

ленькое  число,  заведомо  меньшее  всех  элементов  массива  (например, -1000). 

Затем внутри тела цикла для каждого элемента массива осуществляется «взве-

шивание» - сравнение  с  содержимым  ячейки  xmax.  Если  перевешивает  левая 

чаша весов, то нужно перейти к следующему элементу массива. 

Если  же  перевесила  правая  чаша  весов,  то  значит,  что  текущий  элемент 

больше  содержимого  ячейки  xmax,  и  его  нужно  переложить  на  левую  чашу 

(xmax=x(i)).  Кроме  того,  в  случае  необходимости  здесь  нужно  зафиксировать 

индекс  найденного  «более  тяжелого»  элемента  (imax=i).  Таким  образом,  по 

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

а ячейка imax - его номер (индекс). 

Рассмотрим, как изменяются ячейки памяти ЭВМ при нахождении макси-

мального элемента массива x(5). Перед началом цикла «взвешивания» в памяти 

ЭВМ будет следующая картина: 

xmax 

-1000  imax   1 

3 

-2 

0 

5 

Работа алгоритма в динамике имеет вид: 

i 

1 2  3  4  5 

xmax 

1 3  3  3  5 

imax 

1 2  2  2  5 

Аналогично работает алгоритм нахождения минимального элемента мас-

сива. В этом случае вводим ячейки xmin и imin. До начала цикла взвешивания в 

ячейку xmin записывается очень большое число (например, 1000). При взвеши-

вании  проверяется  условие  x(i)<xmin.  Если  оно  выполняется,  то  нужно  «пере-

ложить»  элемент  (xmin= x(i))  и,  если  необходимо,  зафиксировать  его  индекс 

(imin=i).  Если  условие  не  выполняется,  то  нужно  перейти  к  следующему  эле-

менту. По окончании цикла ячейка xmin будет содержать минимальный элемент 

массива, а ячейка imin - его индекс. 

Пример. В одномерном массиве b(15) найти максимальный элемент и по-

менять его местами с первым. 

60 

Блок-схема 

Программа на Фортране 

DIMENSION b(15) 
WRITE(*,*)’Введите массив b(15)’ 
DO i=1,15 

READ(*,*) b(i) 

END DO 
WRITE(*,*)’Исходный массив b(15)’ 
DO i=1,15 

WRITE(*,*) b(i) 

END DO 
bmax=-1000 
DO i=1,15 

IF(b(i).GT.bmax) THEN 

bmax=b(i) 
imax=i 

 END IF 

END DO 
WRITE(*,*) ’bm=’,bmax,’im=’,imax 
c=b(imax) 
b(imax)=b(1) 
b(1)=c 
WRITE(*,*)’Новый массив b(15)’ 
DO i=1,15 

WRITE(*,*) b(i) 

END DO 
END 

Пример 1. Дана матрица a из четырех строк и пяти столбцов. Для каждой 

строки  вычислить  произведение  ее  элементов.  Из  полученных  произведений 

образовать новый массив b и вывести его на печать. Результирующий массив b 

будет содержать четыре элемента, причем его элементы вычисляются по фор-

муле: 

∏

=

=

=

5

1

,

4

,...,

1

,

j

ij

i

i

a

b

 где a

ij

 – элемент матрицы a.  

i=1 

i=i+1 

i 

≤ 15 

да 

нет 

bmax=b

i

b

i 

> bmax 

да 

нет 

b(15) 

Вывод массива 

Ввод массива 

bmax=-1000 

конец 

imax=i 

b

1

 = c 

c = b

imax

b

imax

 = b

1

Вывод нового мас-

сива 

bmax, imax