Типовые алгоритмы Ч2. Аа нн
 Скачать 1.6 Mb.
|
|
Структурированная запись алгоритма 26.1 1. Получить от вызывающего алгоритма матрицу A и число строки столбцов в ней N. 2. S = 0. 3. Повторить для i от 1 до N: 3.1. S = S + A[i,i]+A[i,N – i+1]. 4. Если N mod 2 = 1, то S = S – A[N div 2 + 1,N div 2 + 1]. 5. Передать вызывающему алгоритму значение переменной S. Схема алгоритма 26.1 Дадим алгоритму 26.1 собственное имя sum_diag, и, обращаясь к нему как функции с двумя аргументами, первый из которых является квадратной матрицей, а второй – числом строк (столбцов) в ней, запишем алгоритм определения матрицы, в которой сумма элементов диагоналей больше. Структурированная запись алгоритма 26.2 177 1. Ввеcти Na - число строк матрицы A. 2. Ввести значение переменной A, используя вспомогательный алгоритм InputRealQuadMatrix. 3. Ввести Nb - число строк матрицы B. 4. Ввести значение переменной B, используя вспомогательный алгоритм InputRealQuadMatrix. 5. SumA := sum_diag(A, Na). 6. SumB := sum_diag(B, Nb). 7. Если SumA > SumB, то вывести сообщение сумма элементов главной и побочной диагоналей первой матрицы больше, чем второй, иначе если SumA < SumB, то вывести сообщение сумма элементов главной и побочной диагоналей второй матрицы больше, чем первой, иначе вывести сообщение сумма элементов главной и побочной диагоналей первой матрицы равна сумме элементов главной и побочной диагоналей второй матрицы. Схема алгоритма 26.2 1 Алгоритмы ввода и вывода матрицы аналогичны алгоритмам ввода и вывода одномерного массива, использованным в предыдущих задачах, за исключением использования вложенных циклов. Программа на языке Си #include #include 1 179 /* Квадратные матрицы размера N*N представляются динамическими массивами из N*N элементов с доступом только с помощью указателей */ Ввод квадратной матрицы из N строк по N столбцов В подсказке используется имя матрицы MatrName типа const char* Функция выделяет память под массив из N*N элементов типа double и заполняет его путем ввода значений с клавиатуры. В случае ошибок возвращает NULL, иначе указатель на выделенную область памяти */ double* InputRealQuadMatrix(int N, const char* MatrName) { double *A=NULL; int i,j; if(N > 0){ if((A=malloc(N*N*sizeof(double)))==NULL) return NULL; for(i=0; i } else return NULL; } /* Вывод квадратной матрицы M размерах- выводимое на экран имя матрицы (const char *) */ void OutputRealQuadMatrix(const char *MatrName, double *M, int N) { int i,j; for(i = 0; i < N; i++){ for(j=0; j< N; j++) printf("%s[%d,%d]=%8.3lg ",MatrName,i+1, j+1,*(M+i*N+j)); printf("\n"); } } double sum_diag(double *A, int N){ 180 double S = 0; int i; for(i=0; i < N; i++) S = S + *(A+i*N+i) + *(A+i*N+N-i-1); при i=0 A[i][N-i-1] -- верхний правый угол */ if(N % 2 == 1) S = S-*(A+(N/2)*N+N/2); return S; } int main(int argc, char *argv[]) { int Na, Nb; double *A, *B, SumA, SumB; Введите число строк матрицы A: "); scanf("%d",&Na); A=InputRealQuadMatrix(Na,"A"); Введите число строк матрицы B: "); scanf("%d",&Nb); B=InputRealQuadMatrix(Nb,"B"); Исходная матрица A:"); OutputRealQuadMatrix("A",A,Na); Исходная матрица B:"); OutputRealQuadMatrix("B",B,Nb); SumA = sum_diag(A, Na); SumB = sum_diag(B, Nb); if(SumA > SumB){ Сумма элементов главной "); и побочной диагоналей "); первой матрицы больше, "); чем второй } else if(SumA < SumB) { Сумма элементов главной "); и побочной диагоналей "); второй матрицы больше, "); чем первой } else { Сумма элементов главной "); и побочной диагоналей "); первой матрицы равна сумме "); элементов главной и побочной "); диагоналей второй матрицы } if(A) 181 free(A); if(B) free(B); system("pause"); return 0; } Вариант функции вывода матрицы в виде таблицы void OutputRealQuadMatrixM(const char *Name, double *M, int N) { int i,j; if(Name) printf("%s\n",Name); for(i = 0; i < N; i++){ for(j=0; j< N; j++) printf("%8.3lg ",*(M+i*N+j)); printf("\n"); } } Программа на языке Паскаль Program Main_26; uses sysutils; type TRealQuadMatrix = array of array of Real; var Na, Nb: Integer; A, B: TRealQuadMatrix; SumA, SumB: Real; { Возвращает False при ошибке и True при удачном вводе матрицы function InputRealQuadMatrix(N: Integer; MatrName: string; var M: TRealQuadMatrix): Boolean; var i, j: Integer; begin InputRealQuadMatrix := False; if N > 0 then begin SetLength(M, N); for i := 0 to N-1 do begin SetLength(M[i],N); for j := 0 to N-1 do begin 182 Введите ',MatrName, '[',i+1,',',j+1,']: '); readln(M[i,j]); end; end; InputRealQuadMatrix := True; end; end; procedure OutputRealQuadMatrix(MatrName: string; M: TRealQuadMatrix; N: Integer); var i, j: Integer; begin for i := 0 to N-1 do begin for j := 0 to N-1 do write(MatrName,'[',i+1,',',j+1,']=', M[i,j]:8:3,' '); writeln; end; end; function sum_diag(M: TRealQuadMatrix; N: Integer):Real; var S: Real; i: Integer; begin S := 0; for i := 0 to N-1 do S := S + M[i,i] + M[i,N-i-1]; if N mod 2 = 1 then S := S - M[N div 2, N div 2]; sum_diag := S; end; begin SetLength(A,0); SetLength(B,0); Введите число строк матрицы A: '); readln(Na); if not InputRealQuadMatrix(Na, 'A', A) then abort; Введите число строк матрицы B: '); readln(Nb); if not InputRealQuadMatrix(Nb, 'B', B) then abort; Исходная матрица A:'); 183 OutputRealQuadMatrix('A', A, Na); Исходная матрица B:'); OutputRealQuadMatrix('B', B, Nb); SumA := sum_diag(A, Na); SumB := sum_diag(B, Nb); if SumA > SumB then begin Сумма элементов главной '); и побочной диагоналей '); первой матрицы больше, '); чем второй end else begin if SumA < SumB then begin Сумма элементов главной '); и побочной диагоналей '); второй матрицы больше, '); чем первой end else begin Сумма элементов главной '); и побочной диагоналей '); первой матрицы равна '); write('cумме элементов главной '); и побочной диагоналей '); второй матрицы end; end; SetLength(A,0); SetLength(B,0); end. Вариант процедуры вывода матрицы в виде таблицы procedure OutputRealQuadMatrixM(Name: string; M: TRealQuadMatrix; N: Integer); var i, j: Integer; begin writeln(Name); for i := 0 to N-1 do begin for j := 0 to N-1 do write(M[i,j]:8:3,' '); writeln; end; end; Программа на языке Фортран Program main_26 Implicit none real, allocatable :: A(:,:),B(:,:) integer Na,Nb real sum_diag ,SumA, SumB Введите число строк матрицы A:' read*,Na allocate(A(Na,Na)) call InputRealQuadMatrix(Na,'A',A); Введите число строк матрицы B:' read*,Nb allocate(B(Nb,Nb)) call InputRealQuadMatrix(Nb,'B',B); Исходная матрица A:' call OutputRealQuadMatrix('A',A,Na) print*,' Исходная матрица B:' call OutputRealQuadMatrix('B',B,Nb) SumA=sum_diag(A, Na) SumB=sum_diag(B, Nb) if (SumA>SumB)then Сумма элементов главной и побочной' диагоналей первой матрицы больше' print*,' чем второй' else if (SumA Implicit none integer,intent(in)::N Character(*),intent(in)::MatrName real,intent(out)::X(N,N) integer i,j do i=1,N do j=1,N print 'Введите ', & 185 MatrName,'[',i,',',j,']=' read*,X(i,j) enddo enddo end Subroutine OutputRealQuadMatrix(MatrName,X,N) Implicit none integer,intent(in)::N Character(*),intent(in)::MatrName real,intent(in)::X(N,N) integer i,j do i=1,N do j=1,N print '(A,A,I1,A,I1,A,F3.0)',MatrName,'[',i,',',j,']=',X(i,j) enddo enddo end Real function sum_diag(A,N) Implicit none integer,intent(in)::N real,intent(in)::A(N,N) integer i real S S=0 do i=1,N S=S+A(i,i)+A(i,N-i+1) enddo if (mod(N,2)==1) then S=S-A(N/2+1,N/2+1) endif sum_diag=S Вариант подпрограммы вывода матрицы в виде таблицы Subroutine OutputRealQuadMatrix(MatrName,X,N) Implicit none integer,intent(in)::N Character(*),intent(in)::MatrName real,intent(in)::X(N,N) integer i,j print *, MatrName do i=1,N print '( Программа на языке Python # В качестве матрицы используется стандартный тип # list (список, элементами которого являются списки # Ввод квадратной матрицы из N строк по N столбцов def InputRealQuadMatrix(N): A = [] # Создаем пустой список for i in range(0, N): # i = 0, ... , N-1 -- всего n A.append([]) # Добавляем пустой список элементов й строки for j in range(0, N): Введите A[{0},{1}]: ".format(i+1,j+1)) A[i].append(float(input())) return A # Вывод квадратной матрицы M размерах- выводимое на экран имя матрицы (строка) def OutputRealQuadMatrix(MasName,M,N): for i in range(0, N): for j in range(0, N): print("{0}[{1},{2}]={3:8.3} ". format(MasName,i+1, j+1,M[i][j]), sep='',end=' ') print(" ") return None def sum_diag(A, N): S = 0 for i in range(0, N): S = S + A[i][i] + A[i][N-i-1] # при i=0 A[i][N-i-1] -- верхний правый угол if N % 2 == 1: S = S - A[N // 2][N // 2] return S Введите число строк матрицы A: ") Na=int(input()) A = InputRealQuadMatrix(Na) Введите число строк матрицы B: ") Nb=int(input()) B = InputRealQuadMatrix(Nb) Исходная матрица A:") OutputRealQuadMatrix("A",A,Na) Исходная матрица B:") OutputRealQuadMatrix("B",B,Nb) 187 SumA = sum_diag(A, Na) SumB = sum_diag(B, Nb) if SumA > SumB: # тройные кавычки сохраняют внутри # строки все переводы строк, пробелы и т.п. Сумма элементов главной и побочной диагоналей первой матрицы больше, чем второй) elif SumA < SumB: Сумма элементов главной и побочной диагоналей второй матрицы больше, чем первой) else: Сумма элементов главной и побочной диагоналей первой матрицы равна сумме элементов главной и побочной диагоналей второй матрицы.""") Вариант подпрограммы вывода матрицы в виде таблицы # Вывод квадратной матрицы M размерах- первая выводимая на экран строка # (например, имя матрицы) def OutputRealQuadMatrixM(Name,M,N): print(Name) for i in range(0, N): for j in range(0, N): print("{0:8.3} ". format(M[i][j]), sep='',end=' ') print(" ") return None Программа в системе Матлаб % Главная clear; Введите число строк матрицы A:'); A=InputRealQuadMatrix(Na,'A'); Введите число строк матрицы B:'); B=InputRealQuadMatrix(Nb,'B'); Исходная матрица A:') OutputRealQuadMatrix('A',A,Na) disp(A) Исходная матрица B:') OutputRealQuadMatrix('B',B,Nb) disp(B) SumA=sum_diag(A, Na) SumB=sum_diag(B, Nb) if SumA>SumB Сумма элементов главной и побочной' ) диагоналей первой матрицы больше, ') чем второй) else if SumA 188 disp(' чем первой, или равна ей) else Сумма элементов главной и побочной' ) диагоналей первой матрицы равна ') сумме элементов главной и побочной' ) диагоналей второй матрицы) end % Ввод квадратной матрицы из N строк по N столбцов function X=InputRealQuadMatrix(N,MatrName) for i=1:N for j=1:N Введите %s(%d,%d)=',MatrName,i,j)) X(i,j)= input(' '); end end end Вывод квадратной матрицы из N строк по N столбцов function OutputRealQuadMatrix(MatrName,M,N) for i=1:N for j=1:N disp(sprintf('%s[%d,%d]=%g',MatrName,i,j,M(i,j))) end end end Сумма диагоналей function S=sum_diag(A,N) S=0; for i=1:N S=S+A(i,i)+A(i,N-i+1); end if mod(N,2)==1 S=S-A(fix(N/2)+1,fix(N/2)+1); end end Вариант вывода матрицы в виде таблицы (вместо вызова функции OutputRealQuadMatrix) disp(X) Задача 27. Использование вспомогательных алгоритмов. Обработка отдельных столбцов матрицы Условие задачи. Дана матрица А. Найти минимальный элемент в том столбце матрицы, в котором среднее арифметическое элементов самое большое Исходным данным является матрица вещественных чисел А, размер которой в условии не определён. Поэтому число строки число столбцов матрицы (целочисленные n и m) также являются исходными данными и должны вводиться пользователем. Результатом будет минимальный элемент min в том столбце матрицы, в котором среднее арифметическое элементов самое большое. Для получения результата надо сначала вычислить среднее арифметическое элементов во всех столбцах, затем определить номер столбца с наибольшим средними уже в этом столбце найти минимальный элемент. Поэтому для решения задачи можно использовать несколько вспомогательных алгоритмов ввод матрицы In_matr; вычисление среднего арифметического элементов водном, любом, столбце Sredn; определение номера столбца с максимальным средним арифметическим поиск минимального элемента в искомом столбце Min_el. Вспомогательный алгоритм выполняет ввод элементов матрицы А. Входными данными будут количество строки количество столбцов m матрицы, а выходным параметром – исходная матрица A. В этом алгоритме для обхода всех элементов матрицы использована конструкция вложенных циклов. Чтобы вводить элементы в порядке их следования по строкам, внешний цикл надо организовать по строкам, а внутренний по столбцам. Вспомогательный алгоритм Min_el(A,n,j) предназначен для поиска минимального элемента водном столбце с любым номером. Входными параметрами будут матрица A, количество её строки номер столбца j, в котором надо найти минимальный элемент. В этом алгоритме будет использован цикл с известным числом повторений для поиска минимального элемента в столбце по рассмотренному ранее алгоритму. Минимальный элемент min будет результатом работы вспомогательного алгоритма и передан в вызывающий алгоритм. Вспомогательный алгоритм Sredn (A,n,m,j) предназначен для вычисления среднего арифметического водном столбце матрицы. Входными данными будут матрица A, количество её строк n, столбцов m и номер столбца j, в котором ищется результата выходным параметром – значение среднего арифметического всех элементов данного столбца Sredn. В этом алгоритме будет использована конструкция цикла с предопределённым числом повторений для получения суммы элементов столбца путем перебора строк. Полученная сумма будет поделена на количество строки результат передан в вызывающий алгоритм. Вспомогательный алгоритм J_max(A,n,m) предназначен для поиска номера столбца с максимальным средним арифметическим. Входными параметрами будут матрица A, количество её строки столбцов m, а выходным параметром – значение номера столбца, в котором среднее арифметическое всех элементов наибольшее J_max. Чтобы найти искомый номер столбца, надо воспользоваться известным уже алгоритмом поиска максимума, в котором до цикла за начальное значение максимума принимается значение среднего в первом столбце, полученное как результат вспомогательного алгоритма, и запоминается его номер столбца. Исходными данными для первого вызова будут матрица A, количество строк n, количество столбцов m и номер первого столбца. В цикле с параметром, который изменяется от номера второго столбца до последнего, вызывается вспомогательный алгоритм получения среднего арифметического в текущем столбце. В него будут передаваться матрица A, количество строк n, количество столбцов m и текущий номер столбца j. Среднее арифметическое текущего столбца сравнивается с максимальным значением, и если оно окажется больше максимального, то им заменяется значение максимума и запоминается его номер. Если надо, чтобы результат одного вспомогательного алгоритма использовался в другом алгоритме, возможны разные варианты организации их вызовов. Главный алгоритм может последовательно один за другим вызывать вспомогательные алгоритмы, получая результат одного алгоритма и передавая его другому как входное данное. Обращение к одному алгоритму (если это функция) можно указать в качестве входного данного для другого, и это также будет означать передачу результата первого алгоритма второму как входного данного. Можно обращаться из одного вспомогательного алгоритма к другому и использовать его выходное значение. В данной задаче будут использоваться все три варианта. В главном алгоритме сначала вводим число строки число столбцов m матрицы А. Затем вызываем вспомогательный алгоритм In_matr(A,n,m) для ввода элементов матрицы. Входными данными для этого алгоритма будут количество строки количество столбцов m. Выходным значением будет матрица А. Далее выполняем вызов вспомогательного алгоритма для поиска минимального элемента в искомом столбце. Входными данными для этого алгоритма будут матрица, количество строки третьим параметром – результат вызова вспомогательного алгоритма J_max(A,n,m), те. номер столбца с наибольшим средним. Выходное значение вспомогательного алгоритма Min_el (A,n,j) сохранится в переменной значение которой и будет выведено на экран. Структурированная запись главного алгоритма 1. Ввести с клавиатуры числа n и m. 2. Перейти к вспомогательному алгоритму In_matr с исходными данными количеством строки количеством столбцов. 3. Перейти к вспомогательному алгоритму Min_el с исходными данными массив Аи результатом вспомогательного алгоритма J_max(A,n,m). 4. Вывести на экран сообщение “min=” и результат, полученный в п. 3. Схема алгоритма Структурированная запись вспомогательного алгоритма In_matr 1. Получить от вызывающего алгоритма исходные данные количество строки количество столбцов m. 2. Повторять для i от 1 до n: Повторять для j от 1 до m: 2.1.1 Ввести А 4. Передать результат A в вызывающий алгоритм. Структурированная запись вспомогательного алгоритма Min_el 1. Получить от вызывающего алгоритма исходные данные матрицу А количество строк номер столбца j. 2. Присвоить переменной min значение первого элемента го столбца А. 3. Повторить для i от 2 до n: 3.1. Если А min , то запомнить А в min. 4. Передать результат min в вызывающий алгоритм. Схема алгоритма Структурированная запись вспомогательного алгоритма Sredn 1. Получить от вызывающего алгоритма исходные данные матрицу А ее размер n , и номер столбца j. 2. Обнулить s=0. Повторять для i от 1 до n: 3.1 s=s+ А. 4. Sredn |