Как найти произведение элементов массива pascal

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

Нахождение суммы и произведения элементов массива аналогичны алгоритмам нахождения суммы и произведения элементов последовательности.

Дан массив X, состоящий из n элементов. Найти сумму элементов этого массива. Переменной S присваивается значение, равное нулю, затем последовательно суммируются элементы массива X. Блок-схема алгоритма расчёта суммы приведена на рис. 5.19.

Соответствующий алгоритму фрагмент программы будет иметь вид:

s : = 0;
for i :=1 to n do
s := s+x [ i ];
writeln ( ’ s= ’, s : 7 : 3 );

Найдём произведение элементов массива X. Решение задачи сводится к тому, что значение переменной Р, в которую предварительно была записана единица, последовательно умножается на значение i-го элемента массива. Блок-схема алгоритма приведена на рис. 5.20.

Соответствующий фрагмент программы будет иметь вид:

p : = 1;
for i :=1 to n do
p:=p * x [ i ];
writeln ( ’P= ’,P : 7 : 3 );

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

Рассмотрим задачу поиска максимального элемента (Max) и его номера (Nmax) в массиве X, состоящем из n элементов.

Алгоритм решения задачи следующий. Предположим, что первый элемент массива является максимальным, и запишем его в переменную Max, а в Nmax — его номер (число 1). Затем все элементы, начиная со второго, сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax — текущее значение индекса i. Процесс определения максимального элемента в массиве изображен при помощи блок-схемы на рис. 5.21.

Соответствующий фрагмент программы имеет вид:

Max:=X [ 1 ];
Nmax: = 1;
for i :=2 to n do
if X[ i ]>Max then
begin
Max:=X[ i ];
Nmax:= i;
end;
write ( ’  Max= ’,Max : 1 : 3, ’  Nmax= ’,Nmax );

Алгоритм поиска минимального элемента в массиве будет отличаться от приведённого выше лишь тем, что в условном блоке и, соответственно, в конструкции if текста программы знак поменяется с > на <.

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

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

и в порядке убывания, если

Многие алгоритмы сортировки основаны на том факте, что переставлять два элемента надо таким образом, чтобы после перестановки они были правильно расположены друг относительно друга. При сортировке по возрастанию после перестановки элемент с меньшим индексом должен быть не больше элемента с большим
индексом^{2При сортировке по убыванию после перестановки элемент с меньшим индексом должен быть не меньше элемента с большим индексом.}. Рассмотрим некоторые из алгоритмов.

5.7.1 Сортировка методом “пузырька”

Наиболее известным методом сортировки является сортировка массивов пузырьковым методом. Её популярность объясняется запоминающимся
названием^{3Название алгоритма объясняется его сходством с процессом движения пузырьков в резервуаре с водой, когда каждый пузырёк находит свой собственный уровень.} и простотой алгоритма. Сортировкаметодом “пузырька” основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки на примере сортировки по возрастанию более подробно.

Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Затем сравним второй с третьим, и если второй окажется больше третьего, то поменяем и их. Далее сравниваем третий и четвёртый, и если третий большего четвёртого, их также меняем местами. После трёх этих сравнений самым большим элементом станет элемент с номером 4. Если продолжить сравнение соседних элементов: сравнить четвертый с пятым, пятый с шестым и т. д. до сравнения -го и n-го элементов, то в результате этих действий самый большой элемент станет на последнее (-е) место.

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

В табл. 5.8 подробно показан процесс упорядочения элементов в массиве.

Нетрудно заметить, что для преобразования массива, состоящего из элементов, необходимо просмотреть его раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок-схема описанного алгоритма приведена на рис. 5.22. Для обмена двух элементов в массиве (блок 4) используется буферная переменная , в которой временно хранится значение элемента, подлежащего замене.

Ниже приведён текст консольного приложения, предназначенного для упорядочения массива по возрастанию методом пузырька.

program upor_massiv;
var i, j, n : byte;
	X: array [ 1.. 100 ] of real;
	b : real;
begin
writeln ( ’введите размер массива ’ );
	readln ( n );
for i :=1 to n do
begin
write ( ’X[ ’, i, ’ ]= ’ );
readln (X[ i ] );
end;
writeln ( ’массив X  ’ );
for i :=1 to n do write ( x [ i ] : 5 : 2, ’   ’ );
writeln;
for j :=1 to n-1 do
for i :=1 to n-j do
		if X[ i ] > X[ i +1] then
	{Если текущий элемент больше следующего, то}
		begin {поменять их местами.}
			b:=X[ i ]; {Сохранить значение текущего элемента.}
			X[ i ] : =X[ i + 1 ]; {Заменить текущий элемент следующим.}
			X[ i +1]:=b; {Заменить следующий элемент переменной b.}
		end;
writeln ( ’упорядоченный массив ’ );
for i :=1 to n do
	write (X[ i ] : 5 : 2, ’   ’ );
writeln;
end.

На рис. 5.23 приведены результаты работы этой программы.

Для упорядочения элементов в массиве по убыванию их значений необходимо при сравнении элементов массива заменить знак > на < (см. блок 3 на рис. 5.22).

Рассмотрим следующий алгоритм сортировки.

5.7.2 Сортировка выбором

Для сортировки элементов массива по возрастанию (по убыванию) можно воспользоваться алгоритмом сортировки выбора максимального (минимального) элемента. Алгоритм выбором приведён в виде блок-схемы на рис. 5.24.

Найдём в массиве самый большой элемент (блоки 2—5) и поменяем его местами с последним элементом (блок 6). После этого максимальный элемент встанет на своё место. Теперь надо повторять эти действия (блоки 2—6), уменьшив количество просматриваемых элементов на единицу (блок 7) до тех пор, пока количество рассматриваемых элементов не станет равным одному (блок 8). В связи с тем, что мы на каждом шаге уменьшаем количество элементов на 1, то, чтобы не потерять размер массива (N), необходимо в начале алгоритма переписать N в переменную K (блок 1) и уменьшать уже значение K.

При упорядочении массива по убыванию необходимо перемещать минимальный элемент. Для этого в алгоритме (рис. 5.24) в блоке 4 достаточно поменять знак > на знак <.

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

k:=n;
repeat
max:=x [ 1 ];
nom: = 1;
for i :=2 to k do
if max < X[ i ] then
begin
max:=X[ i ];
nom:= i;
end;
b:=x [ nom ]; x [ nom] : = x [ k ]; x [ k ] : = b;
k:=k -1;
until k=1;

Следующим важным алгоритмом обработки массивов является алгоритм удаления элемента из массива.

Перейти к контенту

Program proisveden;

Var a: array[1..100] of integer;

      i, n, p: integer;

Begin

  Write (‘Сколько элементов? ’);  Readln (n);

  p:=1;

  For i:=1 to n do

     begin

       write (‘введите число’); readln (a[i]);

       p:=p*a[i];

     end;

     writeln(‘произведение элементов равно:  ‘,p);

End.

Сегодня мы с вами наконец-то начинаем новую тему — одномерные массивы.

Одномерные массивы. Определение.

Одномерный массив — это фиксированное количество элементов одного и того же типа, объединенных одним именем, где каждый элемент имеет свой номер. Обращение к элементам массива осуществляется с помощью указания имени массива и номеров элементов.

var 
   a : array [1..N] of integer;

//или
type 
  arr = array[1..N] of integer;

var
  a: arr;

Между именем типа и именем переменной ставится знак «двоеточие». Array — служебное слово (в переводе с английского означает «массив», «набор»); [1..N] — в квадратных скобках указывается номер первого элемента, затем, после двух точек, номер последнего элемента массива; of — служебное слово (в переводе с английского «из»); integer — тип элементов массива.

Индексом могут быть не только натуральные числа: мы можем написать так: [0..10], [-29..45], [‘a’..’z’], [false..true] — то есть нам подходят любые символы и числа — главное соблюсти следующее условие: левая часть меньше правой. Для того чтобы определить, что меньше — восклицательный знак(‘!’) или точка(‘.’) используем таблицу ASCII и функции Ord() и Chr().

Как же производится ввод одномерного массива?

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

for i := 1 to N do
   read(a[i]); //где a[i] -- элемент одномерного массива a с индексом (порядковым номером) i.

Как видите, ничего страшного в массивах нет. Массивы применяют в тех случаях, когда нельзя обойтись одной-двумя переменными (примеры таких задач мы рассматривали в решении задач из блока Series). В случаях, когда после ввода последовательности целиком пользователю необходимо обратиться к переменным в середине последовательности, в начале, поменять их значения местами, отсортировать.

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

Одномерные массивы. Решение задач.

Series8. Дано целое число N и набор из N целых чисел. Вывести в том же порядке все четные числа из данного набора и количество K таких чисел.

Исходное решение: Series8.

Модифицированное решение:

var
  a: array[1..1000] of integer; {мы не знаем заранее N, поэтому берем с запасом.}
  k, N, i: integer;

begin
  write('N = '); 
  readln(N);  
  write('Введите ', N, ' целых чисел: '); 
  for i := 1 to N do read(a[i]); {заполняем масссив}
  
  {Начинаем выбирать чётные числа}
  write('Чётные числа: ');
  for i := 1 to N do
  begin
    if a[i] mod 2 = 0 then 
    begin
      Inc(k);
      write(a[i], ' ');
    end;
  end;  
  writeln();
  writeln('Количество четных чисел - ', k); 
end.

Series28.  Дано целое число N и набор из N вещественных чисел: A₁, A₂, …, A_N. Вывести следующие числа:

(A₁)^N, (A₂)^N−1, …, (A_N−1)², A_N.

Исходное решение: Series28.

Более подробно про возведение числа в степень мы говорили в решении задачи for36.

Модифицированное решение:

var
  a: array[1..1000] of integer; 
  N, i, j, n_pow: integer;
  d, r: real;

begin
  write('N = ');
  readln(N);
  write('Введите ', N, ' целых чисел: '); 
  for i := 1 to N do read(a[i]);
  
  {Возводим элементы массива в степень}
  for i := 1 to N do
  begin
    n_pow := N + 1 - i;
    d := a[i];
    if n_pow mod 2 <> 0 then r := d else r := 1; //в r будет записываться результат
    while n_pow > 1 do
    begin
      n_pow := n_pow div 2;
      d := d * d;
      if n_pow mod 2 <> 0 then r := r * d;
    end;
    writeln(a[i], ' в степени ', N + 1 - i, ' равно ', r);
  end;
end.

Ну и напоследок давайте разберём веселенькую задачу на длинную арифметику.

Задача. Найти факториал числа. 

Мы уже решали эту задачу здесь(for19).

Научимся вычислять факториал натурального числа N. Факториал числа — это произведение чисел 1*2*3*…*(N-1 )*N (обозначается как N!).  Сложность задачи в том, что уже 8!=40320, а 13!=6227020800. Типы данных Integer, Longlnt применимы весьма в ограниченном диапазоне натуральных чисел. Для представления факториала договоримся использовать массив. Пример:

В массиве записано значение 11!=39916800. Каким образом? В А[0] фиксируется число занятых элементов массива, в А[1] — цифра единиц результата, в А[2] — цифра десятков результата, в А[3] — цифра сотен результата и т. д. Почему так, а не наоборот? Такая запись позволяет исключить сдвиг элементов массива при переносе значений в старший разряд. А сейчас наберите, как обычно, текст программы, выполните компиляцию и, выполните ее в пошаговом режиме, отслеживая изменение значений переменных при не очень большом значении N. Добейтесь полного понимания логики работы программы.

Для того чтобы выполнить программу в пошаговом режиме, нажмите «шаг без входа в подпрограмму» и перейдите в «локальные переменные».

const 
  MaxN = 300;

var
  A: array [0..MaxN] of integer;
  i, j, r, w, N: integer;

begin
  Write('Введите число, факториал которого необходимо подсчитать: ');
  Read(N);
  A[0] := 1;
  A[1] := 1; 
  j := 2; {Начальные присвоения, начинаем вычислять 2! }
  while (j <= N) and (A[0] < MaxN) Do {Второе условие 
  позволяет избежать выхода из границ диапазона, если 
  количество цифр в факториале превзойдет 300.}
  begin
    r := 0;
    i := 1;
    {r - перенос из разряда в разряд при
    выполнении умножения числа j на очередную цифру
    A[i] предыдущего результата.}
    while (i <= A[0]) or (r <> 0) Do 
    begin
      {Пока не
      «прошли» все цифры предыдущего результата или
      есть перенос цифры в старший разряд}
      w := A[i] * j + r;{Умножаем очередную цифру и
      прибавляем цифру переноса из предыдущего
      разряда}
      A[i] := w mod 10; {Оставляем остаток от деления на 10}
      r := w div 10;{Вычисляем значение переноса}
      if A[A[0] + 1] <> 0 then Inc(A[0]);{Изменяем 
      количество элементов, если их количество увеличилось.}
      Inc(i);
    end;
    Inc(j);
  end;
  write('Факториал: ');
  for i := A[0] downto 1 Do Write(A[i]);{Вывод результата}
end.

Подведем итоги:

Одномерный массив — это конечное упорядоченное множество элементов. За первым элементом идет второй, за вторым — третий и т. д. Индекс может быть чем угодно — и целым числом, и символом. Но чаще мы всё-таки будем пользоваться следующим диапазоном:  [1.. N].

На сегодня все! Если у вас еще остались вопросы о том, как работает программа выше, оставляйте их в комментариях. И очень скоро мы начнем решать задачи на массивы из задачника М. Э. Абрамяна.