Задача 50. Вспомогательные алгоритмы. Обработка двух массивов с получением новых массивов

Условие задачи. Даны два массива: А – из N чисел, В – из М чисел. Для каждого из них сформировать массив из тех элементов, которые превышают среднее арифметическое всех чисел своего массива.

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

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

В рамках данной задачи нельзя однозначно определить, какой способ будет лучше, без выяснения, как именно в том или ином языке программирования осуществляется передача массивов в процедуры и функции и возврат массивов из процедур и функций, ибо общая идея декомпозиции оказывается одинаковой – выполнение одного алгоритма формирования нового массива над несколькими наборами исходных данных.

Непосредственно алгоритм вычисления среднего арифметического всех элементов массива был описан в задаче 26, алгоритм формирования нового массива на основе исходного и некоторого критерия отбора был описан в задаче 35. На их основе, а также предполагая, что у нас имеются вспомогательные алгоритмы для ввода и для вывода значений массивов указанной размерности (описание алгоритма ввода массива приведено в задаче 48), рассмотрим второй способ. При этом, для повышения наглядности сначала приведем вариант алгоритма вывода массива вещественных чисел, позволяющий явно указывать, какое имя массива должно быть выведено в строке перед значением индекса каждого элемента массива и самим значением элемента. Дадим ему номер 50.1 и имя OutputRealArray. Каждое значение отделяется от следующего как минимум пробелом или выводится на отдельной строке – определяется реализацией, в описании алгоритма укажем в качестве разделителя одиночный пробел.

Структурированная запись алгоритма 50.1

Имя алгоритма: OutputRealArray

Входные данные: MasName – строка, содержащая имя массива, выводимое перед индексом элемента; M – массив чисел; N – количество элементов в массиве.

На вход нельзя подавать N не целое, меньшее 1 или большее числа элементов в массиве M. Некорректные значения N могут приводить к неожиданным результатам или аварийным ситуациям, зависящим от конкретной реализации способа доступа к элементам массива по индексу.

Выходные данные отсутствуют.

5. Повторить для i от 1 до N:

1.1. Вывести имя массива MasName, символ «[», значение переменной i, символы «]=», значение M [ i ], пробел.

6. Вернуться в точку обращения к алгоритму.

Теперь оформим алгоритм вычисления среднего арифметического элементов массива на основании задачи 26.

Структурированная запись алгоритма 50.2

Имя алгоритма: CalcAverage

Входные данные: M – массив чисел; N – количество элементов в массиве.

На вход нельзя подавать N не целое или меньшее 1.

Выходные данные (возвращаются именем алгоритма как функцией): Sr – среднее арифметическое элементов в массиве.

1. Если N < 1, то завершить работу аварийно.

2. Sr = 0

3. Повторить для i от 1 до N:

3.1. Sr = Sr + M [ i ]

4. Sr = Sr / N

5. Вернуть Sr

Схема алгоритма

Запишем алгоритм формирования нового массива с использованием алгоритма CalcAverage (50.2).

Структурированная запись алгоритма 50.3

Имя алгоритма: CreateNewArray.

Входные данные: MI – исходный массив чисел; NI – количество элементов в исходном массиве.

На вход нельзя подавать NI не целое или меньшее 1.

Выходные данные: NO – количество элементов в сформированном массиве; MO – сформированный массив.

Сформированный массив может быть пустым (NO равно 0), если все элементы исходного массива равны среднему арифметическому.

1. Если NI < 1, то завершить работу аварийно.

2. NO = 0

3. S = CalcAverage(MI, NI)

4. Повторить для i от 1 до NI:

4.1. Если MI [ i ] > S, то добавить элемент в конец массива MO:

4.1.1. NO = NO + 1;

4.1.2. MO[NO] = MI[i].

5. Вернуть MO, NO

Схема алгоритма

 

Используя алгоритм CreateNewArray, запишем основной алгоритм решения задачи.

Структурированная запись алгоритма 50.4

1. Ввести число элементов N массива A и сам массив A

2. Ввести число элементов M массива B и сам массив В

3. Обратиться к алгоритму CreateNewArray с входными данными A, N, результирующий массив присвоить AO, количество элементов в нем присвоить NAO

4. Обратиться к алгоритму CreateNewArray с входными данными B, M, результирующий массив присвоить BO, количество элементов в нем присвоить NBO

Схема алгоритма

Программа на языке Си

#include <stdio.h>

#include <stdlib.h>

/* Функция выделяет память под массив из N элементов

типа double и заполняет его путем ввода значений с

клавиатуры. В случае ошибок возвращает NULL, иначе

указатель на выделенную область памяти */

double* InputRealArray(int N)

{

double *A=NULL;

int i;

if(N > 0){

   if((A=malloc(N*sizeof(double)))==NULL)

      return NULL;

   for(i=0; i<N; i++){

    printf("Введите %d-й элемент: ",i+1);

    scanf("%lf", &A[i]);

  }

  return A;

}

else

return NULL;

}

 

/* Вывод массива M из N элементов типа double.

MasName -- название массива на экране

(const char *) */

void OutputRealArray(const char *MasName,

                         double *M, int N)

{

int i;

for(i = 0; i < N; i++){

printf("%s[%d]=%lg ",MasName,i+1,M[i]);

}

}

 

/* Вычисление среднего арифметического для

 массива M из N элементов типа double.*/

double CalcAverage(double M[],int N){

int i;

double Sr;

if(N < 1){

printf("Переданное число элементов ");

  printf("массива не является натуральным!");

  exit(1);

}

Sr = 0;

for(i=0; i< N; i++)

Sr += M[i];

Sr /= N;

return Sr;

}

 

/* Формирование нового массива по предыдущему:

double *MI -- исходный массив

         (указатель на первый элемент)

int NI -- количество элементов в исходном массиве

double **MO -- указатель на переменную, которая

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

При ошибках - NULL, или если все элементы одинаковы

int *NO -- указатель на переменную, которая будет

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

При ошибках помещается значение -1, если нет

элементов, превышающих среднее - помещает значение 0

*/

void CreateNewArray(double *MI, int NI,

                       double **MO, int *NO){

double S;

int i;

*MO = NULL;

*NO = -1;

if(NI < 1 || MI == NULL)

return;    

if(*MO = malloc(NI*sizeof(double))){

   *NO = 0;

   S = CalcAverage(MI,NI);

   for(i=0; i < NI; i++)

      if(MI[i] > S){

       (*MO)[*NO]=MI[i];

       (*NO)++;

        }

if(*NO){

 if(*NO!= NI)

/* Перераспределение памяти */

*MO = realloc(*MO, (*NO)*sizeof(double));

 }

else

{

 free(*MO);

 *MO = NULL;

} 

}

}

 

int main(int argc, char *argv[]) {

int N, M, NAO, NBO;

double *A, *B, *AO, *BO;

printf("Введите число элементов массива A: ");

scanf("%d",&N);

A=InputRealArray(N);

printf("Введите число элементов массива B: ");

scanf("%d",&M);

B=InputRealArray(M);

CreateNewArray(A, N, &AO, &NAO);

CreateNewArray(B, M, &BO, &NBO);

OutputRealArray("AO",AO,NAO);

OutputRealArray("BO",BO,NBO);

if(A)

free(A);

if(B)

free(B);

if(AO)

free(AO);

if(BO)

free(BO);

printf("\n");

system("pause");

return 0;

}

Программа на языке Паскаль

program Main_50;

uses

Classes, SysUtils;

{ Используем динамические массивы }

type

TRealArray = array of Real;

var

N, M, NAO, NBO: Integer;

A, B, AO, BO: TRealArray;

 

procedure InputRealArray(var A:TRealArray;

                              N:Integer);

var

i: Integer;

begin

 if N < 0 then

begin

ExitCode:= 1;

Abort;

end;

SetLength(A, N);

for i:= 1 to N do

begin

write('Введите ',i,'-й элемент массива: ');

    readln(A[i-1]);

end;

end;

 

procedure OutputRealArray(MasName: string;

            const M: TRealArray; N: Integer);

var

i: Integer;

begin

for i:= 1 to N do

write(MasName,'[',i,']=',M[i-1]:8:3,' ');

end;

 

function CalcAverage(const M: TRealArray;

                          N: Integer): Real;

var

i: Integer;

Sr: Real;

begin

if N < 1 then

begin

ExitCode:= 1;

Abort;

end

else

begin

Sr:= 0;

for i:= 1 to N do

    Sr:= Sr + M[i-1];

Sr:= Sr / N;

CalcAverage:= Sr;

end;

end;

 

procedure CreateNewArray(const MI: TRealArray;

         NI: Integer; var MO: TRealArray;

                        var NO: Integer);

var

i: Integer;

S: Real;

begin

if NI < 1 then

begin

ExitCode:= 1;

Abort;

end

else

begin

SetLength(MO, 0);

NO:= 0;

S:= CalcAverage(MI, NI);

for i:= 0 to NI-1 do

   if MI[i] > S then

   begin

      NO:= NO + 1;

      SetLength(MO, NO);

      MO[NO-1]:= MI[i];

   end;

   end;

end;

 

begin

write('Введите N - число элементов массива A: ');

readln(N);

InputRealArray(A,N);

write('Введите M - число элементов массива B: ');

readln(M);

InputRealArray(B,M);

CreateNewArray(A,N,AO,NAO);

CreateNewArray(B,M,BO,NBO);

OutputRealArray('AO',AO,NAO);

OutputRealArray('BO',BO,NBO);

end.

Программа на языке Фортран

Program Main_50

Implicit none

integer N,M,NO,NBO

real, allocatable:: A(:), B(:),AO(:),BO(:)

print*,'Введите N -- число элементов массива A:'

read*,N

allocate (A(N))

call InputRealArray(A,N);

print*,'Введите M -- число элементов массива M:'

read*,M

allocate (B(M))

allocate (AO(N))

allocate (BO(M))

call InputRealArray(B,M)

call OutputRealArray('A',A,N)

call OutputRealArray('B',B,M)

call CreateNewArray(A,N,AO,NO)

call CreateNewArray(B,M,BO,NBO)

call OutputRealArray('AO',AO,NO)

call OutputRealArray('BO',BO,NBO)

deallocate (A)

deallocate (B)

deallocate (AO)

deallocate (BO)

end

! Ввод массива из N элементов:

Subroutine InputRealArray(X,N)

Implicit none

integer,intent(in):: N

real, intent(out):: X(N)

integer i

do i=1,N

  print '(1x,A,I1,A)','элемент(',i,')='

 read*,X(i)

enddo

end

! Вывод массива из N элементов:

Subroutine OutputRealArray(MasName,M,N)

Implicit none

integer,intent(in)::N

real,intent(in)::M(N)

character(*),intent(in)::MasName

integer i

do i=1,N

  print '(1x,A,A,I2,A,F5.1)', MasName,'[',i, &

                                    ']=',M(i)

enddo

end

! Расчет среднего арифметического для массива

! из N элементов

Real function CalcAverage(M,N)

Implicit none

integer,intent(in)::N

real,intent(in)::M(N)

integer i

real Sr

if (N<1) then

print*,'Переданное число элементов'

    print*,'массива не является натуральным!'

stop

endif

Sr=0

do i=1,N

 Sr=Sr+M(i)

enddo

Sr=Sr/N

CalcAverage=Sr

end

!Формирование нового массива:

Subroutine CreateNewArray(MI,NI,MO,NO)

Implicit none

integer, intent(in):: NI

real, intent(in):: MI(NI)

integer, intent(out):: NO

real, intent(out):: MO(NO)

integer i

real S, CalcAverage

NO=0

S = CalcAverage(MI,NI)

do i=1,NI

if (MI(i)>S) then

    NO=NO+1

    MO(NO)=MI(i)

endif

   enddo

end

Программа на языке Python

# В качестве массива используется стандартный

# тип list (список)

 

# Ввод массива из N элементов:

def InputRealArray(N):

A = [] # Создаем пустой список

for i in range(1,N+1):

print("Введите {0}-й элемент: ".format(i))

A.append(float(input()))

return A

 

# Вывод массива из N элементов:

def OutputRealArray(MasName,M,N):

for i in range(1,N+1):

print("{0}[{1}]={2} ".format(MasName,i,M[i-1]))

return None

 

# Расчет среднего арифметического для массива

# из N элементов

def CalcAverage(M, N):

if N < 1:

  quit(1)

else:

Sr = 0

for i in range(0, N):

Sr += M[i]

Sr /= N

return Sr

 

# Формирование нового массива:

def CreateNewArray(MI, NI):

if N < 1:

quit(1)

else:

MO = []

NO = 0

S = CalcAverage(MI, NI)

for i in range(0, N):

if MI[i] > S:

   MO.append(0.0)

   # Для выполнения шага 4.1.1,

   # значение заменится на шаге 4.1.3

   NO = NO + 1 

   MO[NO-1] = MI[i]

 # Поскольку индексы с 0, то последний на 1 меньше

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

return NO, MO

 

print("Введите N -- число элементов массива A: ")

N=int(input())  

A=InputRealArray(N)

print("Введите M -- число элементов массива M: ")

M=int(input())  

B=InputRealArray(M)

NAO, AO = CreateNewArray(A, N)

NBO, BO = CreateNewArray(B, M)

OutputRealArray("AO",AO,NAO)

OutputRealArray("AO",BO,NBO)

Программа в системе Матлаб

N=input('Введите N -- число элементов массива A: ');

A=InputRealArray(N);

M=input('Введите M -- число элементов массива M: ');

B=InputRealArray(M);

OutputRealArray('A',A,N);

OutputRealArray('B',B,M);

[AO NO]=CreateNewArray(A,N);

[BO NBO]=CreateNewArray(B,M);

OutputRealArray('AO',AO,NO);

OutputRealArray('BO',BO,NBO);

 

% Ввод массива из N элементов:

function X=InputRealArray(N)

for i=1:N

  disp(sprintf('элемент(%g)=',i))

  X(i)= input(' ');    

end

end

 

% Вывод массива из N элементов:

function OutputRealArray(MasName,M,N)

for i=1:N

  disp(sprintf('%s[%d]=%g',MasName,i,M(i)))  

end

end

 

% Расчет среднего арифметического

% для массива из N элементов

function Sr=CalcAverage(M,N)

if N<1

disp('Переданное число не элементов')

disp('массива не является натуральным!')

exit

end

Sr=0;

for i=1:N

Sr=Sr+M(i);   

end

Sr=Sr/N;

end

 

% Формирование нового массива:

function [MO NO]=CreateNewArray(MI,NI)

NO=0;

S = CalcAverage(MI,NI);

for i=1:NI

if MI(i)>S

    NO=NO+1;

  MO(NO)=MI(i);

end

end

end