Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задача 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
|
||||||||
Последнее изменение этой страницы: 2021-04-12; просмотров: 77; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.12.146.87 (0.179 с.) |