Типовые алгоритмы Ч2. Аа нн
 Скачать 1.6 Mb.
|
|
deallocate(A) end Программа на языке Python # В качестве массива используется # стандартный тип list (список) Введите N -- число элементов массива A: ") N=int(input()) A = [] # Создаем пустой список for i in range(1,N+1): Введите й элемент : ".format(i)) A.append(float(input())) # в Python списки индексируются с 0: Min = abs(A[0] - A[1]) Pos1 = 0 Pos2 = 1 for i in range(0, N-1): for j in range(i + 1, N): R = abs(A[i] - A[j]) if R < Min: Min = R Pos1 = i Pos2 = j print("Pos1={0}, A[{0}]={1}, Pos2={2}, A[{1}]={3}". format(Pos1+1,A[Pos1],Pos2+1,A[Pos2])) Программа в системе Матлаб Введите количество элементов массива for i=1:n A(i)=input('A(i)='); 63 end Min=abs(A(1)-A(2)); Pos1=1; Pos2=2; for i=1:n-1 for j=i+1:n R=abs(A(i)-A(j)); if R Pos1=I; Pos2=j; end end end Наиболее близкие элементы) disp( strcat('A[',int2str(Pos1),']=', … int2str(A(Pos1)),' и A[',int2str(Pos2),']=', … int2str(A(Pos2)))) Задача 12. Сортировка массива методом попарно-обменных перестановок Условие задачи. Отсортировать заданный массив по возрастанию методом попарно-обменных перестановок. Сортировка является классической задачей программирования, на реализацию которой приходится 25% времени работы компьютеров. Сортировка – это перестановка заданного множества элементов в некотором определённом порядке. Порядок расположения элементов может быть следующим по возрастанию, если каждый следующий объект больше предыдущего по неубыванию, если каждый следующий объект больше либо равен предыдущему по убыванию, если каждый следующий объект меньше предыдущего по невозрастанию, если каждый следующий объект меньше либо равен предыдущему. Существует довольно большое число методов сортировки массивов, различающихся по трудоёмкости и учитывающих различные особенности находящихся в массивах данных. Рассмотрим простейшие методы. Следует отметить, что на практике часто при сортировке по возрастанию фактически используется порядок следования элементов по неубыванию, аналогично при сортировке по убыванию используется порядок следования элементов по невозрастанию, поскольку иначе при наличии в массиве равных элементов сортировка невозможна. Сортировка массива методом попарно-обменных перестановок сводится к последовательному сравнению значений соседних элементов массива (элементов, индексы которых различаются ровно на 1). Если в очередной сравниваемой паре элементы расположены в требуемом порядке (при сортировке по возрастанию значение элемента с меньшим индексом должно быть меньше или равно значению элемента с большим индексом, то они остаются на своих местах. Если же элементы не расположены в требуемом порядке (при сортировке по возрастанию значение элемента с меньшим индексом больше, чему элемента с большим индексом, то необходимо поменять местами значения элементов, используя дополнительную переменную. После однократного последовательного от начала к концу сравнения всех пар соседних элементов в массиве и, при необходимости, выполнения перестановок последний элемент массива получает наибольшее значение при сортировке по возрастанию (или наименьшим при сортировке по убыванию. При этом после однократного прохода по массиву переставляемые элементы поменяют свои значения, а минимальное значение переместится на одну позицию ближе к началу. Таким образом, однократный проход по массиву из N элементов от начала к концу и выполнение N–1 сравнения пар соседних элементов и не более N–1 перестановок приводят к занятию последней позиции максимальным значением. Поэтому после однократного прохода по массиву для полной его сортировки необходимо выполнить еще один аналогичный просмотр. В этот раз должна быть пройдена часть массива, предшествующая последнему элементу (от первого до предпоследнего, для нахождения второго по величине значения и его перемещения на место, предшествующее последнему элементу, и т.д., пока оставшаяся для очередного просмотра часть массива не станет состоять всего из одного элемента – первого элемента сортируемого массива, значение которого к этому моменту уже будет точно наименьшим при сортировке по возрастанию или наибольшим при сортировке по убыванию. Таким образом, сначала выполняется просмотр части массива длиной N, затем N–1, затем N–2 и т.д. Последним выполняется просмотр части массива из двух элементов. Массив из одного элемента не проверяется — в нем нет пары для сравнения. Всего последовательный просмотр со сравнением и перестановками выполняется N–1 раз. Для реализации такого поведения используем алгоритмическую конструкцию цикл с предопределенным числом повторений для повторения N–1 раз действия просмотр массива с попарным сравнением значений элементов и перестановкой при необходимости. Причем на каждой его й итерации будут попарно сравниваться с соседними только элементы исходного массива с го поте. сравниваются пары элементов, где ближайший к началу элемент имеет индекс с го по N–i). Просмотр элементов также реализуется с помощью вложенной алгоритмической конструкции цикл с предопределенным числом повторений, причем для каждой й итерации внешнего цикла тело вложенного цикла будет выполняться N–i раз. Если переменная i – счетчик внешнего цикла, а переменная j – счетчик внутреннего цикла, то i последовательно принимает значения от 1 до N–1, а для каждого значения i переменная j последовательно принимает значения от 1 до N–i, где N – количество элементов массива. Предположим, что у нас существуют следующие переменные некоторый массив Marr, натуральное число Lma, соответствующее числу элементов массива Marr, переменная для временного хранения элемента массива TmEl. Тогда алгоритм попарно-обменной сортировки по возрастанию массива Marr длины Lma, введенного пользователем с последующим выводом отсортированного массива, можно записать следующим образом: Структурированная запись алгоритма 12.1 1. Ввести натуральное значение в переменную Lma. 2. Ввести массив из Lma элементов в переменную Marr. 3. Повторять для i от 1 до Lma – 1: 3.1. Повторять для j от 1 до Lma – i: 3.1.1. Если Marr[j]>Marr[j+1], то 3.1.1.1. TmEl = Marr[j]. 3.1.1.2. Marr[j] = Marr[j+1]. 3.1.1.3. Marr[j+1] = TmEl. 4. Вывести массив Marr. Схема алгоритма 1 66 Программа на языке Си #include #include /* Использование динамического выделения памяти для массива 1 67 int main(int argc, char *argv[]) { int Lma=0, i, j; double *Marr = NULL, TmEl; do{ Введите натуральное Lma –\ число элементов массива Marr: "); scanf("%d",&Lma); } while(Lma < 1); if( (Marr = malloc(Lma*sizeof(double))) == NULL) { Ошибка выделения памяти printf(" Аварийное завершение программы return 1; } for(i=0; i < Lma; i++){ Введите й элемент массива ",i+1); scanf("%lf", &Marr[i]); } /* i = 1, 2, 3, ... , Lma-2, Lma-1 */ for(i=1; i < Lma; i++) /* j = 0, 1, 2, ... , Lma-i-1 -- Lma-i значений */ for(j=0; j < Lma-i; j++) if(Marr[j] > Marr[j+1]){ TmEl = Marr[j]; Marr[j]=Marr[j+1]; Marr[j+1]=TmEl; } for(i=0;i Program pr_12_1; Var Marr: array of real; i, j, Lma:integer; TmEl:real; begin Введите количество элементов readln(Lma); setlength(a, Lma); Введите элементы массива for i:=0 to Lma-1 do readln(Marr[i]); for i:=1 to Lma-1 do for j:=0 to Lma-1-i do 68 if Marr[j] > Marr[j+1] then begin TmEl := Marr[j]; Marr[j]:=Marr[j+1]; Marr[j+1]:=TmEl; end Отсортированный массив for i:=0 to Lma-1 do write(Marr[i]:3); readln Marr:=Nil; end. Программа на языке Фортран Program Sort_mas_1 ! Сортировка массива Implicit none real, allocatable :: Marr(:) real TmEl integer i, Lma, j print *,' Введите количество элементов n' read *, Lma allocate (Marr(Lma)) print *,' Введите элементы массива' read *, Marr do i=1, Lma-1 do j=1, Lma-i if (Marr(j) > Marr(j+1))then TmEl = Marr(j) Marr(j) =Marr(j+1) Marr(j+1) =TmEl endif enddo enddo print Отсортированный массив' print *, Marr deallocate (Marr) end Программа на языке Python # В качестве массива используется # стандартный тип list (список) Lma = 0 while Lma < 1: Введите число элементов массива Marr: ") Lma=int(input()) Marr = [] for i in range(1,Lma+1): Введите й элемент массива ".format(i)) 69 Marr.append(float(input())) for i in range(1, Lma): for j in range(1, (Lma-i) + 1): if Marr[j-1] > Marr[j]: TmEl = Marr[j-1] Marr[j-1] = Marr[j] Marr[j] = TmEl for i in range(1, Lma + 1): print("Marr[{0}]={1}".format(i, Marr[i-1])) Программа в системе Матлаб Введите число элементов массива '); Введите элементы массива for i=1: Lma disp(sprintf(' Marr (%g)=',i)) Marr (i)= input(''); end for i=1: Lma-1 for j=1: Lma-i if Marr(j) > Marr(j+1) TmEl = Marr(j); Marr(j) =Marr(j+1); Marr(j+1) =TmEl; end end end Отсортированный массив) disp(Marr) С использованием матричных функций Введите число элементов массива '); Введите элементы массива for i=1: Lma disp(sprintf(' Marr(%g)=',i)) Marr(i)= input(''); end Marr=sort(Marr) Отсортированный массив) disp(Marr) Если при выполнении внутреннего цикла не произведено ни одной перестановки, то можно сказать, что массив уже отсортирован. Если в исходном массиве Marr при сортировке по возрастанию наименьшее значение имеет последний элемент, то последняя перестановка произойдет на N–1 итерации при сравнении первого и второго элементов. Если же наименьшее значение находилось в массиве не на последнем месте, то упорядоченность может быть достигнута раньше, чем за N–1 проход по массиву. Поэтому можно немного 70 улучшить алгоритм, завершив проходы по массиву, когда он уже будет отсортирован. Для этого можно сохранять в некоторой переменной признак выполнения перестановки (например, присваивая ей логическое значение истина) хотя бы водной из итераций вложенного цикла, и заменяя внешний цикл на алгоритмическую конструкцию цикл с постусловием, где условием повторения цикла будет пока i < Lma И признак выполнения перестановок истинен. При этом вычисление номера итерации внешнего цикла i и сброс значения переменной признака в состояние ложь необходимо осуществлять явно. Введя для хранения признака выполнения перестановки переменную, принимающую одно из двух значений истина или ложь, которые непосредственно можно использовать в логических выражениях, запишем модифицированный алгоритм: Структурированная запись алгоритма 12.2 1. Ввести натуральное значение в переменную Lma. 2. Ввести массив из Lma элементов в переменную Marr. 3. i = 1. 4. Повторять 4.1. SwapFlag = ложь. 4.2. Повторять для j от 1 до Lma – i: 4.2.1. Если Marr[j]>Marr[j+1], то 4.2.1.1. TmEl = Marr[j]. 4.2.1.2. Marr[j] = Marr[j+1]. 4.2.1.3. Marr[j+1] = TmEl. 4.2.1.4. SwapFlag = истина. 4.3. i = i + 1. Продолжить повторение, если (i < Lma И SwapFlag = истина. 5. Вывести массив Marr. Схема алгоритма 1 71 1 72 Программа на языке Си #include #include /* Использование динамического выделения памяти для массива int main(void) { int Lma=0, i, j, SwapFlag; double *Marr = NULL, TmEl; Введите натуральное Lma --\ число элементов массива Marr: "); scanf("%d",&Lma); if( (Marr = malloc(Lma*sizeof(double))) == NULL) { Ошибка выделения памяти printf(" Аварийное завершение программы return 1; } for(i=0; i < Lma; i++){ Введите й элемент массива ",i+1); scanf("%lf", &Marr[i]); } i = 1; do{ SwapFlag = 0; /* j = 0, 1, 2, ... , Lma-i-1 -- Lma-i значений */ for(j=0; j < Lma-i; j++) if(Marr[j] > Marr[j+1]){ TmEl = Marr[j]; Marr[j]=Marr[j+1]; Marr[j+1]=TmEl; SwapFlag = 1; } }while( ++i < Lma && SwapFlag); for(i=0;i Program pr_12_2; Var Marr: array of real; i, j, Lma:integer; TmEl:real; SwapFlag:Boolean; 73 begin Введите количество элементов readln(Lma); setlength(a, Lma); Введите элементы массива for i:=0 to Lma-1 do readln(Marr[i]); i:=1; repeat SwapFlag:= false; for j:=0 to Lma-1-i do if Marr[j] > Marr[j+1] then begin TmEl := Marr[j]; Marr[j]:=Marr[j+1]; Marr[j+1]:=TmEl; SwapFlag:=true; end; i:=i+1 until (i=Lma) or not SwapFlag; Отсортированный массив for i:=0 to Lma-1 do write(Marr[i]:5:1); readln Marr:=Nil; end. Программа на языке Фортран Program Sort_mas_2 ! Сортировка массива Implicit none real, allocatable :: Marr(:) real TmEl integer i, Lma, j logical SwapFlag print *,' Введите количество элементов n' read *, Lma allocate (Marr(Lma)) print *,' Введите элементы массива' read *, Marr i=1 SwapFlag = .True. do while (i < Lma .and. SwapFlag) SwapFlag = .False. do j=1, Lma-i if (Marr(j) > Marr(j+1))then TmEl = Marr(j) Marr(j) =Marr(j+1) Marr(j+1) =TmEl SwapFlag = .True. 74 endif enddo i=i+1 enddo print Отсортированный массив' print *, Marr deallocate (Marr) end Программа на языке Python Lma = 0 while Lma < 1: Введите натуральное Lma -- число \ элементов массива Marr: ") Lma=int(input()) Marr = [] # Создаем пустой список for i in range(1,Lma+1): # i = 1, ... , Lma -- всего Lma Введите й элемент массива ".format(i)) Marr.append(float(input())) i = 1 # в Python нет цикла с постусловием – используем # цикл с предусловием и предварительным значением SwapFlag = True while i < Lma and SwapFlag: SwapFlag = False for j in range(1, (Lma-1) + 1): # j = 1, 2, ... , Lma-i -- Lma-i значений if Marr[j-1] > Marr[j]: TmEl = Marr[j-1] Marr[j-1] = Marr[j] Marr[j] = TmEl SwapFlag = True i = i + 1 for i in range(1, Lma + 1): print("Marr[{0}]={1}".format(i, Marr[i-1])) Программа в системе Матлаб Введите число элементов массива '); Введите элементы массива for i=1: Lma disp(sprintf(' Marr (%g)=',i)) Marr (i)= input(''); end i=1; SwapFlag = True; do while (i < Lma && SwapFlag) for j=1:Lma-i 75 if Marr(j) > Marr(j+1) TmEl = Marr(j); Marr(j) =Marr(j+1); Marr(j+1) =TmEl; SwapFlag = True; end end i=i+1; end Отсортированный массив) disp(Marr) Задача 13. Сортировка массива методом поиска максимума Условие задачи.Отсортировать заданный целочисленный массив по убыванию методом выбора (методом поиска максимума. Исходные данные представим в виде одномерного массива А из n целых чисел. Результатом будет тот же массив после сортировки. Метод выбора отличается от рассмотренного в предыдущей задаче и состоит в следующем. Для неупорядоченного массива из n элементов ищут максимальный элемент массива и меняют местами с первым, так как максимальный элемент должен находиться на первом месте, а следующие должны располагаться по убыванию. Входе одного просмотра массива только один элемент встает на свое место. Поэтому просмотр массива и поиск максимального элемента повторяют заново. Так как максимальный элемент после первого просмотра уже стоит на своем месте, то просматривают часть массива от второго элемента до последнего, ищут максимальный и меняют местами со вторым. Такие проходы по массиву повторяют многократно до тех пор, пока из последних двух не будет найден максимальный и поставлен на свое место (предпоследнее. На последнем месте останется самый маленький элемент. Таких проходов потребуется n-1, и каждый раз просматриваемая часть массива уменьшается на один элемент. Алгоритм сортировки использует конструкцию вложенных циклов. Правила использования вложенных циклов рассматривались в задаче 11. Внешний цикл задает количество просмотров массива n-1. При первом просмотре рассматривается часть массива от первого до последнего, при втором от второго до последнего, при третьем от третьего до последнего, прим просмотре от го до последнего и т.д. Во внешнем цикле выполняются следующие действия запоминание го элемента как максимального 76 выполнение внутреннего цикла для элементов от i+1 догов котором ищется максимальный элемент перестановка максимального см элементом. Для перестановки местами максимального элемента см необходимо знать номер максимального элемента. Поэтому при поиске наибольшего значения среди элементов от го до го необходимо запоминать его номер. Введем обозначения n – количество элементов массива, А – массив из n целых чисел, i – переменная для организации внешнего цикла, j – переменная для организации внутреннего цикла, max – значение максимального элемента массива, imax – номер (индекс) максимального элемента. Структурированная запись алгоритма 13 1. Ввести количество элементов массива n. 2. Ввести элементы массива А. 3. Повторять для i от 1 до n-1 следующие действия 3.1. Принять за максимум элемент массива А , max= А. 3.2. Запомнить номер i в переменной imax, imax=i. 3.3. Повторять для j от i+1 до n: 3.3.1. Если А > max, то 3.3.1.1. Max= А. 3.3.1.2. imax=j. 3.4. Поменять местами элемент A[imax] с элементом А. 4. Вывести элементы массива А. Схема алгоритма 1 Программа на языке Си #include #define N 25 int main (void) { int A[N], k, n, i, j, max, imax; Введите количество элементов n\n"); scanf("%d", &n); Введите элементы массива А \n"); for (i=0; i { imax=j; 1 78 max=A[j]; } A[imax]= A[i]; A[i]=max; } printf (Отсортированный массив А \n"); for (i=0; i Program pr_13; Var a: array of integer; i,j,n,imax:integer; max:integer; begin Введите количество элементов readln(n); setlength(a,n); Введите элементы массива for i:=0 to n-1 do readln(a[i]); for i:=0 to n-2 do begin max:=a[i]; imax:=i; for j:=i+1 to n-1 do if a[j]>max then begin imax:=j; max:=a[j]; end; a[imax]:=a[i]; a[i]:=max; end; Отсортированный массив for i:=0 to n-1 do write(a[i]:3); a:=nil; end. Программа на языке Фортран Program Sort_max ! Сортировка массива Implicit none integer, allocatable :: A(:) integer max integer i, n, j,imax print *,' Введите количество элементов n' 79 read *, n allocate (A(n)) print *,' Введите элементы массива' read *, A do i =1, n-1 max= A(i) imax= i do j= i+1, n if (A(j)>max) then imax=j max=A(j) endif enddo A(imax)= A(i) A(i)=max enddo print Отсортированный массив' print *, A deallocate (A) end Программа на языке Python Введите n -- число элементов массива A: ") n=int(input()) A = [] # Создаем пустой список for i in range(1,n+1): # i = 1, ... , n -- всего N Введите й элемент массива ". format(i)) A.append(float(input())) # в Python списки индексируются с 0: for i in range(0, n-1): Max = A[i] imax = i for j in range(i + 1, n): if A[j] > Max: Max = A[j] imax = j A[imax] = A[i] # В переменной Max - предыдущее значение A[imax] A[i] = Max Отсортированный массив ") for i in range(1, n + 1): # i = 1, ... , n print("A[{0}]={1}".format(i, A[i-1])) Программа в системе Матлаб Введите число элементов массива '); Введите элементы массива for i=1:n 80 disp(sprintf('a(%g)=',i)) a(i)= input(''); end for i=1:n-1 max=a(i); imax=i; for j=i+1:n if a(j)>max max=a(j); imax=j; end end a(imax)=a(i); a(i)=max; end Отсортированный массив) disp(a) С использованием матричных функций Введите число элементов массива '); Введите элементы массива for i=1:n disp(sprintf('a(%g)=',i)) a(i)= input(''); end a=-sort(-a); % Или можно a=sort(a,’descend’); Отсортированный массив) disp(a) Многомерные массивы. Матрицы Любой массив характеризуется именем, размером, числом измерений (размерностью) и типом элементов. Размер массива соответствует количеству его элементов. Размерность массива, или число измерений,определяет количество индексов, необходимых для однозначного доступа к элементам массива. Говорят, что число индексов характеризует размерность массива. До сих пор мы рассматривали одномерные массивы, в которых доступ к элементу массива определяется одним индексом. Каждый элемент имеет номер или индекс, определяющий его местоположение в массиве. Сточки зрения структуры данных одномерный массив является линейной структурой и соответствует понятию вектора в математике. Часто данные могут быть организованы в виде таблицы, где расположение каждого элемента определяется двумя параметрами. Например, место в зрительном зале задается указанием номера ряда и номером места в этом ряду. Сточки зрения структуры данных это таблица, что соответствует в математике понятию матрица. Примером матрицы может быть таблица Пифагора (таблица умножения, состоящая из 10 строки столбцов, в которой каждый элемент определяется формулой a ij =i*j. Положение элемента a ij в таблице задается двумя индексами. Индекс i обозначает номер строки, а индекс номер столбца, на пересечении которых находится элемент матрицы. В программировании такие данные удобно описывать как двумерный массив, в котором каждому элементу также соответствуют два индекса первый номер строки, второй номер столбца, где расположен элемент матрицы. Таким образом, в матрице два измерения, те. её размерность – два. Размер матрицы задается количеством элементов по каждому измерению и вычисляется выражением n*m, где n – число строк, m – число столбцов в матрице. Для программирования рассмотренной выше таблицы Пифагора понадобится двумерный массив размером 10*10=100 элементов. В математике принято обозначать элемент матрицы, указывая номера строки и столбца мелким шрифтом после имени матрицы. Например, обращение к элементу й строки го столбца матрицы А обозначается a 23 . В программировании индексы элементов записываются в скобках, в зависимости от языка программирования квадратных или круглых, а индексы элемента или перечисляются через запятую, или помещаются каждый в свою пару скобок. В данном пособии при описании алгоритмов всеми способами, кроме непосредственно текста программы на конкретном языке, используется запись индексов строки и столбца через запятую в квадратных скобках после имени матрицы Например, запись А означает обращение к элементу й строки го столбца матрицы А. Количество используемых индексов массива может быть различным. Как уже известно, массивы с одним индексом являются одномерными, с двумя – двумерными и т.д. Чаще всего применяются массивы с одним или двумя индексами, реже – стремя, ещё большее количество индексов встречается крайне редко. Массивы с несколькими индексами называют многомерными. Многомерные массивы создаются на основе одномерных. Двумерный массив – это одномерный массив, элементы которого являются одномерными массивами. Трехмерный массив – одномерный массив, элементы которого являются двумерными. мерный – одномерный, элементы которого являются (мерными. 82 Проиллюстрировать, как строятся многомерные массивы, можно на приведенном ниже примере. Например, строка – это одномерный массив символов. На странице помещается несколько строк, значит, страница – одномерный массив строки одновременно двумерный массив символов. Позиция каждого символа будет определяться номером строки и его положением в строке. Несколько страниц образуют книгу, таким образом, книга – одномерный массив страниц, он же двумерный массив строки он же трехмерный массив символов. Полка книг будет описываться одномерным массивом книг, он же двумерный массив страниц, трехмерный массив строки четырехмерный массив символов. Книжный стеллаж представляется одномерным массивом полок, двумерным массивом книг, трехмерным массивом страниц, четырехмерным массивом строки пяти- мерным массивом символов. Нетрудно продолжить эту последовательность для читального зала, содержащего несколько стеллажей, библиотеки, в которой не один читальный зал, и даже библиотеки, располагающейся в нескольких зданиях по несколько залов в каждом. Для обращения к элементам многомерного массива требуется несколько индексов, поэтому для перебора всех элементов, как правило, используются вложенные циклы. Количество вложений зависит от размерности массива. Так, для обработки двумерных массивов используют два вложенных цикла. В зависимости от решаемой задачи просмотр матрицы может осуществляться или по строкам, или по столбцам. Когда действия производятся во всей матрице, то порядок обхода элементов неважен. Если необходимо произвести обработку по строкам, сначала обрабатываются все элементы первой строки, затем все элементы второй строки итак до конца массива. Для этого во внешнем цикле изменяется первый индекс (индекс строки, а во внутреннем – второй индекс столбца. Иными словами, чтобы перемещаться по элементам одной строки, нужно изменять номера столбцов. Когда необходимо выполнить действия по столбцам, поступают аналогично, стой лишь разницей, что внешний цикл организуется по столбцам, а внутренний – по строкам, те. сначала обрабатываются все элементы первого столбца, потом все элементы второго, третьего и т.д., а для перемещения по элементам столбца изменяется номер строки. При заполнении матрицы с клавиатуры можно как выводить на экран сообщения-подсказки о том, значение какого именно элемента надо задать, таки не делать этого. В последнем случае пользователь имеет возможность задать матрицу таблично и визуально наблюдать, как размещаются элементы в строках и столбцах. Вывод матрицы на экран также можно осуществлять с указанием индексов каждого элемента или в виде таблицы. Второй способ является более наглядными если размер матрицы это позволяет, предпочтительно использовать именно табличный вывод. Задача 14. Вычисление среднего арифметического в строках матрицы Условие задачи Дана матрица А размера 5*6. В каждой строке матрицы найти среднее арифметическое. Исходным данным в этой задаче является двумерный массив, состоящий из пяти строки шести столбцов. Примем обозначения n=5, m=6. Размеры матрицы заданы конкретными значениями, их вводить не надо, поэтому с клавиатуры вводятся только элементы матрицы. По условию задачи нужно в каждой строке найти среднее арифметическое. Среднее арифметическое это сумма элементов строки, деленная на их количество. Поэтому в этой задаче имеет значение, в каком порядке следует обрабатывать матрицу слева направо (по строкам) или сверху вниз (по столбцам. Чтобы обработка велась по строкам, надо организовать внешний цикл по строками последовательно для каждой й строки выполнять все действия по вычислению суммы, а также по вычислению и выводу среднего арифметического этой строки.Чтобы сумма правильно считалась для каждой строки, нужно всегда задавать начальное значение суммы s=0 перед началом обработки очередной строки. Для суммирования элементов строки надо организовать внутренний цикл по столбцам j=1,m, он обеспечит доступ к каждому элементу й строки, ив нём каждый элемент будет прибавляться к сумме s=s+A[i,j]. В результате после окончания работы внутреннего цикла, будет найдена сумма элементов в й строке. Теперь надо сосчитать среднее арифметическое й строки sr=s/m, так как в строке шесть элементов, и вывести это значение на экран. Далее опять выполнятся те же действия для следующей строки итак до тех пор, пока все строки не будут просмотрены. Так, при обработке первой строки, когда i=1, надо задать s=0 и дальше в цикле при изменении номеров столбцов j=1, m в переменной будет накапливаться сумма элементов й строки s=s+A[1, j]. Сначала в s прибавится значение элемента первой строки первого столбца А затем последовательно элементы А, Аи т.д. По окончании внутреннего цикла нужно сосчитать среднее арифметическое й строки sr=s/m, и вывести это значение на экран. Затем переменная i становится равной 2 (обрабатывается вторая строка, 84 снова надо задать начальное значение суммы s=0, и опять в цикле повторятся те же действия для второй строки s=s+A[2, j]. Далее будет сосчитано среднее арифметическое й строки и выведено на экран и т.д., до тех пор, пока не будут просмотрены все n строк. Структурированная запись алгоритма 14 1. Задание числовых значений для количества строки столбцов матрицы A: n=5; m=6. 2. Ввод элементов матрицы. 3. Цикл по строкам для i=1,n: 3.1. Задание начального значения суммы для обработки й строки s=0. 3.2. Цикл по столбцам для j=1, m: 3.2.1. Прибавление к сумме элемента й строки матрицы s=s+A[i,j]. Конец цикла по j. 3.3. Вычисление среднего арифметического элементов й строки. Выводи на экран. Конец цикла по i. Схема алгоритма 1 Программа на языке Си #include #define N 5 #define M 6 int main() { double a[N][M],s,sr; int i,j; printf(" Введите элементы матрицы for(i=0;i 1 86 for(j=0;j } Программа на языке Паскаль Program main_14; Const n=5; m=6; Var a: array [1..n,1..m] of real; i,j: integer; s,sr: real; begin Введите элементы матрицы for i:=1 to n do for j:=1 to m do read(a[i,j]); Исходная матрица for i:=1 to n do begin for j:=1 to m do write(a[i,j]:3:1,' '); writeln; end; for i:=1 to n do begin s:=0; for j:=1 to m do s:=s+a[i,j]; sr:=s/m; Сред. арифметическое ',i:2, ' строки end; end. Программа на языке Фортран Program main_14 Implicit none integer,parameter :: n=5,m=6 integer i,j real a(n,m),s,sr Введите элементы матрицы' read*,((a(i,j),j=1,m),i=1,n) C1:do i=1,n 87 s=0 C2:do j=1,m s=s+a(i,j) enddo C2 sr=s/m print '(A,I2,1x,A,F5.2)','Ср.арифм. ',& i,' строки enddo C1 end program Программа на языке Python A = [] # Создаем пустой список строк # в Python списки индексируются с 0: for i in range(0, 5): A.append([]) # Добавляем пустой список элементов й строки for j in range(0, 6): Введите A[{0},{1}]: ".format(i+1,j+1)) A[i].append(float(input())) for i in range(0, 5): s = 0 for j in range(0, 6): s = s + A[i][j] sr = s/6 Среднее арифметическое й строки. format(i+1,sr)) Программа в системе Матлаб n=5; m=6; Введите эл. матрицы for i=1:n for j=1:m a(i,j)=input('a(i,j)='); end end for i=1:n s=0; for j=1:m s=s+a(i,j); end sr=s/m; Среднее арифм. %2d строки i, sr)) end С использованием матричных операций и функций n=5; 88 m=6; Введите эл. матрицы for i=1:n for j=1:m a(i,j)=input('a(i,j)='); end end sr=mean(a'); Среднее арифм. каждой строки disp(sprintf('%5.2f ', sr)) Задача 15. Поиск максимального по модулю элемента в столбцах матрицы Условие задачи. Дана матрица В. В каждом столбце матрицы найти максимальное по модулю значение элемента и создать массив Сиз найденных значений. Поскольку в условии данной задачи ничего не сказано о размерах матрицы, то число её строки столбцов M будут целочисленными исходными данными, которые вводятся пользователем в процессе выполнения программы, далее вводятся элементы матрицы B (вещественные числа. В данной задаче требуется выполнять одинаковые действия с каждым столбцом матрицы (матрица будет условно рассматриваться как набор столбцов. Поэтому в цикле для каждого столбца необходимо находить максимальный по модулю элемент (вещественный, как и все элементы) и найденный результат помещать в очередной элемент нового массива С, который будет результатом в этой задаче. Количество элементов в массиве С, очевидно, должно быть таким же, как количество столбцов в матрице В. Поиск максимального по модулю элемента водном столбце с номером j выполняется также, как в одномерном массиве. Для этого сначала в специально выделенную для максимума переменную MAX помещают модуль первого элемента столбца B[1,j]. Далее все остальные элементы этого столбца, взятые по модулю, сравнивают стеку- щим значением переменной MAX (для перемещения по остальным элементам столбца изменяют i от 2 дои, если встречается большее значение, то его помещают в переменную MAX. По окончании всех сравнений в переменной MAX останется значение самого большого по модулю элемента столбца, и его надо поместить в очередной элемент массива С. Его номер, очевидно, должен совпадать с номером столбца матрицы, в котором осуществлялся поиск максимума. Описанные действия должны повторяться в цикле для каждого столбца матрицы В, в результате чего будут получены все элементы массива С. Структурированная запись алгоритма 15 1. Ввести число строки столбцов N и M и элементы матрицы В. 2. В цикле для j=1,M повторять 2.1. Присвоить начальное значение MAX=abs( B[1,j] ). 2.2. В цикле для i=2,N повторять 2.2.1. Выполнять сравнение abs( B[i,j] )>MAX. Если условие выполняется, то присвоить MAX= abs( B[i,j] ). 2.3. Занести MAX в новый массив С. 3. Вывести элементы массива С. Схема алгоритма 1 90 Программа на языке Си #include #include #define N 25 int main (void) { int n,m,i,j; double b[N][N],c[N],max; printf ("\n Введите размеры матрицы n и m\n"); scanf ("%d%d", &n,&m); for (i=0; i } printf (Получен массив С \n"); for (i=0; i 91 printf ("%3.0lf", c[i]); return 0; } Программа на языке Паскаль Program Pr_15; Var B: array [1..20, 1..20] of real; C: array [1..20] of real; N, M, i, j: integer; MAX: real; begin writeln(' Введите размеры матрицы readln(N,M); for i:=1 to N do begin writeln( 'Введите элементы строки for j:=1 to M do read(B[i,j]); end; for j:=1 to M do begin MAX:=abs(B[1,j]); for i:=2 to N do if abs(B[i,j])>MAX then MAX:= abs(B[i,j]); C[j]:=MAX end; Получен массив С '); for j:=1 to M do write(C[j]:6:1); end. Программа на языке Фортран Program Pr_15 Implicit none real, allocatable:: B(:,:), C(:) integer N, M, i, j real MAX print *, ' Введите размеры матрицы' read *, N,M allocate(B(N,M)) allocate(C(M)) do i=1, N print *, 'Введите элементы ',i,' строки' read *, (B(i,j),j=1,M) enddo do j=1, M do MAX=abs(B(1,j)); 92 do i=2, N if (abs(B(i,j))>MAX) then MAX:= abs(B(i,j)) endif enddo C(j)=MAX enddo print Получен массив С ' print *,(C(j),j=1,M) deallocate(B) deallocate(C) end Программа на языке Python Введите N -- число строк матрицы B: ") N=int(input()) Введите M -- число столбцов матрицы B: ") M=int(input()) B = [] # Создаем пустой список строк # в Python списки индексируются с 0 for i in range(0, N): B.append([]) # Добавляем пустой список элементов й строки for j in range(0, M): Введите B[{0},{1}]: ".format(i+1,j+1)) B[i].append(float(input())) C= [] # Создаем пустой список максимальных модулей for j in range(0, M): # j = 0, ... M-1 -- всего M C.append(-1.0) # Добавляем новый элемент со значением, # недопустимым для модуля числа если оно такими останется, значит что-то идет не так. MAX = abs(B[0][j]) for i in range(1, N): if abs(B[i][j]) > MAX: MAX = abs(B[i][j]) C[j] = MAX Получен массив C:") for i in range(0, M): print("C[{0}]={1}".format(i+1, C[i])) Программа в системе Матлаб Введите n='); Введите m='); for i=1:n Введите элементы %d строки) for j=1:m B(i,j)=input('B(i,j)='); 93 end end for j=1:m MAX=abs(B(1,j)); for i=2:n if abs(B(i,j))>MAX MAX=abs(B(i,j)); end end C(j)=MAX; end disp(' Получен массив С ') disp(C) С использованием матричных операций и функций Введите n='); Введите m='); for i=1:n Введите эл. %d строки матрицы) for j=1:m B(i,j)=input('B(i,j)='); end end C= max(abs(B)); disp(' Получен массив С ') disp(C) Задача 16. Преобразование строки и столбца, где находится минимум матрицы Условие задачи.Дана матрица А. Обнулить в ней элементы той строки итого столбца, где находится минимальный элемент матрицы. Известно, что в матрице имеется только один элемент с минимальным значением. Исходными данными являются целочисленные количество строки столбцов M матрицы A и вещественные элементы этой матрицы. Результатом будет та же матрица А после требуемых преобразований. Решение задачи должно начинаться с поиска минимального элемента матрицы, но при этом недостаточно найти значение минимума, а необходимо определить его позицию, те. номера строки и столбца, где он находится. После этого можно будет заменить нулями элементы найденных строки и столбца. Поиск минимума среди всех элементов матрицы отличается от поискав каждой строке или в каждом столбце тем, что сначала в качестве исходного значения за эталон минимума Min берётся любой 94 элемент, обычно в левом верхнем углу, а затем каждый элемент (в любом порядке) сравнивается с эталоном. Обход матрицы при этом можно производить как по строкам, таки по столбцам, нов любом случае с помощью двух вложенных циклов. Если какой-либо элемент оказывается меньше эталона Min, то теперь в качестве эталона берёт- ся этот меньший элемент. Для того чтобы определить местоположение минимума, нужно запоминать ещё два значения номер строки Pos_i и номер столбца Pos_j минимального элемента. Порядок действий для определения искомых номеров строки и столбца минимума будет следующим. Сначала в качестве начального значения эталона возьмём элемент, находящийся в левом верхнем углу, иначе говоря элемент первой строки, первого столбца, Min = A[1,1], и запомним его номер строки и столбца Pos_i = 1; Pos_j=1. Затем будем обходить все элементы матрицы построчно, для этого организуем вложенные циклы внешний цикл – по строкам i=1, N, внутренний цикл – по столбцам j=1, M. При этом каждый элемент A[i,j] будем сравнивать с текущим значением Min, и если встретится меньший по значению элемент, тов занесём его, в Pos_i – его номер строки i, в Pos_j – его номер столбца j. В результате обхода матрицы местоположение минимума будет найдено. Теперь останется заменить нулями элементы строки Pos_i и столбца Pos_j. Для прохода по строке Pos_i нужен цикл, изменяющий номера столбцов j=1,M, в нём каждому элементу A[Pos_i,j] будем присваивать ноль. Аналогично, для прохода по столбцу Pos_j нужен цикл, изменяющий номера строк i=1,N, в нём каждому элементу A[i,Pos_j] будем присваивать ноль. После преобразований полученную матрицу выведем на экран, используя вложенные циклы. Структурированная запись алгоритма 16 1. Ввести размеры матрицы N, M и элементы матрицы А. 2. Задать начальные значения Min = A[1,1]; Pos_i = 1; Pos_j=1. 3. В цикле для i=1,N повторять 3.1. В цикле для j=1,M повторять 3.1.1. Проверять если A[i,j] 3.1.1.2. Pos_i=i; Pos_j=j. 4. В цикле для j=1,M повторять 4.1. A[Pos_i,j]=0. 5. В цикле для i=1,N повторять 5.1. A[i,Pos_j]=0. 6. Вывести элементы матрицы А. Схема алгоритма 1 96 Программа на языке Си #include #include #define N 25 int main (void) { int n,m,i,j,pos_i,pos_j; double a[N][N],min; printf (Введите n и m\n"); scanf ("%d%d", &n,&m); for (i=0; i 1 97 pos_i=0; pos_j=0; for (i=0; i } for (j=0; j } Программа на языке Паскаль Program Pr_16; Var N,M,i,j,Pos_i,Pos_j: integer; A: array [1..20, 1..20] of real; Min: real; begin Введите N и M'); readln (N,M); for i:=1 to N do begin writeln (Введите элементы ', i, ' строки for j:=1 to M do read (A[i,j]); end; Min:=a[1,1]; Pos_i:=1; Pos_j:=1; for i:=1 to N do for j:=1 to M do if A[i,j] Pos_i:=i; Pos_j:=j; end; 98 for j:=1 to M do A[Pos_i,j]:=0; for i:=1 to N do A[i,Pos_j]:=0; writeln (Полученная матрица for i:=1 to N do begin for j:=1 to M do write ( A[i,j]:5:1); writeln; end; end. Программа на языке Фортран Program Pr_16 Implicit none real, allocatable:: A(:,:) integer N, M, i, j real Min print *, ' Введите размеры матрицы' read *, N,M allocate(A(N,M)) do i=1, N print *, 'Введите элементы ',i,' строки' read *, (A(i,j),j=1,M) enddo Min=A(1,1) Pos_i=1 Pos_j=1 do i=1, N do j=1, M if (A(i,j) Pos_i=i Pos_j=j endif enddo enddo do j=1, M A(Pos_i,j)=0 enddo do i=1, N A(i,Pos_j)=0 enddo Print *, 'Полученная матрица' do i=1,N print *,(A(i,j),j=1,M) enddo 99 deallocate (А) end Программа на языке Python Введите 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())) Min = A[0][0] # "Верхний левый угол матрицы" Pos_i = 0 Pos_j = 0 for i in range(0, N): for j in range(0, M): if A[i][j] < Min: Min = A[i][j] Pos_i = i Pos_j = j for j in range(0, M): A[Pos_i][j] = 0.0 for i in range(0, N): A[i][Pos_j] = 0.0 Получена матрица) for i in range(0, N): for j in range(0, M): print("{0}".format(A[i][j]),sep='',end=' ') print(" ") Программа в системе Матлаб Введите N='); Введите M='); for i=1:N Введите элементы %d строки) for j=1:M A(i,j)=input('A(i,j)='); end end AMin=A(1,1); Pos_i=1; Pos_j=1; for i=1:N for j=1:M 100 if A(i,j) Pos_i=i; Pos_j=j; end end end for j=1:M A(Pos_i,j)=0; end for i=1:N A(i,Pos_j)=0; end Полученная матрица) disp(A) С использованием матричных операций и функций clear; Введите N='); Введите M='); for i=1:N Введите эл. %d строки матрицы) for j=1:M A(i,j)=input('A(i,j)='); end end [Amin_stb,pos_j]=min(min(A)); [Amin_str,pos_i]=min(min(A,[],2)); A(:,pos_j)=0; A(pos_i,:)=0; полученная матрица) disp(A) Задача 17. Перестановка столбцов матрицы Условие задачи.Дана матрица В. Поменять в ней местами столбцы с минимальными максимальным элементами. Известно, что в матрице имеется только по одному элементу с минимальными максимальным значением. В этой задаче исходными данными являются двумерный массив В и количество строки столбцов n, которые заранее неизвестны и вводятся с клавиатуры. Чтобы поменять местами столбцы, в которых расположены минимальный и максимальный элемент матрицы, необходимо найти номера этих столбцов. Для этого используем уже известный алгоритм нахождения наибольшего и наименьшего элементов матрицы. Выберем переменные для хранения наибольшего и наименьшего значений, например max и min, а также переменные, в которых будут храниться номера столбцов, где располагаются эти элементы, например и jmin. В переменные max и min сначала поместим значение первого элемента матрицы (элемента в левом верхнем углу В) max=B[1,1] и min=max, а в переменных и jmax запомним номер столбца этого элемента jmin |