Типовые алгоритмы Ч2. Аа нн
 Скачать 1.6 Mb.
|
|
Структурированная запись алгоритма 20 1. Ввести размеры матрицы N и M и элементы самой матрицы А. 2. Обнулить счётчик КВ цикле для каждой строки i=1,N повторять 3.1. Присвоить начальное значение истина переменной f. 3.2. В цикле для j=1,M-1 повторять 3.2.1. Сравнивать соседние элементы, и если A[i,j] A[i,j+1], то переменная f меняет своё значение на ложь и цикл прерывается. 3.3. По окончании цикла проверить если f имеет значение истина, то К=К+1. 4. Вывести К. Схема алгоритма 1 120 121 1 Программа на языке Си #include #include #define N 25 int main (void) { int n,m,i,j,k,f; double a[N][N]; printf (Введите n и m\n"); scanf ("%d%d", &n,&m); for (i=0; i { f=0;break; } if (f) k++; } printf ("Кол-во упорядоченных строк - %d",k); return 0; } Программа на языке Паскаль Program Pr_20; Var A: array of array of real; N, M, i, j, K: integer; f: boolean; begin writeln(’ Введите размеры матрицы ’); readln(N,M); SetLengh(A,N,M); N:=N-1; M:=M-1; for i:=0 to N do begin Введите элементы ’,i,’ строки for j:=0 to M do 123 read(A[i,j]); end; K:=0; for i:=0 to N do begin f:=true; for j:=0 to M-1 do if A[i,j]>=A[i,j+1] then begin f:=false; break end; if f then K:=K+1 end; writeln(’Кол-во упорядоченных строк - ’,K); A:=nil; end. Программа на языке Фортран Program Pr_20 Implicit none real, allocatable :: A(:,:) integer N, M, i, j, K logical f print *,’ Введите размеры матрицы read *, N,M allocate(A(N,M)) do i=1,N print *, Введите элементы ’,i,’ строки) read(A(i,j),j=1,M) enddo K=0 do i=1, N f=.true. do j=1, M-1 if (A(i,j)>=A(i,j+1)) then f=.false. exit endif enddo if (f) K=K+1 enddo print *, ’Кол-во упорядоченных строк - ’,K deallocate(A) end Программа на языке Python # В качестве матрицы используется стандартный тип # list (список, элементами которого являются списки Введите N -- число строк матрицы A: ") N=int(input()) Введите M -- число столбцов матрицы A: ") M=int(input()) A = [] # Создаем пустой список строк # в Python списки индексируются с 0: 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())) K = 0 for i in range(0, N): f = True for j in range(0, M-1): if A[i][j] >= A[i][j+1]: f = False break if f: K += 1 # K = K + 1 Количество строк, строго, end=' ') упорядоченных по' ') возрастанию - {0}".format(K)) Программа в системе Матлаб Введите N='); Введите M='); for i=1:N Введите эл. %d строки матрицы) for j=1:M A(i,j)=input('A(i,j)='); end end K=0; for i=1:N f=true; for j=1:M-1 if A(i,j)>=A(i,j+1) f=false; break; end end if f K=K+1; end end disp(sprintf('Кол-во упорядоченных строк - %d',K)) Задача 21. Обработка трехмерного массива Условие задачи. Трехмерный массив описывает школьный журнал одного класса. Каждая страница журнала содержит оценки N учеников за М уроков по одному предмету (в каждой строке – оценки одного ученика, в каждой колонке – оценки за один урок. В журнале L страниц – по количеству изучаемых школьниками предметов. Пусть N=25, M=40, L=15. Определить общую среднюю оценку ученика Х по всем предметам. Чаще всего в задачах используются одномерные и двумерные массивы. Но могут существовать трёхмерные и более. Одномерный массив можно представить как столбец или строку данных, двумерный как таблицу данных. Трёхмерный массив можно представлять как куб (точнее говоря, параллелепипед, массивы большей размерности представить в уме сложнее – как массив из массивов, но тем не менее их можно описывать и использовать в программах. В данной задаче предполагается использование трёхмерного массива. Каждая страница журнала является по сути двумерным массивом размера N*M, состоящим из оценок (чисел от 2 до 5). Таких страниц в журнале – L. В результате весь журнал описывается как массив из L страниц – матриц N*M, и получается структура трёхмерного массива размера L*N*M. Для обращения к элементу такого массива потребуется указать три индекса, а для обхода всех элементов массива например, ввода) надо использовать три вложенных цикла. Исходным данным в этой задаче является трёхмерный массив А, описывающий школьный журнал с оценками. Элемент А, i, j] соответствует оценке ученика i за урок j на странице p (те. по предмету p). Будем считать, что элемент А, i, j], равный нулю, означает отсутствие оценки ученика заданный урок. Ввод всех элементов массива такого размера с клавиатуры – довольно трудоёмкий процесс, реально такое количество данных целесообразно было бы вводить из файла, но ввод данных из файла в данном пособии не рассматривается. Ещё одним исходным данным является номер ученика Х, для которого требуется определить среднюю оценку. В задаче для нахождения общей средней оценки одного ученика по всем предметам потребуется найти сумму S и количество K всех ненулевых оценок ученика Х, которые находятся на всех страницах журнала в строках с номером Х. Для этого после ввода исходных данных и обнуления переменных S и К необходимо на каждой странице, изменяя её номер p от 1 до L, проверять каждую оценку в строке Х номера оценок в строке будут изменяться в цикле от 1 до Ми все ненулевые значения прибавлять к сумме S, а к их количеству К прибавлять по 1. Для просмотра всех необходимых данных потребуется два цикла по номерам страниц p и по номерам колонок в строке j. После получения общей суммы S и количества Коста тся S разделить на К и вывести результат. Структурированная запись алгоритма 21 1. Ввести исходные данные трёхмерный массив Аи номер ученика Х. 2. Присвоить начальные значения переменным S=0, K=0. 3. В цикле для каждого p от 1 до L выполнять следующие шаги 3.1. Повторять для каждого М 3.1.1. Проверять элемент массива A[p, Х, j]: если он неравен нулю, то 3.1.1.1. S=S+ A[p, Х, j] 3.1.1.2. K=K+1. 4. Если К неравно нулю, то вывести результат деления S/K, иначе вывести сообщение Оценок нет. Схема алгоритма 1 Программа на языке Си #include #define L 15 #define N 25 #define M 40 int main() { double A[L][N][M],s; int i,p,x,j,k; 1 128 printf(" Введите массив оценок for(p=0;p } Программа на языке Паскаль Program Pr_21; Const N=25; M=40; L=15; Var p, X, i, j, K, S: integer; A: array [1..L, 1..N, 1..M] of integer; begin for p:=1 to L do begin Введите оценки по предмету ', p); for i:=1 to N do begin writeln(' для ученика ', i); for j:=1 to M do read(A[p,i,j]); end; end; Введите номер ученика Х readln(X); S:=0; K:=0; for p:=1 to L do for j:=1 to M do if A[p,X,j]>0 then begin S:= S+ A[p,X,j]; K:= K+1; end; if K>0 then Средняя оценка, S/K) 129 else Оценок нет end. Программа на языке Фортран Program Pr_21 Implicit none integer, parameter :: N=25, M=40, L=15 integer p, X, i, j, K, S integer A(L, N, M) do p=1,L print *, 'Введите оценки по предмету ', p do i=1,N print *,' для ученика ', i read *, (A(p,i,j), j=1,M) enddo enddo print *, 'Введите номер ученика Х' read *, X S=0 K=0 do p=1,L do j=1,M if (A(p,X,j)>0) then S= S+ A(p,X,j) K= K+1 endif enddo enddo if (K>0) then print *, 'Средняя оценка, S/K else print *, 'Оценок нет' endif end Программа на языке Python # В качестве массива используется стандартный тип # list (список, элементами которого являются # списки, состоящие из списков L = 15 N = 25 M = 40 # Ввод трехмерного массива A A = [] # Создаем пустой список страниц for p in range(0, L): # p = 0, ... , L-1 A.append([]) # Добавляем пустой список строк й страницы 130 Введите оценки по предмету {0}". format(p+1)) for i in range(0, N): # i = 0, ... N-1 A[p].append([]) # Добавляем пустой список элементов й строки print(" для ученика {0}".format(i+1)) for j in range(0, M): # j = 0, ... M-1 print("A[{0},{1},{2}]: ". format(p+1,i+1,j+1)) A[p][i].append(int(input())) Введите номер ученика X (от 1 до {0}):". format(N)) X=int(input()) - 1 # Расчет средней оценки S = 0 K = 0 for p in range(0, L): # p = 0, ... , L-1 – L раз for j in range(0, M): # j = 0, ... M-1 – M раз if A[p][X][j] != 0: S = S + A[p][X][j] K = K + 1 if K != 0: Средняя оценка = {0}".format(S/K)) else: Оценок нет) Программа в системе Матлаб L = 15; N = 25; M = 40; for p=1:L Введите оценки по предмету ', int2str(p)]); for i=1:N disp([' для ученика ', int2str(i)]); for j=1:M A(p,i,j)=input('A='); end; end; end Введите номер ученика Х S=0; K=0; for p=1:L for j=1:M if A(p,X,j)>0 S= S+ A(p,X,j); K= K+1; end end 131 end if K>0 Средняя оценка, num2str(S/K)]); else Оценок нет) end ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ При составлении алгоритмов решения различных задач достаточно часто встречается ситуация, когда одна и та же последовательность действий (указаний, команд) используется для различных данных или же одинаковая последовательность действий над одними и теми же данными неоднократно встречается в разных частях алгоритма. В такой ситуации выделение данной последовательности действий во вспомогательный (подчиненный) алгоритм, обращение к которому производится по его имени, позволяет сократить запись основного алгоритма. Соответственно можно сформулировать четвертый (в дополнение к линейным, разветвляющимся и циклическим) вид алгоритмов – вспомогательные (подчиненные) алгоритмы, предназначенные для использования в других алгоритмах. Для обращения к отдельно описанному вспомогательному алгоритму служит особая алгоритмическая конструкция – обращение к ранее определенномупоименованному алгоритму (или обращение к вспомогательному алгоритму, или обращение к подчиненному алгоритму. Алгоритм, из которого происходит обращение к вспомогательным алгоритмам (где используется данная алгоритмическая конструкция, называют основным алгоритмом. Возможна ситуация, когда в самом вспомогательном алгоритме также используются вспомогательные, по отношению к которым уже данный вспомогательный алгоритм может рассматриваться как основной и т.д. Кроме того, обращение к ранее определенномупоименованному алгоритму применяется при использовании ранее разработанных известных алгоритмов (или алгоритмов, разработанных другими авторами, например при вычислении элементарных математических функций. Во многих языках программирования выполнение подобных действий синтаксически оформляется также, как и обращение к программной реализации вспомогательного алгоритма, определенной программистом. При описании вспомогательных алгоритмов часто используются понятия входа и выхода алгоритма применительно к данным, обрабатываемым данным алгоритмом. Под входом алгоритма подразумевают данные, получаемые вспомогательным алгоритмом из основного алгоритма перед началом выполнения, а под выходом – данные, получаемые основным алгоритмом из вспомогательного после завершения последнего. При описании процесса выполнения алгоритма, использующего вспомогательные алгоритмы, и самих вспомогательных алгоритмов используется понятие точка обращения и его синонимы точка вызова и момент обращения. Подними подразумевается место в основном алгоритме и момент в процессе его выполнения, где указана (и будет выполнена) алгоритмическая конструкция обращение к ранее определенному поименованному алгоритму с передачей на его вход конкретных значений входных данных и получением результатов с выхода данного алгоритма. Нормальное (безаварийное) выполнение вспомогательного алгоритма всегда завершается возвратом в точку вызова и передачей данных с выхода в основной (вызывающий) алгоритм. Многообразие способов описания вспомогательных алгоритмов и способов реализации обращения к ним в различных языках программирования существенно затрудняет приведение некоторой обобщенной терминологии, одинаково приемлемой для всех языков программирования. Наиболее общими понятиями, соответствующими отношению основной алгоритм – вспомогательный алгоритм, соответственно являются основная (главная) программа и подпрограмма. Тогда говорят, что обращению в основном алгоритме к вспомогательному (точке вызова вспомогательного алгоритма) в основной программе соответствует вызов подпрограммы (обращение к подпрограмме, а определению вспомогательного алгоритма – определение подпрограммы. Кроме термина подпрограмма, в различных языках программирования также широко распространены термины процедура и функция. Для определенности дальнейших рассуждений функцией назовем подпрограмму, которая вычисляет одно значение, зависящее от переданных ей входных данных, а все остальные подпрограммы (вычисляющие больше одного значения или не вычисляющие их вовсе) назовем процедурами. Вызов функции обычно осуществляется из выражений, чтобы вычисленный ею результат можно было сразу использовать. Вызов процедуры записывается самостоятельным оператором. Для разграничения описаний данных, используемых во вспомогательном алгоритме, и данных, передаваемых в него в момент вызова, вводятся понятия формальныхи фактических параметров алгоритма. Формальные параметры – это параметры, которые используются при описании вспомогательного алгоритма для указания используемых в алгоритме имен его входных и выходных данных. Ближайшей аналогией будет понятие аргумента при описании какой-либо математической функции. Например, известно, что cos(x) можно вычислить по формуле cos(x)=sin(x+π/2). Тогда x можно считать формальным параметром функции косинуса приведенную формулу – алгоритмом вычисления данной функции для любого заданного значениях с использованием стандартной функции синус. Фактические параметры – это параметры, указываемые в основном алгоритме как передаваемые вспомогательному в конкретной точке вызова. Порядок перечисления аргументов при определении поименованного алгоритма и при обращении к нему совпадает первое значение при обращении будет соответствовать первому значению при определении алгоритма, второе – второму и т. д. Очевидно, что при наличии в основном алгоритме более одной точки вызова вспомогательного алгоритма фактические параметры могут как различаться, таки совпадать. Воспользовавшись предыдущим примером с алгоритмом вычисления функции косинус, запишем обращение к данному алгоритму в обычной для математики форме, используемой для вычисления значения функции – cos(0), cos(π/3), cos(π/2) и cos(π) . Тогда числа 0 и π, как и выражения π/3 и π/2, будут фактическими параметрами, значение которых принимает формальный параметр x. Соответственно для вычисления функции sin фактическим параметром все четыре раза будет значение выражения x+π/2, зависящее от конкретного значения параметра x, полученного при обращении к функции cos в точке вызова. В качестве фактических параметров при передаче входных данных вспомогательному алгоритму могут быть использованы константы, переменные или даже выражения. Если в качестве параметра использовано выражение, то его значение вычисляется до передачи в подпрограмму. В составе таких выражений могут встречаться и обращения к подпрограммам, соответствующим понятию функция. Например, при обращении хна вход функции передается вычисленное значение выражениях, а результат вызова функции sin(х/2)передается на вход функции sqr, те. является её входным фактическим параметром. Из вспомогательного алгоритма, который является алгоритмом функции, результат передается в точку вызова непосредственно по имени функции при завершении ее работы, поэтому у него есть только входные параметры. Ау алгоритма, вычисляющего несколько значений выходных данных, помимо входных, должны быть еще и выходные параметры, потому что иного способа передать набор выходных данных из вспомогательного алгоритма в основной не существует. Когда параметры используются для передачи выходных данных из вспомогательного алгоритма в основной, тов качестве фактических параметров могут использоваться только переменные, в которые будут записаны вычисленные подпрограммой результаты. Поскольку в любом вспомогательном алгоритме могут использоваться другие вспомогательные алгоритмы, по отношению к которым уже он будет основным, то ив любой подпрограмме в принципе могут использоваться другие подпрограммы. Причем это могут быть другие подпрограммы, определенные в той же программе, или же подпрограммы из стандартных или пользовательских библиотек. Использование внутри подпрограмм обращения к другим подпрограммам не отличается от такого обращения из основной программы. Особым случаем передачи входных данных во вспомогательный подчиненный) алгоритм является передача имени другого вспомогательного алгоритма. В таком случаев составе формальных параметров объявляется имя, с которым сопоставляется конкретный другой вспомогательный алгоритм, имя которого будет передано в качестве соответствующего фактического параметра. При этом по имени формального параметра будет происходить обращение к алгоритму, имя которого является фактическим параметром. Например, можно составить алгоритм, который будет строить на экране график функции. Одним из входных данных для этого алгоритма должно быть указание, график какой именно функции надо строить. Для этого ему надо передать через параметры имя этой функции. Особой разновидностью обмена данными между основной программой и подпрограммой является использование в подпрограмме глобальных данных, доступных для использования в любой части программы. Наличие такой возможности в принципе зависит от конкретного языка программирования, нов любом случае использование глобальных данных является нежелательным, потому что при этом увеличивается вероятность ошибок. Задача 22. Использование вспомогательных алгоритмов. Поиск минимального из двух значений Условие задачи. Даны вещественные числа a, b, c. Вычислить F = min(a, b)/(2*min(a/2, c/b)) + Для вычисления F требуется найти минимум из двух значений и минимум из трех, причем несколько раз для разных наборов значений. Теоретически данное вычисление можно реализовать через ряд последовательных и вложенных условных структур, где выбор наименьшего из трех производится рядом вложенных попарных сравнений. Однако такой алгоритм будет очень сильно ветвящимся, громоздкими относительно сложным для программной реализации. При этом алгоритм определения минимума из трех аргументов можно свести к вложенному обращению к алгоритму определения минимума из двух min(a, b, c) = min( min(a,b),c ), так как если сначала найти минимум из первых двух чисел, а затем сравнить его с третьими определить наименьшее из них, то это и будет наименьшее из трех чисел. В результате потребуется пять раз найти минимальное из различных пар чисел. Правило выбора меньшего значения из двух чисел a и b можно сформулировать следующим образом если a < b, то возвращаем значение, если a > b, то возвращаем значение b, если a = b, то возвращаем значение, равное a (и, следовательно, также равное b). Поскольку при равенстве чисел a и b все равно, какое именно из значений возвращать, то правило выбора можно переформулировать если a < b, то возвращаем значение a, иначе (если a ≥ b) возвращаем значение b. Оформим данное правило в виде отдельного поименованного алгоритма, получающего на входе из внешнего (обращающегося к нему) алгоритма значения чисел a и b, и возвращающего при своем завершении наименьшее из полученных значений в вызывавший алгоритм. Для большей определенности в процессе выполнения наименьшее значение будет сохраняться в отдельной переменной min. В качестве имени алгоритма 22.1 поиска наименьшего значения из двух чисел будем использовать «min2». Запишем алгоритм с использованием введенных обозначений: |