 |
Матрицы (двумерные массивы) (РГЗ)
|
|
|
|
1. Цель работы: программирование алгоритмов обработки двумерных массивов
2. Основные сведения
Матрица – это прямоугольная таблица элементов (например, чисел или символов). Матрица представляется в виде двумерного массива, то есть массива, все элементы которого имеют два индекса. Матрица, как и таблица, состоит из строк и столбцов. Два индекса элемента - это и есть номера строки и столбца, на пересечении которых этот элемент находится. В языке Си каждый индекс записывается отдельно в квадратных скобках. Каждую строку и каждый столбец матрицы можно рассматривать как обычный одномерный массив. Поэтому можно сказать, что матрица – это массив из массивов.
Первый индекс элемента матрицы – это строка, второй – столбец. Поэтому когда говорят о «матрице 4 на 5», это означает, что матрица имеет 4 строки и 5 столбцов. Матрицы, у которых число строк равно числу столбцов, называют квадратными. В квадратных матрицах можно выделить главную диагональ – это все элементы, у которых номер строки равен номеру столбца, то есть A[0][0], A[1][1],..., A[N-1][N-1] для матрицы размером N на N.
Объявление матриц
Матрицы объявляются так же, как и простые массивы, но у них не один индекс, а два. При объявлении в отдельных квадратных скобках указывается количество строк и количество столбцов. Например, оператор
int B[10][10];
выделит место в памяти под матрицу целых чисел, имеющую 10 строк и 10 столбцов. Если матрица глобальная (объявляется выше всех процедур и функций), то она в самом начале заполняется нулями. Локальные матрицы (объявленные внутри процедуры или функции) первоначально содержат «мусор» – неизвестные значения.
Начальные значения элементов
|
|
|
При объявлении можно сразу задать все или часть ее элементов, например:
float X[2][3] = {{1., 2., 3.},{4., 5., 6.}};
Как видно из примера, элементы каждой строки заключаются в отдельные фигурные скобки. Если задать не все элементы, то остальные заполнятся нулями:
float X[2][3] = {{1., 3.},{6.}};
Здесь элементы X[1][2], X[2][1] и X[2][2] будут нулевыми.
Расположение матриц в памяти
Во всех современных языках программирования элементы матрицы располагаются по строкам, то есть сначала изменяется последний индекс. Объявленная выше матрица X расположена так:
X[0][0] X[0][1] X[0][2] X[1][0] X[1][1] X[1][2]
Стандартный ввод и вывод
Для работы с матрицами требуется вложенный цикл, то есть цикл в цикле.
#include <stdio.h>
const int M = 5; // число строк
const int N = 4; // число столбцов
main()
{
int i, j, A[M][N];
for (i = 0; i < M; i ++) // цикл по строкам
for (j = 0; j < N; j ++) // цикл по столбцам строки (элементы строки)
{
printf ("A[%d][%d]=", i, j); // подсказка для ввода
scanf ("%d", & A[i][j]); // ввод A[i][j]
}
// работа с матрицей
}
Заполнение случайными числами
Выполняется также в двойном цикле аналогично одномерным массивам. В примере показано заполнение целой матрицы случайными числами в интервале [a,b].
for (i = 0; i < M; i ++)
for (j = 0; j < N; j ++)
A[i][j] = random(b-a+1) + a;
Вывод на экран
При выводе матрицы ее элементы желательно расположить в привычном виде – по строкам, т.е. вывели одну строку матрицы, перешли на новую строку экрана, и т.д. Надо учитывать, что для красивого вывода на каждый элемент матрицы надо отвести равное количество символов (иначе столбцы будут неровные). Делается это с помощью форматирования – цифра после знака процента задает количество символов, отводимое на данное число.
printf("Матрица A\n");
for (i = 0; i < M; i ++) // цикл по строкам
{
for (j = 0; j < N; j ++) // вывод одной строки (в цикле)
printf ("%4d", A[i][j]); // 4 символа на число
printf("\n"); // переход на другую строку
}
Алгоритмы для работы с матрицами
|
|
|
1) Поиск минимального элемента
В отличие от одномерных массивов, для перебора всех элементов матрицы надо использовать двойной цикл. Ниже показано, как найти минимальный элемент в массиве и его индексы. Сначала считаем, что минимальным является элемент A[0][0], а затем проходим все элементы, проверяя, нет ли где еще меньшего. Можно запоминать только индексы, а значение минимального элемента получать прямо из массива.
float A[M][N], i, j, row, col;
...
row = col = 0; // сначала считаем, что A[0][0] - минимальный
for (i = 0; i < M; i ++) // просмотр всех строк
for (j = 0; j < N; j ++) // просмотр всех столбцов
if (A[i][j] < A[row][col])
{
row = i; // запомнили новые индексы
col = j;
}
printf ("Минимальный элемент A[%d][%d]=%d",row, col, A[row][col]);
2) Работа с отдельными элементами
Рассмотрим квадратную матрицу N на N. Выведем на экран обе ее диагонали (главную диагональ и перпендикулярную ей). С главной диагональю все просто – в цикле выводим все элементы, у которых номера строки и столбца равны, то есть A[i][i] для всех i от 0 до N-1.
Вторую диагональ формируют такие элементы:
A[0][N-1], A[1][N-2], A[2][N-3],..., A[N-1][0]
Обратим внимание, что каждый следующий элемент имеет номер строки на 1 больше, а номер столбца – на 1 меньше. Таким образом, сумма номеров строки и столбца постоянна и равна N-1. Тогда, зная номер строки i можно сразу сказать, что на второй диагонали стоит ее элемент A[i][N-1-i].
3) Перестановка строк и столбцов
Пусть надо переставить две строки с индексами i1 и i2. Это значит, что для каждого столбца j надо поменять местами элементы A[i1][j] и A[i2][j] через временную переменную temp.
for (j = 0; j < N; j ++)
{
temp = A[i1][j];
A[i1][j] = A[i2][j];
A[i2][j] = temp;
}
Пример, объединяющий некоторые типовые алгоритмы работы с матрицей.
Даны две матрицы А и В одинакового размера m x n, заполненные случайными числами в диапазоне от 0 до 19. Получить матрицу C=max(A[i.j],B[i,j]) и матрицу D=min(A[i,j],B[i,j]).
#include <stdio.h>
#include <conio.h>
#include <stdlib.h> //для генерации случайных чисел
const int m=4, n=4;
int random(int r)
{ return rand()%r;
}
main()
{
int i,j,a[m][n],b[m][n],c[m][n],d[m][n];
system("CLS");
srand(11); //инициализация датчика случайных чисел
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=random(20);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
b[i][j]=random(20);
// вывод матриц а и b
printf("\n матрица a\n");
for (i=0;i<m;i++)
|
|
|
{ printf("\n");
for (j=0;j<n;j++)
printf("%4d",a[i][j]);
}
printf("\n\n матрица b\n");
for (i=0;i<m;i++)
{ printf("\n");
for (j=0;j<n;j++)
printf("%4d",b[i][j]);
}
// формирование матриц c и d
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if (a[i][j]>b[i][j])
{ c[i][j]=a[i][j];
d[i][j]=b[i][j];
}
else
{ c[i][j]=b[i][j];
d[i][j]=a[i][j];
}
// вывод матриц c и d
printf("\n\n матрица c\n");
for (i=0;i<m;i++)
{ printf("\n");
for (j=0;j<n;j++)
printf("%4d",c[i][j]);
}
printf("\n\n матрица d\n");
for (i=0;i<m;i++)
{ printf("\n");
for (j=0;j<n;j++)
printf("%4d",d[i][j]);
}
puts("\n");
system("PAUSE");
}
3. Выполнение работы
Варианты задания (номер варианта определяется по последней цифре номера студенческого билета):
0. Сформировать двумерный массив A размером N x 2 (N - количество строк, равное предпоследней цифре номера студенческого билета+2; 2 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Найти наибольший элемент каждой строки матрицы А. Из этих максимальных элементов составить одномерный массив F. Вывести элементы массива F.
1. Сформировать двумерный массив B размером N x 3 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 3 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Составить одномерный массив D из минимальных элементов столбцов матрицы. Вывести элементы массива D.
2. Сформировать двумерный массив B размером N x 4 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 4 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Вычислить и вывести строку матрицы B, содержащую максимальное количество отрицательных.
3. Сформировать двумерный массив C размером N x 5 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 5 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Вычислить сумму положительных элементов в каждой строке матрицы C. Из полученных сумм составить одномерный массив D. Вывести элементы массива D.
4. Сформировать двумерный массив D размером N x 6 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 6 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива на экран и в файл (см. п.3.4. и п.3.6.). В каждом столбце матрицы D найти максимальный элемент. Среди найденных чисел найти минимальное и вывести на экран и в файл.
|
|
|
5. Сформировать двумерный массив E размером N x 7 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 7 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Вычислить сумму отрицательных элементов столбца, в котором находится максимальный элемент матрицы E. Вывести полученную сумму и номер столбца.
6. Сформировать двумерный массив F размером N x 8 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 8 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. В строке матрицы F, содержащей максимальный элемент, заменить все отрицательные числа на нули. Вывести номер этой строки и максимальный элемент.
7. Сформировать двумерный массив G размером N x 9 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 9 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Записать в одномерный массив F строку матрицы G, содержащую минимальный элемент. Вывести элементы массива F.
8. Сформировать двумерный массив L размером N x 10 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 10 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Вывести номер строки и саму строку матрицы L, в которой сумма положительных элементов максимальна.
9. Сформировать двумерный массив Z размером N x 11 (N – количество строк, равное предпоследней цифре номера студенческого билета +2; 11 – количество столбцов) с помощью генератора случайных чисел и вывести элементы массива. Вычислить сумму положительных элементов строки, в которой находится минимальный элемент матрицы Z. Вывести полученную сумму и номер строки.
4. Контрольные вопросы
1. Как объявить матрицу? Как инициализировать?
2. Ввод – вывод матрицы по строкам.
3. Как поменять местами строки в матрице?
4. Как найти минимальный элемент матрицы и его индексы?
5. Как вычислить сумму элементов строки матрицы?
6. Как получить транспонированную матрицу?
2 часть
Лабораторная работа № 6
Функции
1. ЦЕЛЬ РАБОТЫ: Изучение методов использования функций языка Си.
2. ОСНОВНЫЕ СВЕДЕНИЯ
Часто в программе требуется повторить определенную последовательность операторов в разных частях программы. Для того, чтобы описывать эту последовательность один раз, а применять многократно, в языках программирования применяются подпрограммы. Подпрограмма - автономная часть программы, выполняющая определенный алгоритм и допускающая обращение к ней из различных частей общей программы.
|
|
|
В языке Си существует один вид подпрограмм - функции. Каждая программа в своем составе должна иметь главную функцию main(), служащую точкой входа в программу. Кроме функции main(), в программу может входить произвольное число функций, выполнение которых инициализируется либо прямо, либо вызовами из функции main(). Каждая функция по отношению к другой является внешней. Для того, чтобы функция была доступной, необходимо, чтобы до ее вызова о ней было известно компилятору. Форма записи функции:
<тип > <имя функции>(<формальные параметры>){<тело функции >}
Если тип возвращаемого функцией значения не указан, то подразумевается int. Если с именем функции не связан результат, то нужно указать тип функции void. Параметры, записываемые в обращении к функции, называются фактическими; параметры, указанные в описании функции - формальными. Фактические параметры должны соответствовать формальным по количеству, порядку следования и типу. Объекты, объявленные вне функции, действуют в любой функции и называются глобальными. Объекты, объявленные в функции, действуют только в ней и называются локальными. В теле функции обычно присутствует оператор return <выражение>, определяющий возвращаемое функцией значение.
Все параметры функции, кроме массивов, передаются по значению, т.е. внутри функции создаются локальные копии параметров. Если необходимо передать саму переменную, а не её копию, то в функцию передаётся адрес этой переменной. Таким образом, через параметры можно передавать результат выполнения функции. То есть, параметры, с помощью которых результаты должны передаваться из функции в точку вызова, описываются как указатели. Вызов функции может быть оформлен в виде оператора, если с именем функции не связано возвращаемое значение, или в виде выражения, если возвращаемое значение связано с именем функции.
Прототип функции может указываться до вызова функции вместо описания функции для того, чтобы компилятор мог выполнить проверку соответствия типов аргументов и параметров. Прототип функции по форме такой же, как и заголовок функции. В конце него ставится «;».
Функции можно подключать с помощью директивы #include <имя файла>. Такие файлы с функциями удобно использовать в диалоговых программах с пользовательским меню, позволяющих выбрать один из режимов.
Пример 1: Функция с параметрами-значениями. Результат связан с именем функции. В программе объявляется прототип функции, а сама функция описывается ниже.
//lab8_1
#include <stdio.h>
#include <conio.h>
int max(int,int); //Прототип функции
void main()
{ int x,y,z;
printf(" input x,y ");
scanf("%d%d",&x,&y);
z=max(x,y); //Вызов функции с фактическими параметрами
printf("x=%d y=%d max=%d",x,y,z);
getch();
}
int max(int a,int b) //Заголовок функции с формальными параметрами
{ int c;
if (a>b) c=a;
else c=b;
return c;
}
Пример 2: Функция с параметрами-указателями. Здесь передаются адреса фактических параметров, по которым и получаем результат. Функция меняет местами переменные x,y.
//lab8_2
#include <stdio.h>
#include <conio.h>
main()
{ float x,y;
void swap(float *, float *); // Прототип функции с параметрами - указателями
printf("\n введите x,y ");
scanf("%f%f",&x,&y);
swap(&x,&y); // Передаём адреса переменных
printf("\n x=%4.2f y=%4.2f ",x,y);
getch();
}
void swap(float * a, float * b)
{float c;
c=*a; // *a - содержимое по адресу a
*a=*b;
*b=c;
}
Пример 3: Подключение файлов с функциями и создание меню.
! Внимание! Следите за тем, чтобы константы, объявленные директивой #define, не переобъявлялись в функциях.
//lab8_3
#include <stdio.h>
#include <conio.h>
#include "lab3.c"
#include "lab5.c"
#include "lab6.c"
main()
{ int nom;
while(1)
{ clrscr();
printf("\n 1. Сумма ряда \n");
printf(" 2. Матрица \n");
printf(" 3. Строки \n");
printf(" 4. Выход \n");
scanf("%d",&nom);
switch(nom)
{
case 1:lab3();break;
case 2:lab5();break;
case 3:lab6();break;
case 4:return 0;
default:printf("Неверный режим");
}
}
getch();
}
Пример 4: Передача в функцию массива с использованием указателя. Результат – элементы массива возводятся в квадрат. Функция описывается до вызова, поэтому прототип не объявляется.
//lab8_4
#include <stdio.h>
#include <conio.h>
void quart(int n, float * x) // Можно void quart(int n, float x[])
{ int i;
for (i=0;i<n;i++)
x[i]=x[i]*x[i];
}
main()
{ float z[]={1,2,3,4};int j;
clrscr();
for (j=0;j<4;j++)
printf(" %6.2f",z[j]);
quart(4,z);
for (j=0;j<4;j++)
printf("\n %6.2f",z[j]);
getch();
}
3. ВЫПОЛНЕНИЕ РАБОТЫ
Используя функции, написать программу по своему варианту.
Варианты заданий
1. Написать функцию, выводящую в порядке возрастания элементы одномерного массива. В главной программе вызвать функцию для двух разных массивов.
2. Написать функцию вычисления произведения прямоугольной матрицы A размера k x m на прямоугольную матрицу B размера m x n. В главной программе обратиться к этой функции.
3. Написать функцию вычисления суммы ряда s=s(1)+…+s(n),
где s(n)=(-1)n x(2n-1)/(2n+1) с точностью до eps=0.001. В качестве параметров выбрать x и eps.
4. Написать функцию, которая вычисляет для заданной квадратной матрицы A её симметричную часть S(ij)=(A(ij)+A(ji))/2 и кососимметричную часть K(ij)=(A(ij)-A(ji))/2.
5. Написать функцию “шапочка” f(x), зависящую от параметров a и b: если |x| >a то f(x)=0 иначе f(x)=b*exp(-a2/(a2-|x|2)). В качестве параметров передать a,b,x.
6. Написать функцию поиска максимального и минимального элементов одномерного массива. В основной программе вызвать эту функцию для двух разных массивов.
7. Написать функцию, которая сортирует одномерный массив в порядке убывания методом пузырька. В основной программе вызвать эту функцию для двух разных массивов.
8. Написать функцию, которая по двум заданным одномерным массивам (A размера m и B размера n) вычисляет максимальное значение двумерного массива c(ij)=a(i)*b(j).
9. Написать функцию определителя квадратной матрицы A размера 3x3:
detA=a(1,1)a(2,2)a(3,3)+a(3,1)a(1,2)a(2,3)+a(2,1)a(3,2)a(1,3)-a(3,1)a(2,2)a(1,3)-a(1,1)a(3,2)a(2,3)-a(2,1)a(1,2)a(3,3).
10. Написать функцию вычисления суммы ряда y=sinx-(sin2x)/2+…
+(-1)n+1sin(nx)/n с точностью до eps=0.001. В качестве параметров передать x (в радианах) и eps.
11. Написать функцию вычисления ряда y=x+x3/3!+…+x2n+1/(2n+1)! с точностью до eps=0.0001. В качестве параметров передать x и eps.
12. Написать функцию обработки матриц A и B одинакового размера m x n. Получить матрицу C =max(a(i,j),b(i,j)), и матрицу D=min(a(i,j),b(i,j)). Матрицы C и D вывести в главной программе.
4. КОНТРОЛЬНЫЕ ВОПРОСЫ
4.1. Описание функции. Для чего объявляется прототип?
4.2. Что такое формальные и фактические параметры? Локальные и глобальные?
4.3. Как можно передавать массив в функцию?
4.4. Способы вызова функций.
Лабораторная работа № 7
Рекурсии
1. ЦЕЛЬ РАБОТЫ: Изучение методов использования алгоритмов и программ с рекурсиями в языке Си.
2. ОСНОВНЫЕ СВЕДЕНИЯ
В языке Си функции могут вызывать сами себя, т.е. обладать свойством рекурсивности. Рекурсивная функция обязательно должна содержать в себе условие окончания рекурсивности, чтобы не вызвать зацикливания программы. При каждом рекурсивном вызове создается новое множество локальных переменных. Т.о. переменные, расположенные вне вызываемой функции, не изменяются.
Пример. Составить рекурсивную функцию, вычисляющую факториал числа n следующим образом: n!= 1, если n<= 1 и n!= (n -1)! · n, если n > 1
long fact(int n)
{ if (n <=1) return l;
else return (n * fact (n -1)); // функция fact вызывает саму себя
}
Таким образом, последовательно вызываются функции f(n), f(n-1),f(n-2)…f(1).
Достоинством рекурсий является компактная запись, а недостатком – расход времени и памяти на повторные вызовы функции и передачу ей копий параметров.
3. ВЫПОЛНЕНИЕ РАБОТЫ
Составить алгоритмы и программы с использованием рекурсии в соответствии с вариантом задания.
Варианты заданий
1. Ввести с клавиатуры целое число N. Используя рекурсию, распечатать сначала последовательность, состоящую из N букв 'А', а затем из N букв 'В'.
2. Напечатать в обратном порядке последовательность чисел, признаком конца которой является 0.
3. Водится любое целое число b и вещественные a, c. Вычислить z=a b +c b, используя рекурсивную функцию x n 1, если n = 0
x n = 1/ x n, если n < 0
x × x n-1, если n > 0
4. Для N=12 найти числа Фибоначчи, которые вычисляются следующим образом: F(0)=1, F(1)=2, F(N)=F(N-2)+F(N-1)
5. Методом деления отрезка пополам найти с точностью EPS=0,0001 корень уравнения cos(2/x)-2*sin(1/x)+1/x=0
6. Даны целые числа m и n, где 0<=m<=n. Вычислить рекурсивно число сочетаний по формуле:
7. Дана последовательность положительных чисел, признаком конца которых служит отрицательное число. Используя рекурсию, подсчитать количество чисел и их сумму.
8. Дана последовательность ненулевых целых чисел, признаком конца которых служит 0. Используя рекурсию, напечатать сначала все отрицательные, а потом – все положительные числа этой последовательности.
9. Дан вектор Х из N вещественных чисел. Найти минимальный элемент вектора, используя вспомогательную рекурсивную функцию, находящую минимум среди последних элементов вектора Х, начиная с N-го.
10. Дана строка символов, в конце которой стоит точка. Напечатать строку в обратном порядке.
11. Задан вещественный массив из N. Упорядочить его по возрастанию методом быстрой сортировки: выбрать средний элемент массива и переставить элементы так, чтобы слева от выбранного элемента были меньшие, а справа только большие (т.о. выбранный элемент окажется на окончательном месте). Затем применить этот способ рекурсивно к левой и правой части массива.
12. Имеется 10 населенных пунктов. Дана последовательность пар чисел пар чисел I и J (I<J), указывающих, что I –ый J-ый пункты соединены дорогой. Признак конца этой последовательности - пара нулей. Используя рекурсию, определить, можно ли по этим дорогам попасть из 1-го пункта в N-ый.
4. КОНТРОЛЬНЫЕ ВОПРОСЫ
4.1. Что такое рекурсия?
4.2. Как меняются локальные и глобальные переменные в рекурсиях?
4.3. Где находится окончание рекурсии?
Лабораторная работа № 8
|
|
|
