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

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

=s/n.
5. Передать результат Sredn в вызывающий алгоритм.

Схема алгоритма Структурированная запись вспомогательного алгоритма J_max
1. Получить от вызывающего алгоритма исходные данные матрицу Аи ее размер n , m.
2. Присвоить переменной max =Sredn(A,n,m,1).
3. Присвоить переменной J_max=1.
4. Повторять для j от 2 до m:
4.1. Присвоить переменной tek=Sredn(A,n,m, j).
4.2. Если tek> max , то запомнить tek в max, а в запомнить. Передать результат J_max в вызывающий алгоритм.

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

Программа на языке Си
#include
#include
#define N 30
#define M 50 void in_matr(double *a,int n)
{ int i; Введите Элементы матрицы for (i=0;i } double sredn(double *a,int n,int m,int j)
{ int i; double s; s=0; for (i=0;i} double min_el(double *a,int n,int m,int j)
{ int i; double min,m1; min=*(a+j); for (i=1;i { m1=*(a+i*m+j); if(m1 } return min;
} double j_max(double *a,int n,int m)
{ int j,jmax; double max,tek,*p; p=a; max=sredn(p,n,m,0); jmax=0; for(j=1;j { tek=sredn(p,n,m,j); if (tek>max)
{ max=tek;

197
jmax=j;
}
} return jmax;
} int main()
{ int n,m; double a[N][M],min; printf(" n= "); scanf("%d",&n); printf(" m= "); scanf("%d",&m); in_matr(&a[0][0],n*m); min=min_el(&a[0][0],n,m,j_max(&a[0][0],n,m)); printf("min=%6.2lf \n",min); system("pause"); return 0;
} Программа на языке Паскаль
Program Pr_27;
Type matr=array of array of real; procedure in_matr( var a:matr; n,m:byte); var i,j:byte; begin Введите элементы матрицы for i:=0 to n-1 do for j:=0 to m-1 do read(a[i,j]); end; function sredn (a:matr; n,j:byte):real; var i:byte; s:real; begin s:=0; for i:=0 to n-1 do s:=s+a[i,j]; sredn:=s/n; end; function min_el (a:matr; n,j:byte):real; var i:byte; min:real; begin min:=a[0,j]; for i:=1 to n-1 do if a[i,j]

198
min_el:=min; end; function j_max(a:matr;n,m:byte):byte; var j:byte; max,tek:real; begin max:=sredn(a,n,0); j_max:=0; for j:=0 to m-1 do begin tek:=sredn(a,n,j); if tek>max then begin max:=tek; j_max:=j end; end; end;
Var a:matr; n,m:byte; min:real; begin Введите n и m:'); readln (n,m);
SetLength(a,n,m); Введите элементы матрицы in_matr(a,n,m); min:=min_el (a,n,j_max(a,n,m)); writeln ('min=', min:6:2); end. Программа на языке Фортран
Program Pr_27 implicit none real, allocatable :: A(:,:) integer n,m,j_max real min,min_el print Введите n и m:' read*,n,m allocate (A(n,m)) print Введите элементы матрицы' call in_matr(A,n,m) min=min_el(A,n,m,j_max(A,n,m)) print *,'min=',min deallocate (A) end

199
subroutine in_matr (A,n,m) implicit none integer, intent (in)::n,m real,intent(out) :: A(n,m) integer i,j read *,((A(i,j),j=1,m),i=1,n) end real function sredn(A,n,m,j) implicit none integer, intent (in)::n,m,j real,intent(in) :: A(n,m) real s integer i s=0 do i=1,n s=s+A(i,j) enddo sredn=s/n end real function min_el(A,n,m,j) implicit none integer, intent (in)::n,m,j real,intent(in) :: A(n,m) real min integer i min=A(1,j) do i=2,n if (A(i,j)max) then max=tek j_max=j end if enddo end

Программа на языке Python
# В качестве матрицы используется стандартный
# тип list (список,
# элементами которого являются списки
# Функции ввода-вывода матриц реализованы по
# аналогии с задачей 51
# Ввод матрицы из N строк по M столбцов def InputRealMatrix(N, M):
A = [] # Создаем пустой список for i in range(0, N):
A.append([])
# Добавляем пустой список элементов й строки for j in range(0, M): Введите A[{0},{1}]: ".format(i+1,j+1))
A[i].append(float(input())) return A
# Вывод квадратной матрицы A из N строк
# по M столбцов
# MatrName - выводимое на экран имя матрицы (строка) def OutputRealMatrix(MasName,A,N,M): for i in range(0, N): for j in range(0, M): print("{0}[{1},{2}]={3:8.3} ".format(MasName, i+1,j+1,A[i][j]), sep='',end=' ') print(" ") return None
# A -- матрица из N строк, j -- номер столбца
# возвращает среднее в ом столбце
# (считая с 1 до M, где M -- число столбцов) def sredn(A, N, j):
S = 0 j = j-1
# номер столбца с 1, а индексы в списке с 0. for i in range(0, N):
S = S + A[i][j] return S/N
# A -- матрица из N строк, j -- номер столбца
# возвращает значение минимального элемента в
# ом столбце (считая с 1 до M,
# где M -- число столбцов) def min_el(A, N, j): j = j-1
# номер столбца с 1, а индексы в списке с 0. minimum = A[0][j]

201
for i in range(1, N): if A[i][j] < minimum: minimum = a[i,j] return minimum
# A -- матрица из N строк по M столбцов
# возвращает номер столбца (от 1 до M),
# среднее арифметическое элементов которого
# максимально def jmax(A, N, M): jmaxsredn = 1
# не индекса порядковый номер столбца матрицы maxsredn = sredn(A,N,jmaxsredn) for j in range(2, M+1): teksredn = sredn(A,N,j) if teksredn > maxsredn: maxsredn = teksredn jmaxsredn = j return jmaxsredn Введите число строк матрицы A: ")
Na=int(input()) Введите число столбцов матрицы A: ")
Ma=int(input())
A = InputRealMatrix(Na,Ma) Исходная матрица A:")
OutputRealMatrix("A",A,Na,Ma) minel = min_el(A,Na,jmax(A,Na,Ma)) print("min = {0:8.3}".format(minel)) Программа в системе Матлаб Введите n= '); Введите m= '); Введите элементы матрицы
A=in_matr(n,m); min=min_el(A,n,m,j_max(A,n,m)); disp(sprintf('min =%4.2f',min)) function A=in_matr(n,m) for i=1:n for j=1:m
A(i,j)= input(''); end end end function min=min_el(A,n,m,j) min=A(1,j);

202
for i=1:n if A(i,j)max max=tek; jmax=j; end end end function s=sredn(A,n,j) s=0; for i=1:n s=s+A(i,j); end s=s/n; end Задача 28. Использование вспомогательных алгоритмов. Передача функции как параметра в другую функцию. Нахождение площади между двумя кривыми Условие задачи. Найти площадь между кривыми
x
e
x
f
x
sin
3
)
(
1


и
3 2
2
)
(
2 2



x
x
x
f
на отрезке от а до b как разность интегралов




b
a
b
a
dx
x
f
dx
x
f
S
)
(
)
(
2 Из математики известно, что определенный интеграл

b
a
dx
x
f
)
(
равен площади криволинейной трапеции – фигуры, ограниченной сверху графиком положительной на отрезке [a;b] функции y=f(x), слева – прямой, справа – прямой x=b, и снизу – осью ОХ. Вычислить значение

определенного интеграла можно для любой непрерывной на отрезке
[a;b] функции. Следовательно, площадь искомой фигуры будет равна разности площадей криволинейных трапеций, ограниченных прямыми
x=a, x=b, y=0 и графиками функций f
1
(x) и f
2
(x), те. абсолютному значению разности интегралов




b
a
b
a
dx
x
f
dx
x
f
S
)
(
)
(
2 1
, что иллюстрирует рис. 1. Рис. 1 Алгоритм приближенного вычисления интеграла методом прямоугольников был подробно рассмотрен в задаче 16 пособия [1]. Интервал [a;b] разбивается на n равных отрезков, длина которых
h=(b-a)/n, и на каждом отрезке строится прямоугольник, высота которого равна значению подынтегральной функции в центре отрезка. Таким образом, площадь искомой криволинейной трапеции приближенно представляется суммой площадей полученных прямоугольников, те.










n
i
i
n
i
i
n
i
i
b
a
x
f
h
h
x
f
S
dx
x
f
1 1
1
)
(
)
(
)
(
, где x
1
=a+h/2, а остальные x
i
= x
i-1
+h. Чем больше значение n, тем точнее вычисляется интеграл.
y
O
x
f
1
(x)
f
2
(x)
a
b

В качестве подынтегральной функции может быть взята любая непрерывная на интервале [a;b] функция, вид этой функции никак не может повлиять на алгоритм. Следовательно, нет необходимости составлять алгоритм вычисления интеграла для каждой конкретной функции, достаточно имеющегося обобщенного алгоритма. Таким образом, можно сделать вывод, что данный алгоритм является вспомогательным для решения поставленной задачи. Чтобы сего помощью можно было вычислить значение определенного интеграла от конкретной функции на конкретном отрезке (a;b), эти данные ему нужно передать. Чтобы оба интеграла вычислялись с одинаковой точностью, число разбиений у них должно совпадать. Этого можно добиться двумя способами или взять некоторое фиксированное значение, или запросить его у пользователя в основной части алгоритма и передать во вспомогательный. Выберем второй вариант. Итак, входными данными для алгоритма вычисления интеграла являются подынтегральная функция f(x), пределы интегрирования a и b (вещественные числа) и число разбиений n (натуральное число. Результатом работы алгоритма будет значение интеграла – выходное данное. Входные данные будут передаваться в функцию вычисления интеграла из вызывающего алгоритма через параметры, а вычисленный результат непосредственно возвращаться в точку вызова. Структурированная запись вспомогательного алгоритма
вычисления интеграла Integral Входные данные – функция f(x), вещественные числа a и b, целое
n, результат – значение суммы s.
1. Получить от вызывающего алгоритма функцию f и значения
a, b и n.
2. Вычислить шаг интегрирования
b a
h
n


. Обнулить значение суммы и задать начальное значение
2
h
x a
 
3. Повторять n разследующие действия
3.1. Прибавить к сумме очередное слагаемое s=s+f(x).
3.2. Вычислить новое значение x= x+ h.
4. Умножить на величину h полученную сумму s=s*h.
5. Передать вызывающему алгоритму значение s.

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

Структурированная запись вспомогательного алгоритма F1 Входное данное – вещественное число х, выходное данное – значение выражения res
1. Получить от вызывающего алгоритма значение х
2. Вычислить значение
x
e
res
x
sin
3


3. Передать вызывающему алгоритму значение res. Схема алгоритма Структурированная запись вспомогательного алгоритма F2 Входное данное – вещественное число х, выходное данное – значение выражения res
1. Получить от вызывающего алгоритма значение х
2. Вычислить значение
3 2
2 2



x
x
res
3. Передать вызывающему алгоритму значение res. Схема алгоритма

Итак, определены три вспомогательных алгоритма алгоритм вычисления интеграла и два алгоритма подынтегральных функций. Теперь нужно составить основной алгоритм, который, используя вспомогательные алгоритмы, будет решать поставленную задачу. Входными данными для него будут координаты концов отрезка a и b и число разбиений отрезка па результатом – искомая площадь S. Значения и b вводятся с клавиатуры, после этого можно вычислить значения интегралов от функций f
1
(x) и f
2
(x) и найти их разность по модулю. Полученное число и будет искомым значением площади. Чтобы использовать вспомогательный алгоритм, к нему нужно обратиться по имени, указав в скобках значения необходимых ему входных данных, в данном случае – имя подынтегральной функции, значения координат концов отрезка [a;b] и число разбиений n. Например, обращение Integral (F1, 1, 3, 100) приведет к тому, что начнет выполняться вспомогательный алгоритм с именем Integral и обозначения, используемые в нем, будут применяться к данным, указанным в скобках станет обозначать вспомогательный алгоритм F1, a – число 1,
b – число 3, а n – число 100. Соответственно использованное в алгоритме обращение f(x) будет тождественно обращению F1(x). Структурированная запись основного алгоритма
1. Ввести a, b и n
2. Вычислить S = | Integral (F1, a, b, n) - Integral (F2, a, b, n) |
3. Вывести S Схема алгоритма

Программа на языке Си
#include
#include double f1 (double); double f2 (double); double integral (double (*)(double), double, double, unsigned); int main (void)
{ double a, b, s; unsigned n; printf (Введите значения a и b\n”); scanf (״%lf%lf”, &a, &b); printf (Введите число разбиений интервала scanf (״%u”, &n); s = fabs(integral(f1,a,b,n)-integral(f2,a,b,n)); printf(״S = %lf”, s); return 0:
} double f1 (double x)
{ return sqrt(exp(x))+3*sin(x);
} double f2 (double x)
{ return x*x/2-2*x+3
} double integral (double (*f)(double), double a, double b, unsigned n)
{ double s=0, h, x; h = (b-a)/n; for (x = a+h/2; n>0; --n, x += h) s += f(x); s *= h; return s;
} Программа на языке Паскаль
Program Main_28;
Type
Func = function (real): real;
Var a, b, S : real; n : integer;

209
function F1(x:real):real; far; begin
F1 := sqrt(exp(x))+3*sin(x) end; function F2(x:real):real; far; begin
F2 := x*x/2-2*x+3 end; function Integral (f: Func; a, b: real, n: integer):real; far; var i : integer;
S, h, x : real; begin h := (b-a)/n;
S := 0; x := a+h/2; for i:=1 to n do begin
S := S+f(x); x := x+h end;
S := S*h;
Integral := S end;
BEGIN writeln (Введите значения a и b'); readln (a, b); writeln (Введите число разбиений read (n);
S := abs(Integral(F1,a,b,n)-Integral(F2,a,b,n)); writeln ('S = ', S:8:3)
END. Программа на языке Фортран
Program Main_28
Implicit none real a, b, S, Integral integer n real,external :: F1, F2 print Введите значения a и b' read *, a, b print *, 'Введите число разбиений' read *, n
S = abs(Integral(F1,a,b,n)-Integral(F2,a,b,n)) print *, 'S = ', S end

210
real function F1(x) real, intent(in) :: x
F1 = sqrt(exp(x))+3*sin(x) end real function F2(x:real):real; far; real, intent(in) :: x
F2 = x*x/2-2*x+3 end real function Integral (f, a, b, n) real, intent(in) :: a, b integer, intent(in) :: n real f integer i real S, h, x h = (b-a)/n
S = 0 x := a+h/2 do i=1, n
S = S+f(x) x = x+h enddo
S = S*h
Integral = S end Программа на языке Python
from math import sqrt, exp, sin def integral(f, a, b, n): h=(b-a)/n; s=0; x=a+h/2 for i in range(n): s+=f(x) x+=h s*=h return s def f1(x): res=sqrt(exp(x))+3*sin(x) return res def f2(x): res=x*x/2-2*x+3 return res Введите значение a:")) Введите значение b:")) Введите число разбиений интервала) s=abs(integral(f1,a,b,n)-integral(f2,a,b,n)) print("S=", s)

Программа в системе Матлаб Вариант с передачей имени функции как строкового данного Введите a='); Введите b='); Введите число разбиений n='); s=abs(Integral('f1',a,b,n)-Integral('f2',a,b,n)); disp(sprintf('s=%f',s)); function f=f1(x); f=sqrt(exp(x))+3*sin(x); end function f=f2(x); f=x^2/2-2*x+3; end function s=Integral(f,a,b,n);
% Имя функции f передается как строковое данное h=(b-a)/n; s=0; x=a+h/2; for i=1:n s=s+feval(f,x); x=x+h; end s=s*h; end Вариант с передачей указателя на функцию Введите a='); Введите b='); Введите число разбиений n='); f1=@(x)sqrt(exp(x))+3*sin(x); f2=@(x)x^2/2-2*x+3; s=abs(Integral(f1,a,b,n)-Integral(f2,a,b,n)); disp(sprintf('s=%f',s)); function s=Integral(f,a,b,n); h=(b-a)/n; s=0; x=a+h/2; for i=1:n s=s+f(x); x=x+h; end s=s*h; end

Библиографический список
1. Типовые алгоритмы и их программирование учебное пособие / АН. Гущин и др под. ред. ИК. Раковой Балт. гос. техн. унт. СПб., 2016.
2. ЕСПД. ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. М,
2010.
3. Кнут Д Искусство программирования. Т. Основные алгоритмы. М, 2006.
4. Керниган Б Ритчи Д. Язык программирования Спер. с англ. М, 2013.
5. Алексеев ЕР Чеснокова О.В., Кучер Т.В. Free Pascal и Lazarus: учебник по программированию. М, 2010.
6. Бартеньев О.В. Современный Фортран. М, 2000.
7. Саммерфильд М Программирование на Python 3. Подробное руководство перс англ. СПб., 2009.
8. Алексеев ЕР, Чеснокова О.В. MATLAB 7. МОГЛА В ЛЕНИ Е ОСНОВНЫЕ АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ ..................................... 3 Одномерные массивы ................................................................................................. 3 Задача 1. Нахождение среднего арифметического элементов массива ............ 5 Задача 2. Нахождение среднего арифметического элементов, удовлетворяющих условию ............................................................................ 9 Задача 3. Проверка наличия определенных элементов в массиве ................... 16 Задача 4. Вычисление значения полинома ........................................................ 21 Задача 5. Поиск максимального элемента в массиве ........................................ 25 Задача 6. Поиск минимума в массиве и его перестановка ............................... 29 Задача 7. Поиск минимального из элементов, удовлетворяющих условию ... 35 Задача 8. Удаление максимального элемента из массива ................................ 41 Задача 9. Вставка элемента в массив ................................................................. 47 Задача 10. Формирование нового массива на основе исходного ..................... 52 Задача 11. Перебор всех пар элементов в массиве. Вложенные циклы ......... 58 Задача 12. Сортировка массива методом попарно-обменных перестановок . 63 Задача 13. Сортировка массива методом поиска максимума .......................... 75 Многомерные массивы. Матрицы ......................................................................... 80 Задача 14. Вычисление среднего арифметического в строках матрицы ........ 83 Задача 15. Поиск максимального по модулю элемента в столбцах матрицы ........................................................................................................... 88 Задача 16. Преобразование строки и столбца, где находится минимум матрицы ........................................................................................................... 93 Задача 17. Перестановка столбцов матрицы ................................................... 100 Задача 18. Работа с элементами главной диагонали квадратной матрицы ... 108 Задача 19. Проверка элементов в части матрицы, ограниченной диагональю Задача 20. Поиск упорядоченных по возрастанию строк матрицы ............... 118 Задача 21. Обработка трехмерного массива .................................................... 125 ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ ............................................................... 131 Задача 22. Использование вспомогательных алгоритмов. Поиск минимального из двух значений .......................................................................... 134 Задача 23. Использование вспомогательных алгоритмов. Поиск минимальных элементов двух массивов ............................................................. 140 Задача 24. Использование вспомогательных алгоритмов. Обработка массива по частям ......................................................................................... 151 Задача 25. Вспомогательные алгоритмы. Обработка двух массивов с получением новых массивов ....................................................................... 159 Задача 26. Вспомогательные алгоритмы. Работа с диагоналями двух квадратных матриц ....................................................................................... 174 Задача 27. Использование вспомогательных алгоритмов. Обработка отдельных столбцов матрицы ...................................................................... 188 Задача 28. Использование вспомогательных алгоритмов. Передача функции как параметра в другую функцию. Нахождение площади между двумя кривыми. 202 Библиографический список .................................................................................... 212

Гущин Артем Николаевич, Лазарева Татьяна Ильинична,
Мартынова Ирина Владимировна, Палехова Ольга Александровна,
Ракова Ирина Константиновна
Алгоритмы обработки массивов и вспомогательные алгоритмы Редактор ГМ. Звягина Корректор Л.А. Петрова Компьютерная верстка СВ. Кашуба Подписано в печать 15.11.2016. Формат х. Бумага документная. Печать трафаретная. Усл. печ. л. 12,2. Тираж 500 экз. Заказ № 186. Балтийский государственный технический университет Типография БГТУ
190005, С.-Петербург, я Красноармейская ул, д