Типовые алгоритмы Ч2. Аа нн

• Название: Аа нн
• Дата: 13.10.2019
• Размер: 1.6 Mb.
• Имя файла: Типовые алгоритмы Ч2.pdf
• Тип: Документы; #89897
• страница: 6 из 8

Структурированная запись алгоритма 22.1
1. Получить от вызывающего алгоритма значения переменных a и b.
2. Если a < b, то min = a, иначе min = b.
3. Передать вызывающему алгоритму значение переменной min.

Схема алгоритма 22.1 Для того чтобы с помощью этого алгоритма найти минимум для разных пар данных, воспользуемся алгоритмической конструкцией обращение к ранее определенному поименованному алгоритму, при этом будем при каждом обращении передавать на вход алгоритма соответствующие значения. Алгоритмы, возвращающие некоторое конкретное значение непосредственно в точку обращения к ним, часто называют алгоритмами функций Данные, передаваемые из вызывающего алгоритма к ранее определенному, называют аргументами или параметрами алгоритма, возвращаемые (для алгоритмов функций результатом работы алгоритма. Для определенности будем считать, что порядок перечисления аргументов при определении поименованного алгоритма и при обращении к нему совпадает первое значение при обращении будет соответствовать первому значению при определении алгоритма. Для дальнейшего сокращения записи обращений к алгоритму функции (и приближения к математической форме записи, а также к форме, принятой во многих языках программирования, будем обозначать такое обращение как имя_алгоритма(передаваемый_аргумент1,
передаваемый_аргумент2, …). При этом использование такого обращения в выражении означает использование в данном выражении значения, возвращаемого алгоритмом-функцией. Например,
var1 = alg1(arg1, arg2) будет означать присвоить переменной var1 результат, возвращаемый алгоритмом alg1, если ему в качестве первого аргумента было передано значение переменной arg1, а в качестве второго – значение переменной arg2. С использованием данных обозначений запишем алгоритм решения поставленной задачи:
Структурированная запись алгоритма 22.2
1. Ввести значение переменных a, b, c.
2. F= min2(a, b)/(2*min2(a/2, c/b)) + min2(min2(a,b),c) /min2(a+b,2*c).
3. Вывести сообщение «F =» и значение переменной F. Следует обратить внимание, что в п. 2 алгоритма 22.2 использовалась сокращенная запись обращения к алгоритму min2, аналогичная обращению к таким математическим функциям как sin(x) или arctg(x). Представим схему данного алгоритма по ГОСТ 19.701. Схема алгоритма 22.2 Программа на языке Си
#include
#include

138
double min2(double, double); int main(int argc, char *argv[]) { double a, b, c, F; Введите a:"); scanf("%lf",&a); Введите b:"); scanf("%lf",&b); Введите c:"); scanf("%lf",&c);
F=min2(a, b)/(2*min2(a/2, c/b))+min2(min2(a,b),c)
/min2(a+b,2*c); printf("F = %lg",F); system("pause"); return 0;
} double min2(double a, double b)
{ double min; if( a < b ) min = a; else min = b; return min;
} Программа на языке Паскаль
Program main_22;
Function Min2(a, b: real): real; begin if aVar a, b, c, F: real; begin Введите a, b и с readln(a,b,c);
F:=min2(a,b)/(2*min2(a/2,c/b))+min2(min2(a,b),c)/ min2(a+b,2*c); writeln('F=', F:5:2); end. Программа на языке Фортран
Program main_22
Implicit none real min2,F,a,b,c Введите a' read*,a

139
Введите b' read*,b Введите c' read*,c
F=min2(a,b)/(2*min2(a/2,c/b))+min2(min2(a,b),c) &
/min2(a+b,2*c) print '(A,F5.3)',' F=',F end real function min2(a,b)
Implicit none real,intent(in)::a,b real min if (a
# Возврат меньшего из двух значений def min2(a, b): if a < b: min = a else: min = b return min Введите a:") a=float(input()) Введите b:") b=float(input()) Введите c:") c=float(input())
F=min2(a, b)/(2*min2(a/2, c/b))+min2(min2(a,b),c)/ min2(a+b,2*c) print("F = ",end=' ') print(F) Программа в системе Матлаб введите a='); введите b='); введите c=');
F=min2(a,b)/(2*min2(a/2,c/b))+min2(min2(a,b),c)/… min2(a+b,2*c); disp(sprintf('F=%5.3f',F))

140
function min=min2(a,b) if aInmas является ввод с клавиатуры значений элементов любого массива. Входной параметру этого алгоритма
 размер массива n. Выходным параметром является массив, назовем его Х. Это имя может быть любыми совпадать с именем массива в главном алгоритме. Все формальные параметры локальны, те. доступны только внутри вспомогательного

алгоритма. В нём описываются действия, которые позволят сформировать элементов массива Х. Задачей вспомогательного алгоритма вывода элементов массива
Outmas является вывод на экран значений элементов любого массива. У этого алгоритма будут только входные параметры массив Хи размер массива n. Выходных параметров у вспомогательного алгоритма
Outmas не будет, так как новых значений в процессе работы алгоритма никакие переменные не получают. В этом алгоритме описываются действия, которые позволят вывести на экран n элементов массива X. Вводи вывод элементов массива, как правило, осуществляется в цикле, но это зависит от конкретной реализации языка программирования. Рассмотрим вспомогательный алгоритм нахождения значениями- нимального элемента в некотором массиве Min_el. Формальными параметрами в этом вспомогательном алгоритме являются входные – некоторый массив Хи количество элементов этого массива n, выходной параметр – значение наименьшего элемента массива minx. Алгоритм поиска наименьшего элемента массива нам известен. В переменную
minx поместим первый элемент массива Х Далее в цикле i=2,
n, начиная со второго элемента массива до последнего, будем последовательно сравнивать каждый элемент массива с содержимым ячейки
minx. Если очередной элемент массива Х окажется меньше, чем значение, тов переменную minx запишем элемент Х Х Далее проверим следующий элемент массива. Так будет продолжаться
n-1 раз, пока все элементы массива не будут проверены. В результате в ячейке minx окажетсязначение наименьшего элемента массива. В вызывающем алгоритме main введём размер массива и последовательно вызовем необходимые вспомогательные алгоритмы, далее вычислим разность минимальных элементов и результат выведем на экран. Сначала с клавиатуры введем количество элементов массива n, затем последовательно происходит обращение к вспомогательным алгоритмам. При вызове вспомогательного алгоритма в него передаются входные данные, по завершении из него в вызывающий алгоритм возвращаются выходные данные. Механизм передачи параметров описан выше, в разных языках он может различаться для входных и выходных данных. Но упрощенно можно себе представить, что при вызове вспомогательного алгоритма формальные параметры заменятся на фактические и все действия в нём будут производиться с полученными от главного алгоритма данными.
При обращении к процедуре ввода массива c фактическими параметрами А алгоритм будет заполнять массив А из n элементов. Затем производится обращение к тому же алгоритму ввода массива с фактическими параметрами В для заполнения массива B из n элементов Далее дважды вызовем алгоритм нахождения минимальных элементов первый разв массиве А, второй – в массиве В. Входные формальные параметры алгоритма Min_el –массивХ, количество элементов результат минимальный элемент. Когда алгоритм Min_el вызывается для первого массива А входными фактическими параметрами будут переменные А результатом
 а значение минимального элемента массива А. Для второго массива В входные фактические параметры
 это B, а результатом будет minb – значение минимального элемента массива В. Затем в переменной Res вычислим разность минимальных элементов массивов mina и minb соответственно и полученное значение выводится на экран. Структурированная запись вспомогательного алгоритма Inmas Входной параметр – размер массива n, выходной
 заполненный массив Х
1. Начало цикла С для i=1,n.
1.1. Ввод элементов массива. Конец цикла C1. Структурированная запись вспомогательного алгоритма Outmas Входные параметры массив X и размер массива n;
1. Начало цикла С для i=1,n
1.1. Вывод элементов массива. Конец цикла C1. Схемы алгоритмов Inmas и Outmas

Структурированная запись вспомогательного алгоритма Min_el Входные параметры размер массива n и массив Х, выходной параметр
 наименьший элемент массива minx.
1. В переменную minx записывается первый элемент массива Х
2. Начало цикла i =2, n .
2.1. Проверка условия Х :
2.1.1. Если условие выполняется, тов переменную minx записывается этот элемент массива Х. Конец цикла по i. Схема алгоритма

Структурированная запись главного алгоритма
1. Ввод с клавиатуры размера массивов n.
2. Обращение к алгоритму Inmas для ввода массива A: Inmas (A,n).
3. Обращение к алгоритму Inmas для ввода массива B: Inmas (B,n).
4. Обращение к алгоритму Outmas для вывода массива A: Outmas
(A,n).
5. Обращение к алгоритму Outmas для вывода массива B: Outmas
(B,n).
6. Обращение к алгоритму Min_el для нахождения минимального элемента массива A: mina = Min_el (A,n).
7. Обращение к алгоритму Min_el для нахождения минимального элемента массива b: minb = Min_el (B,n).

145 8. Вычисление разности минимальных элементов массивов
Res=mina-minb.
9. Вывод на экран значения Res. Схема алгоритма
1

Программа на языке Си
#include
#define N 30 void inmas(double *a,int n); double min_el(double *a,int n); void outmas(double *a,int n); void main()
{ int n; double mina,minb,a[N],b[N],res; printf("n="); scanf("%d",&n); Введите элементы массива A\n"); inmas(a,n); printf("\n Введите элементы массива B\n"); inmas(b,n); printf("Мвссив A\n"); outmas(a,n); Массив B\n"); outmas(b,n); mina=min_el(a,n); minb=min_el(b,n); res=mina-minb; printf("\n res= %5.2lf\n",res);
} void inmas(double *x,int n)
{ int i; for (i=0;i1

147
scanf("%lf",x+i);
} void outmas(double *x,int n)
{ int i; for (i=0;i} double min_el(double *x,int n)
{ int i;double min; min=*x; for (i=1;i} Программа на языке Паскаль
Program main_23;
Type
Mas = array[1..30] of real;
Var a,b: mas; n: integer; res: real; function minel(x:mas; n:integer):real; var i:integer; minx:real; begin minx:=x[1]; for i:=2 to n do if x[i]

148
writeln; end; begin writeln (Введите n '); readln(n); Введите массив a'); inmas(a,n); Введите массив b'); inmas(b,n); writeln(' Массив a'); outmas(a,n); writeln(' Массив b'); outmas(b,n); res:=minel(a,na) - minel(b,nb); Разность минимумов = ',res:4:1); end. Программа на языке Фортран
Program main_23 implicit none real minel,res real, allocatable :: a(:), b(:) integer i, j, n print *,' Введите n' read *, n allocate (a(n), b(n)) print*,' Введите массив a' call inmas(a,n) print*,' Введите массив b' call inmas(b,n) print*,' Массив a' call outmas(a,n) print*,' Массив b' call outmas(b,n) res= minel(a,n)- minel(b,n) print'(A,F4.1)', 'Разность минимумов =',res deallocate(a,b) end real function minel(x, n) implicit none integer, intent(in):: n real, intent(in) :: x(n) integer i real minx minx=x(1) do i=2,n if (x(i)

149
enddo minel=minx end function minel subroutine inmas(x,n) implicit none integer, intent(in) :: n real, intent(out) :: x(n) read *, x end subroutine inmas subroutine outmas(x,n) implicit none integer,intent(in) :: n real,intent(in) :: x(n) print '((F3.1,2x))',x end subroutine outmas Программа на языке Python
# Ввод массива из n элементов def Inmas(n):
A = [] # Создаем пустой список for i in range(1,n+1): Введите й элемент : ".format(i))
A.append(float(input())) return A
# Вывод массива из N элементов def Outmas(MasName,M,N): for i in range(1,N+1): print("{0}[{1}]={2} ".format(MasName,i,M[i-1])) return None
# Поиск значения наименьшего элемента
# массива x из nx элементов def Min_el(x, nx): minx = x[0] for i in range(1, nx): if x[i] < minx: minx = x[i] return minx
# Главная программа Введите n -- размер массивов A и B: ") n=int(input()) Введите массив A:")
A=Inmas(n)

Введите массив B:")
B=Inmas(n) Введенный массив A:")
Outmas("B",B,n) Введенный массив B:")
Outmas("B",B,n) mina = Min_el(A, n) minb = Min_el(B, n)
Res = mina - minb Разность минимумов = {0}".format(Res)) Программа в системе Матлаб
% Главная программа введите n='); введите массив A')
A=Inmas(n) введите массив B')
B=Inmas(n) disp(' Массив A') disp(A) disp(' Массив B') disp(B)
% В системе Матлаб для данной задачи оформление
% вывода массива в виде функции нецелесообразно. mina=Min_el(A,n); minb=Min_el(B,n); res=mina-minb; disp(sprintf('res=%4.3f',res))
% Функция ввода массива function X=Inmas(n) for i=1:n элемент)
X(i)= input(' '); end end
% Функция нахождения минимального элемента function minx=Min_el(X,n) minx=X(1); for i=2:n if X(i)< minx minx=X(i); end end

Задача 24. Использование вспомогательных алгоритмов. Обработка массива по частям Условие задачи Дан одномерный массив А, количество элементов в котором четно. Найти отношение суммы элементов первой половины массива к сумме элементов второй половины.
Исходным данным в данной задаче является одномерный массив А, содержащий четное число элементов. В математике четное число выражается как 2n, где n – любое натуральное число, которое для данной задачи будет являться половиной количества элементов массива. Поскольку требуется использовать четное количество элементов, то удобно вводить число n и формировать массив из 2n элементов. Ввод элементов массива будем выполнять во вспомогательном алгоритме Inmas, описание которого приведено в рассмотренной выше задаче 23. Результатом решения задачи будет одно число, назовем его otn. При решении задачи сначала требуется найти сумму элементов впервой половине массива, затем сумму элементов во второй половине. Поделив первый результат на второй, получим искомое значение. Поскольку необходимо дважды выполнять одинаковые действия с разными элементами массива, то имеет смысл описать эти действия один раз во вспомогательном алгоритме (вызываемом, а в главном вызывающем) обращаться к нему дважды с разными исходными данными. Во вспомогательном алгоритме, назовем его Sum, будем вычислять сумму элементов массива с номерами от n1 до n2. Она и будет результатом работы этого алгоритма. Сего помощью можно найти сумму элементов в любой части массива. Алгоритму Sum для вычисления нужны исходные данные массив А а также значения индексов элементов n1 и n2, которые он должен получить из вызывающего алгоритма. Для получения суммы воспользуемся ранее описанным методом. Сначала полагаем сумму равной нулю s=0. Далее в цикле для i от n1 до n2 последовательно прибавим к ней по одному элементу массива А. Для повторения этого действия используем арифметический цикл, так как число повторений известно. Полученная сумма будет результатом работы этого вспомогательного алгоритма и должна быть возвращена в главный алгоритм средствами выбранного языка. Алгоритмы, возвращающие одно значение, в языках программирования называются функциями.

В главном алгоритме будет вводиться число n, равное половине всего количества элементов массива. Для получения полного количества элементов это число надо умножить на два и сохранить в переменной Далее вызовем вспомогательный алгоритм In_mas для ввода массива, при этом ему необходимо передать полное число элементов Результатом работы этого алгоритма будет массив А длиной Затем дважды вызовем вспомогательный алгоритм Sum ивы- ведем результат. Первый раз обращение к Sum необходимо для нахождения суммы элементов из первой половины массива, для этого в качестве границ номеров элементов укажем 1 и n, второй раз для нахождения суммы элементов из второй половины массива укажем номера n+1 и n2. Структурированная запись главного алгоритма
1. Ввести с клавиатуры число n.
2. Вычислить n2=2* n.
3. Ввести n2 элементов массива А, обратившись к вспомогательному алгоритму Inmas.
4. Перейти к вспомогательному алгоритму Sum с исходными данными массив Аи номерами элементов 1, n. Перейти к вспомогательному алгоритму Sum с исходными данными массив Аи номерами элементов n+1; 2n. Разделить результат, полученный из алгоритма на результат, полученный из алгоритма
Sum(A,n+1,n2) и поместить его в переменную otn.
5. Вывести на экран сообщение Отношение суммы элементов первой половины массива к сумме элементов второй половины =” и результат otn. Схема алгоритма

Структурированная запись алгоритма Sum
1. Получить от вызывающего алгоритма исходные данные массив Аи границы суммирования n1 и n2.
2. Обнулить S.
3. Повторять для i от n1 до n2:
3.1 S=S+ А.
4. Передать результат S в вызывающий алгоритм. Схема алгоритма
1 1

Программа на языке Си
#include
#define N 60 void inmas(double *a,int n)
{ int i; for (i=0;i} double sum(double *a,int n1,int n2)
{ int i;double s=0; for (i=n1;i<=n2;i++) s+=*(a+i); return s;
} int main()
{ int i,n,n2; double a[N],otn; printf(" n= "); scanf("%d",&n); printf("\n"); n2=2*n; Введите 2*n элементов
1 1

155
inmas(a,n2); otn=sum(a,0,n-1)/sum(a,n,n2-1); Отношение суммы элементов первой половины массива к сумме элементов второй половины =%6.2f\n",otn); return 0;
} Так как язык Си позволяет передавать во вспомогательный алгоритм адрес любого элемента массива и работать счастью массива, начинающейся с указанного элемента, то при реализации программы на Си целесообразно по-другому организовать передачу исходных данных во вспомогательный алгоритм при первом вызове алгоритма
sum передавать в него адрес первого элемента первой половины массива аи размер половины массива n, а при втором
 адрес первого элемента второй половины массива &a[n] и n.
#include
#define N 60 void inmas(double *a,int n)
{ int i; for (i=0;i} double sum(double *a,int n)
{ int i;double s=0; for (i=0;i} int main()
{ int i,n,n2; double a[N],otn; printf(" n= "); scanf("%d",&n); printf("\n"); Введите 2*n элементов inmas(a,2*n); otn=sum(a,n)/sum(&a[n],n); printf (Отношение суммы элементов \ первой половины массива к сумме элементов \ второй половины =%6.2f\n",otn); return 0;
}

Программа на языке Паскаль
program z_24; uses crt; type mas=array of real; procedure inmas( var a:mas;n:byte); var i:byte; begin for i:=0 to n-1 do readln(a[i]); end; function sum (a:mas; n1,n2:byte):real; var i:byte; s:real; begin s:=0; for i:=n1 to n2 do s:=s+a[i]; sum:=s; end; var a:mas; n, n2:byte; otn:real; begin writeln (' n= '); readln (n); n2:=2*n;
SetLength (a, n2);
Writeln (' Введите 2*n элементов '); inmas (a, n2); otn:= sum (a,0,n-1) / sum (a,n, n2-1); write (' Отношение суммы элементов первой ' ); write (' половины массива к сумме элементов '); writeln (' второй половины = ', otn:6:2); a:=nil; end. Программа на языке Фортран
real function sum (a,n,n1,n2) implicit none integer, intent(in) :: n,n1,n2 real, intent(in) :: a(n) real s integer i s=0

157
do i=n1,n2 s=s+a(i) enddo sum=s end
Program z_24
Implicit none real,allocatable :: a(:) real sum,otn,s1,s2 integer i,n,n2 print *,' n= ' read *,n n2=2*n allocate (a(n2)) print *,' Введите 2*n элементов' read *,a otn = sum(a,n2,1,n)/ sum(a,n2,n+1,n2) print *,' Отношение суммы элементов ', &
' первой половины массива к сумме ',&
' элементов второй половины = ', otn deallocate (a) end Программа на языке Python
# В качестве массива используется стандартный тип
# list (список)
# Ввод массива из n элементов def Inmas(n):
A = [] # Создаем пустой список for i in range(1,n+1): Введите й элемент массива ". format(i))
A.append(float(input())) return A
# Возвращает значение суммы элементов массива B
# с порядковыми номерами от n1 до n2
# (индексы элементов списка от n1-1 до n2-1) def Sum(B, n1, n2):
S = 0 for i in range(n1-1, n2):
S += B[i] # S = S + B[i] return S n = 0

158
while n < 1: Введите натуральное n",
"в массиве A будет 2*n элементов ") n=int(input())
A=Inmas(2*n) s1 = Sum(A,1,n) s2 = Sum(A,n + 1, 2*n) ot = s1/s2 Отношение суммы элементов первой) половины массива к сумме элементов) второй половины = {0:4.2}".format(ot)) Программа в системе Матлаб Введите n= '); Введите 2*n элементов массива
A=inmas(2*n); otn =summ(A,1,n)/ summ(A,n+1,2*n); отношение суммы элементов первой) половины массива к сумме элементов) второй половины =%4.2f',otn)) function a=inmas(n) for i=1:n disp(sprintf('a(%g)=',i)) a(i)= input(''); end function s=summ(a,n1,n2) s=0; for i=n1:n2 s=s+a(i); end С использованием матричных операций и функций Введи n= '); Введи 2*n элементов массива
A=inmas(2*n); otn=sum(A(1:n))/sum(A(n+1:2*n)); отношение суммы элементов первой) половины массива к сумме элементов) второй половины =%4.2f',otn)) function a=inmas(n) for i=1:n disp(sprintf('a(%g)=',i)) a(i)= input('');

159
end Задача 25. Вспомогательные алгоритмы. Обработка двух массивов с получением новых массивов Условие задачи. Даны два массива А – из N чисел, Виз М чисел. Для каждого из них сформировать массив из тех элементов, которые превышают среднее арифметическое всех чисел своего массива.
По условию задачи для каждого из двух одномерных массивов чисел производится одно и тоже действие – формирование нового массива путем отбора элементов исходного массива, удовлетворяющих некоторому критерию, а именно больших некоторого числа. При этом само число, с которым производится сравнение, также вычисляется на основе соответствующего исходного массива – как среднее арифметическое всех его элементов. Очевидно, что для решения задачи рационально использовать алгоритмическую конструкцию обращение к ранее определенному поименованному алгоритму. Возможны три способа решения задачи. Первый способ сводится к оформлению в один поименованный алгоритм последовательности из поиска среднего арифметического в исходном массиве и последующего формирования нового массива. Его аргументами (входными значениями) будет исходный массив и количество элементов в нем, результатом работы (выходными значениями) – сформированный массива также количество отобранных элементов – размер нового массива. Для второго и третьего способов расчет среднего арифметического для одномерного массива чисел оформляется как второй поименованный алгоритм, которому передается на вход массив и количество элементов в нема возвращается значение среднего арифметического элементов в массиве. Второй способ является модификацией первого, в котором для расчета среднего арифметического производится обращение к соответствующему алгоритму с передачей ему в качестве аргументов (фактических параметров) значений формальных параметров алгоритма формирования нового массива (его аргументов. В третьем способе изменяется алгоритм формирования нового массива он в качестве аргументов получает не только исходный массивно и значение, при превышении которого элемент исходного массива отбирается в результирующий массив, вычисление же данного значения происходит в вызывающем алгоритме до обращения к данному алгоритму. В рамках данной задачи нельзя однозначно определить, какой способ будет лучше, без выяснения, как именно в томили ином языке программирования осуществляется передача массивов в процедуры и функции и возврат массивов из процедур и функций, ибо общая идея декомпозиции оказывается одинаковой – выполнение одного алгоритма формирования нового массива над несколькими наборами исходных данных. Непосредственно алгоритм вычисления среднего арифметического всех элементов массива был описан в задаче 1, алгоритм формирования нового массива на основе исходного и некоторого критерия отбора – в задаче 10. На их основе, а также предполагая, что у нас имеются вспомогательные алгоритмы для ввода и для вывода значений массивов указанной размерности (описание алгоритма ввода массива приведено в задаче 23), рассмотрим второй способ. При этом для повышения наглядности сначала приведем вариант алгоритма вывода массива вещественных чисел, позволяющий явно указывать, какое имя массива должно быть выведено в строке перед значением индекса каждого элемента массива и самим значением элемента. Дадим ему номер 25.1 и имя OutputRealArray. Каждое значение отделяется от следующего как минимум пробелом или выводится на отдельной строке – определяется реализацией, в описании алгоритма укажем в качестве разделителя одиночный пробел. Структурированная запись алгоритма 25.1 Имя алгоритма OutputRealArray. Входные данные MasName – строка, содержащая имя массива, выводимое перед индексом элемента M – массив чисел N – количество элементов в массиве. На вход нельзя подавать N нецелое, меньшее 1 или большее числа элементов в массиве M. Некорректные значения N могут приводить к неожиданным результатам или аварийным ситуациям, зависящим от конкретной реализации способа доступа к элементам массива по индексу. Выходные данные отсутствуют.
1. Повторить для i от 1 до N:
1.1. Вывести имя массива MasName, символ «[», значение переменной i, символы «]=», значение M[i], пробел
2. Вернуться в точку обращения к алгоритму.

Теперь оформим алгоритм вычисления среднего арифметического элементов массива на основании задачи 1. Структурированная запись алгоритма 25.2 Имя алгоритма CalcAverage. Входные данные M – массив чисел N – количество элементов в массиве. На вход нельзя подавать N нецелое или меньшее 1. Выходные данные (возвращаются именем алгоритма как функцией среднее арифметическое элементов в массиве.
1. Если N < 1, то завершить работу аварийно.
2. Sr = 0.
3. Повторить для i от 1 до N:
3.1. Sr = Sr + M[i].
4. Sr = Sr / N.
5. Вернуть Sr. Схема алгоритма

Запишем алгоритм формирования нового массива с использованием алгоритма CalcAverage (25.2). Структурированная запись алгоритма 25.3 Имя алгоритма CreateNewArray. Входные данные MI – исходный массив чисел NI – количество элементов в исходном массиве. На вход нельзя подавать NI нецелое или меньшее 1. Выходные данные NO – количество элементов в сформированном массиве MO – сформированный массив.

Сформированный массив может быть пустым (NO равно 0), если все элементы исходного массива равны среднему арифметическому. Если 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. Схема алгоритма
1

Используя алгоритм CreateNewArray, запишем основной алгоритм решения задачи. Структурированная запись алгоритма 25.4
1. Ввести число элементов N массива A и сам массив A
2. Ввести число элементов M массива B и сам массив В
3. Обратиться к алгоритму CreateNewArray с входными данными A, N, результирующий массив присвоить AO, количество элементов в нем присвоить NAO
4. Обратиться к алгоритму CreateNewArray с входными данными B, M, результирующий массив присвоить BO, количество элементов в нем присвоить NBO Схема алгоритма
1

Программа на языке Си
#include
#include
/* Функция выделяет память под массив из 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 } 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){ Переданное число элементов "); массива не является натуральным exit(1);
}
Sr = 0; for(i=0; i< N; i++)
Sr += M[i];
Sr /= N; return Sr;
}
/* Формирование нового массива по предыдущему

167
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; Введите число элементов массива A: "); scanf("%d",&N);
A=InputRealArray(N); Введите число элементов массива B: "); scanf("%d",&M);

168
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_25; 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 Введите 'й элемент массива '); readln(A[i-1]); end; end;

169
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

170
if MI[i] > S then begin
NO := NO + 1;
SetLength(MO, NO);
MO[NO-1] := MI[i]; end; end; end; begin Введите N - число элементов массива A: '); readln(N);
InputRealArray(A,N); Введите 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_25
Implicit none integer N,M,NO,NBO real, allocatable :: A(:), B(:) ,AO(:),BO(:) Введите N -- число элементов массива A:' read*,N allocate (A(N)) call InputRealArray(A,N); Введите 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

171
! Ввод массива из N элементов
Subroutine InputRealArray(X,N)
Implicit none integer,intent(in) :: N real, intent(out) :: X(N) integer i do i=1,N print 'элемент' 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 Переданное число элементов' массива не является натуральным' 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)

172
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): Введите й элемент ".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)

173
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]
# Поскольку индексы сто последний на 1 меньше
# числа элементов в списке return NO, MO Введите N -- число элементов массива A: ")
N=int(input())
A=InputRealArray(N) Введите 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 -- число элементов массива A: ');
A=InputRealArray(N); Введите 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 элемент)
X(i)= input(' '); end end
% Вывод массива из N элементов function OutputRealArray(MasName,M,N)

174
for i=1:N disp(sprintf('%s[%d]=%g',MasName,i,M(i))) end end
% Расчет среднего арифметического
% для массива из N элементов function Sr=CalcAverage(M,N) if N<1 Переданное число не элементов) массива не является натуральным) 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 Задача 26. Вспомогательные алгоритмы. Работа с диагоналями двух квадратных матриц Условие задачи. Даны две квадратные матрицы. Выяснить, в какой из них сумма элементов главной и побочной диагоналей больше Поскольку по условию задачи необходимо вычислить сумму элементов главной и побочной диагоналей для двух различных квадратных матриц (возможно разной размерности) для последующего сравнения, то вычисление такой суммы для произвольной квадратной матрицы имеет смысл выделить в самостоятельный алгоритм и воспользоваться им для получения конкретных значений. Для квадратной матрицы размерностью NxN элементы главной диагонали будут иметь вид
A[1,1], A[2,2], …, A[i,i], … A[N,N] – совпадают номера строки и столбца. Аналогично для побочной диагонали A[1,N], A[2,N–1], …, A[i,N–i+1],
… A[N,1] – номера строк возрастают от 1 ка номера столбцов убывают от N до 1. Поскольку количество элементов на главной и побочной диагоналях квадратной матрицы одинаково и равно N, то для вычисления сумм этих элементов можно воспользоваться алгоритмической конструкцией цикл с предопределенным числом повторений, где в теле цикла на й итерации вычисляется сумма элементов
A[i,i]+A[i,N – i+1] главной и побочной диагоналей, принадлежащих к одной строке, и уже она используется для вычисления общей суммы. Обозначив интересующую сумму как S, получим
S = (A[1,1] + A[1,N]) + (A[2,2] + A[2,N–1]) +…+ (A[i,i] + A[i,N–i+1]) +…
+ (A[N,N] + A[N,1]). Следует отметить, что при нечетном N элемент, расположенный на пересечении главной и побочной диагоналей, будет учтен дважды, что не соответствует условию сумма элементов главной и побочной диагонали (и соответствовало бы условию сумма суммы элементов главной диагонали и суммы элементов побочной диагонали. Поэтому если N нечетное (N mod 2 = 1), то после окончания подсчета суммы необходимо вычесть из неё значение центрального элемента
A[N div 2 + 1, N div 2 + 1], где с помощью записи «a div b» показана операция результат целочисленного деления a на b». Тогда алгоритм вычисления суммы элементов главной и побочной диагоналей квадратной матрицы A размерностью NxN можно будет записать следующим образом.