Типовые алгоритмы Ч2. Аа нн
 Скачать 1.6 Mb.
|
|
=1, jmax=1. Затем будем просматривать всю матрицу в любом порядке. Зададим внешний цикл по строкам i=1,n , а внутренний по столбцам j=1,m. В цикле сначала будем последовательно сравнивать очередной элемент матрицы с содержимым переменной max, и если очередной элемент матрицы окажется больше max, тов переменную max запишем этот элемента в переменной jmax запомним номер его столбца jmax=j. Иначе будем сравнивать очередной элемент матрицы с содержимым переменной min, и если очередной элемент матрицы B[i,j] окажется меньше min, тов переменную min перепишем его min=B[i,j], а в переменной jmin запомним номер столбца jmin=j. Теперь, когда все элементы будут проверены и номера столбцов для перестановки известны, можно начинать замену. Нам требуется последовательно менять местами элементы столбца с номером с элементами столбца с номером jmax, те. элемент B[1,jmin] c элементом, элемент B[2,jmin] c элементом элемент B[n,jmin] c элементом B[n,jmax]. Перестановка двух элементов всегда осуществляется с использованием третьей вспомогательной переменной, например buf. Для этого организуем цикл, который будет выполняться раз для i=1,n (столько раз, сколько строк в матрице и, следовательно, сколько элементов в столбце. В цикле последовательно осуществим перестановку очередной пары элементов с номерами jmin и jmax, находящихся в й строке, используя операторы buf=B[i,jmin]; B[i,jmin] = B[i,jmax]; B[i,jmax]=buf. При i=1 поменяются местами элемент B[1,jmin] c элементом B[1,jmax], при i=2 – B[2,jmin] c элементом, при i=n – B[n,jmin] c элементом B[n,jmax]. Структурированная запись алгоритма 17 1. Ввод количества строк матрицы n и количества столбцов m. 2. Ввод элементов матрицы. 3. Вывод исходной матрицы до перестановки. 4. В переменные max и min заносится первый элемент матрицы max=B[1,1], min=max. 5. В ячейках jmax и jmin запоминается номер столбца jmax=1 и jmin=1. 6. Начало внешнего цикла по строкам i=1,n. 102 6.1. Начало внутреннего цикла по столбцам j=1,m. 6.1.1. Проверка условия если B[i,j] < min, то и jmin=j. 6.1.2. Иначе проверка условия если B[i,j] > max, то max=B]i,j] и jmax=j. Конец внутреннего цикла по столбцам по j). Конец внешнего цикла по строкам по i). 7. Повторять n раз (для перестановки) i=1,n : 7.1. Перестановка очередной пары элементов в столбцах buf=B[i,jmin] B[i,jmin]= B[i,jmax] B[i,jmax]=buf. Конец цикла по i для перестановки. 8. Вывод матрицы после перестановки. Схема алгоритма 1 103 1 Программа на языке Си #include #include #define N 20 #define M 12 int main() { clrscr(); double b[N][M],min,max,buf; int n,m,jmin,jmax,i,j; Введите n и m"); scanf("%d%d",&n,&m); Введите элементы матрицы for(i=0;i { max=b[i][j]; jmax=j;} for (i=0;i } Программа на языке Паскаль Program main_17; Var i,j,jmin,jmax,n,m:integer; min,max,buf: real; b: array[1..20,1..12] of real; begin Введите n и m'); readln(n,m); Введите элементы матрицы for i:=1 to n do for j:=1 to m do readln(b[i,j]); Исходная матрица for i:=1 to n do begin for j:=1 to m do write(b[i,j]:5:1,' '); writeln; end; min:=b[1,1]; max:=min; jmin:=1; jmax:=1; for i:=1 to n do for j:=1 to m do begin if b[i,j] 106 end; end. Программа на языке Фортран Program main_17 Implicit none integer n, m integer i, j, jmin, jmax real, allocatable :: b(:,:) real min, max, buf print Введите n и m' read *, n, m allocate (b(n,m)) Введите элементы матрицы' read*,((b(i,j),j=1,m),i=1,n) Исходная матрица, & ((b(i,j),j=1,m),i=1,n) min=b(1,1) max=min jmin=1 jmax=1 C1:do i=1,n C2:do j=1,m if(b(i,j) B = [] # Создаем пустой список строк 107 # в 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())) Исходная матрица до перестановки) for i in range(0, n): for j in range(0, m): print("{0:5.1}".format(B[i][j]),sep='',end=' ') print(" ") max = B[0][0] min = max jmax = 0 jmin = 0 for i in range(0, n): for j in range(0, m): if B[i][j] < min: min = B[i][j] jmin = j elif B[i][j] > max: max = B[i][j] jmax = j for i in range(0, n): buf = B[i][jmin] B[i][jmin] = B[i][jmax] B[i][jmax] = buf Матрица после перестановки) for i in range(0, n): for j in range(0, m): print("{0:5.1}".format(B[i][j]),sep='',end=' ') print(" ") Программа в системе Матлаб Введите n='); Введите m='); Введите эл. матрицы for i=1:n for j=1:m b(i,j)=input('b(i,j)='); end end исходная матрица) disp(b) min=b(1,1); max=min; jmin=1; 108 jmax=1; for i=1:n for j=1:m if b(i,j)< min min=b(i,j); jmin=j; elseif b(i,j)>max max=b(i,j); jmax=j; end end end for i=1:n buf=b(i,jmin); b(i,jmin)=b(i,jmax); b(i,jmax)=buf; end Измененная матрица) disp(b) С использованием матричных операций и функций введите n='); введите m='); введите элементы матрицы for i=1:n for j=1:m b(i,j)=input('b(i,j)='); end end исходная матрица) disp(b) [m_min,jmin]=min(min(b)); [m_max,jmax]=max(max(b)); buf=b(:,jmin); b(:,jmin)=b(:,jmax); b(:,jmax)=buf; измененная матрица) disp(b) Задача 18. Работа с элементами главной диагонали квадратной матрицы Условие задачи.Дана квадратная матрица С. Найти значение элемента, наиболее близкого к нулю, среди элементов ее главной диагонали В данной задаче исходными данными является квадратная матрица Си ее размер. В квадратной матрице число строк равно числу столбцов, поэтому для задания размера достаточно одной переменной N. Результатом, те. элементом, наиболее близким к нулю, будет самый маленький по модулю элемент, который назовем min. Элементы матрицы, лежащие на главной диагонали, имеют одинаковые индексы, и для обращения к таким элементам используется одно и тоже значение в качестве номера строки и номера столбца. Например, для матрицы 4*4, элементами главной диагонали являются С, С, С, С. Если в обращении к элементу использовать одну и туже переменную i в качестве го иго индекса, то это будет обращением к элементу главной диагонали С. Алгоритм решения задачи сводится к поиску минимального по модулю элемента на главной диагонали. Сначала поместим модуль первого элемента главной диагонали в переменную min . Затем в цикле, начиная со второго, все элементы главной диагонали сравним с текущим значением min, и если очередной элемент по модулю окажется меньше, чем текущее значение минимального, то поместим в переменную min абсолютное значение этого элемента. Введем обозначения N – количество строки столбцов матрицы С исходная матрица, тогда С – текущий элемент главной диагонали матрицы i – порядковый номер итерации ион же – индекс строки и столбца элемента главной диагонали. Структурированная запись алгоритма 18 1. Ввести размер матрицы N. 2. Ввести элементы матрицы С. 3. Присвоить переменной min модуль первого элемента, стоящий на главной диагонали C[1,1]. 4. Повторить для i от 2 до N. 4.1. Если C[i,i] 5. Вывести результат на экран. Схема алгоритма 1 Программа на языке Си #include #include #define N 25 int main (void) { double C[N][N], min, absC int n, i, j; Введи размер массива scanf("%d", &n); for (i=0; i } printf (″ Элемент главной диагонали наиболее близкий к нулю =% lf″, min); return 0; } 1 Программа на языке Паскаль Program Pr_18; Var C: array of array of real; min, ab:real; n, i, j: integer; begin writeln (' Введите размер матрицы readln (n); setlength (C,n,n); writeln (' Введите элементы матрицы for i:=0 to n-1 do for j:=0 to n-1 do readln ( C[i,j] ); min:=abs(C[0,0]); for i:=1 to n-1 do begin ab:= abs(C[i,i]); if ab < min then min:= ab end; write(' Элемент главной диагонали, ' наиболее близкий к 0 =', min:6:2); C:=nil; end. Программа на языке Фортран Program Pr_18 Implicit none real, allocatable C(:,:), min, ab integer i, j, n print *,’ Введите размер матрицы n’ read *, n allocate(C(n,n)) print *, Введите элементы матрицы read*,(C(i,j), j=1,n),i=1,n) min=abs(C(1,1) do i=2, n ab= abs(C(i,i)) if (ab < min) then min= ab endif enddo print *, ’ Элемент главной диагонали & ’ наиболее близкий к нулю =’, min deallocate(C) end Программа на языке Python # В качестве матрицы используется тип list # (список, элементами которого являются списки Введите N -- размер квадратной матрицы C: ") N=int(input()) C = [] # Создаем пустой список строк # в Python списки индексируются с 0: for i in range(0, N): C.append([]) # Добавляем пустой список элементов й строки for j in range(0, N): Введите C[{0},{1}]: ".format(i+1,j+1)) C[i].append(float(input())) Исходная матрица) for i in range(0, N): for j in range(0, N): print("{0:8.3}".format(C[i][j]),sep='',end=' ') print(" ") min = abs(C[0][0]) for i in range(1, N): # i = 1, ... , N-1 - всего N-1 if abs(C[i][i]) < min: min = abs(C[i][i]) print("min = {:6.2}".format(min)) Программа в системе Матлаб Введите размер матрицы n '); Введите элементы матрицы for i=1:n for j=1:n c(i,j)= input(' '); end end min=abs(c(1,1)); for i=2:n ab=abs(c(i,i)); if ab < min min=ab; end end Элемент главной диагонали) наиболее близкий к 0 =%6.2f',min)) С использованием матричных операций и функций Введите размер матрицы n '); Введите элементы матрицы for i=1:n for j=1:n c(i,j)= input(' '); 113 end end min_el= с Элемент главной диагонали) наиболее близкий к 0 =%6.2f',min_el)) Задача 19. Проверка элементов в части матрицы, ограниченной диагональю Условие задачи. Дана целочисленная квадратная матрица С. Найти в ней среднее арифметическое элементов, кратных 3 или заканчивающихся цифрой 3, среди элементов, лежащих ниже главной диагонали. В данной задаче исходным данным является матрица целых чисел А. Ее размер в условии не определен. Поэтому число строки число столбцов матрицы (целочисленное n) также является исходным данными должно вводиться пользователем. Результатом будет среднее арифметическое некоторых элементов, удовлетворяющих условию вещественное число s. Элементы, лежащие ниже главной диагонали, находятся в строках со второй по последнюю, причем во второй строке под диагональю находится только один элемент, в третьей – два, в четвертой – три, в последней – n-1. То есть в каждой строке матрицы требуется рассматривать только элементы, начиная с первого и заканчивая элементом, предшествующим лежащему на главной диагонали. С учетом того, что у диагональных элементов номера строки и столбца совпадают, элемент, лежащий слева, будет иметь номер столбца на 1 меньше номера строки. Таким образом, для перебора всех элементов под главной диагональю требуется организовать два цикла внешний, изменяющий номер строки i от 2 дои внутренний, изменяющий номер элемента в строке j от 1 до i-1. Для вычисления среднего требуется сначала вычислить сумму s и количество k элементов, удовлетворяющих поставленным условиям, затем поделить сумму на количество. Кратность трем можно проверить, сравнив с нулем остаток отделения числа на 3 (операцию получения остатка отделения, как и во всех предшествующих задачах, обозначим mod). Последняя цифра – остаток отделения числа на Структурированная запись алгоритма 19 1. Ввести размеры матрицы n и элементы самой матрицы А. 2. Обнулить счетчик k=0. 3. Обнулить сумму s=0. 114 4. В цикле для каждой строки i=2,n повторять 4.1. В цикле для каждого элемента строки j=1,i-1 повторять Если A[i,j] mod 3 = 0 или A[i,j] mod 10 = 3, то 4.1.1. Увеличить сумму s=s+A[i,j]. 4.1.2. Увеличить количество k=k+1. 5. Если k>0, то вычислить среднее s=s/k и вывести его на экран, иначе – вывести сообщение Элементов, кратных 3 или оканчивающихся на 3, в массиве нет. Схема алгоритма 1 Программа на языке Си #include { int a[20][20], n, i, j, k=0, s=0; printf (Введите размер квадратной матрицы scanf (″%d”, &n); if (n>20) n=20; printf (Введите значения элементов for (i=0; i 1 116 s+=a[i][j]; k++; } if (k>0) printf (″S = %lf″, (double)s/k); else printf (Элементов, кратных 3 или оканчивающихся на 3, под диагональю нет return 0; } Программа на языке Паскаль Program Pr_19; var a : array [1..20, 1..20] of integer; n, i, j, k, s : integer; begin writeln (Введите размер квадратной матрицы read (n); if n>20 then n:=20; writeln (Введите значения элементов for i:=1 to n do for j:=1 to n do read (a[i,j]); s:=0; k:=0; for i:=2 to n do for j:=1 to i-1 do if (a[i,j] mod 3 = 0)or(a[i,j] mod 10 = 3) then begin s:=s+a[i,j]; k:=k+1 end; if k>0 then write (’S =’, s/k:8:2) else write (Элементов, кратных 3 или ’, оканчивающихся на 3, под диагональю нет) end. Программа на языке Фортран Program Pr_19 Implicit none integer, allocatable :: a(:,:) integer n, i, j, k, s print *, Введите размер квадратной матрицы read *, n allocate(a(n,n)) print *, Введите значения элементов read *, ((a(i,j), j=1,n), i=1,n) do i=2, n 117 do j=1, i-1 if (mod(a(i,j),3)==0.or.mod(a(i,j),10)==3) then s=s+a(i,j) k=k+1 endif enddo enddo if (k>0) then print *, ’S =’, real(s)/k else print *, Элементов, кратных 3 или ’, & оканчивающихся на 3, под диагональю нет) endif deallocate(a) end Программа на языке Python # В качестве матрицы используется тип list # (список, элементами которого являются списки Введите n -- размер квадратной матрицы C: ") n=int(input()) A = [] # Создаем пустой список строк # в Python списки индексируются с 0: for i in range(0, n): A.append([]) # Добавляем пустой список элементов й строки for j in range(0, n): Введите A[{0},{1}]: ".format(i+1,j+1)) A[i].append(float(input())) Исходная матрица) for i in range(0, n): for j in range(0, n): print("{0:8.3}".format(A[i][j]),sep='',end='') print(" ") k=0 s=0 for i in range(1, n): for j in range(0, i-1): if A[i][j] % 3 == 0 or A[i][j] % 10 == 3: s = s + A[i][j] # или s += A[i][j] k = k + 1 # k += 1 if k > 0: s = s / k print("s = {0:8.3}".format(s)) else: Элементов, кратных 3 ",end='') или оканчивающихся на 3, ",end='') под диагональю нет) Программа в системе Матлаб clear; Введите n='); Введите m='); for i=1:n Введите эл. %d строки матрицы) for j=1:m A(i,j)=input('A(i,j)='); end end s=0; k=0; for i=2:n for j=1:i-1 if mod(A(i,j),3)==0 || mod(A(i,j),10)==3 s=s+A(i,j); k=k+1; end end end if k>0 disp(sprintf(' S = %f', s/k)) else Элементов, кратных 3 или оканчивающихся) disp(' на 3, под диагональю нет) end Задача 20. Поиск упорядоченных по возрастанию строк матрицы Условие задачи. В заданной матрице определить количество строк, которые упорядочены по возрастанию. Исходным данным является матрица вещественных чисел А. Её размер в условии не определён. Поэтому число строки число столбцов матрицы (целочисленные N и M) также являются исходными данными и должны вводиться пользователем. Результатом должно стать найденное количество упорядоченных по возрастанию строк матрицы – целое число К. Для подсчёта количества упорядоченных строк необходимо использовать переменную-счётчик К, которая будет увеличиваться на 1 при выполнении условия упорядоченности каждой строки. Для анализа всех строк действия по их проверке должны производиться в цикле, изменяющем номер строки i от первого до последнего. Чтобы узнать, упорядочены ли по возрастанию элементы одной строки, требуется сравнить все пары стоящих рядом элементов этой строки последующий элемент в паре должен быть больше предыдущего. Такие сравнения в строке нужно сделать по количеству парте в цикле M-1 раз (на один раз меньше, чем количество элементов в строке. Но вывод об упорядоченности строки можно сделать только после проведения всех сравнений в ней или досрочно в случае, если какой-то элемент оказался не больше предыдущего. В такой ситуации, как правило, используют логическую переменную f, которой до начала сравнений присваивают одно из двух её возможных значений, например истина. Далее в цикле М раз сравнивают пары соседних элементов, и если требуемое соотношение элементов нарушено, то значение переменной f меняют на ложь (при этом сравнения в данной строке можно прервать, так как уже ясно, что она не упорядочена. После окончания цикла проверяют f: если она осталась с исходным значением истина, то это значит, что в каждой паре следующий элемент больше предыдущего и, следовательно, строка упорядочена по возрастанию, а значит, счётчик К надо увеличить на 1. Если же f поменяла значение на ложь, то это значит, что требуемое условие в данной строке было нарушено и увеличивать К не надо. |