В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
6.5. Примеры решения задач Для иллюстрации возможности применения функций рассмотрим несколько задач. ПРИМЕР Даны три матрицы A N×M , B K×L и C R×H найти произведение их максимальных элементов. Для начала, как обычно, составим тестовый пример: Вход: 1 3 5 3 8 1 0 2 8 11 2 10 A , 4 2 4 5 7 0 1 2 4 3 9 10 B , 2 5 1 4 C 11 MaxA 10 MaxB 5 MaxC Выход: 550 P MaxA MaxB MaxC Итак, для решения задачи необходимо ввести матрицу А, матрицы В и C, найти максимальный элемент матрицы А, матрицы В, матрицы D; вычислить произведение найденных максимумов P и вывести его на экран. 195 Очевидно, что для решения понадобятся функция ввода матрицы и функция поиска максимального элемента матрицы. Решение задачи начинается с составления блок-схем процедур. На этом этапе необходимо определить наборы формальных параметров и способы их передачи для каждой функции, так как эти данные указываются в первом блоке блок-схемы. Назовем функцию ввода матрицы словом Vvod. Для работы этой функции понадобятся матрица и ее размерность (число строк и столбцов). При этом все три параметра должны передаваться как параметры- переменные. Для корректного ввода в функцию передадим также буквенное обозначение матрицы, для чего воспользуемся переменной Mname символьного типа. Чтобы не было коллизии имен между формальными и фактическими параметрами, назовем формальную матрицу X, а ее размерности – Y, Z. Функция поиска максимального элемента пусть будет Maximum. Для функции, собственно, матрица и ее размерность будут входными параметрами, а значение максимального элемента – выходным. Таким образом, здесь будет использован набор из четырех формальных параметров, три из которых будут передаваться как параметры-константы, а один – как параметр-переменная. Переменные i, j, используемые в качестве переменных в циклах- счетчиках – чисто локальные, так как их значения носят вспомогательный характер и нужны только в пределах функций для перебора элементов матрицы. Затем составляется блок-схема основной программы (рис. 6.9, а), функций ввода (рис. 6.9, б) и поиска максимума (рис. 6.10). 196 При вызове функций используются три набора фактических параметров: первый – для матрицы A, второй – для матрицы B, третий – для матрицы C. Наборы фактических параметров соответствуют набору формальных параметров по количеству, типу, порядку следования и способу передачи. В функцию Vvod сначала передается матрица A, ее размерности N, M и буква ‘A’, затем матрица B, ее размеры K, L и буква ‘B’; после этого идет третий вызов процедуры, на этот раз уже с матрицей C, ее размерностью R, H и названием ‘C’ в качестве фактических параметров. Распространенная ошибка – передавать все двенадцать параметров в одном блоке. Начало Конец Vvod(A, N, M, ‘A’) Maximum(A, N, M, MaxA) Vvod(B, K, L, ‘B’) Maximum(B, K, L, MaxB) P:= MaxA*MaxB*MaxC Вывод P void Vvod(Int x[10][15], int &y, int &z, char Mname) Выход i=0; i Ввод x[i][j] б) а) Vvod(C, R, H, ‘C’) Maximum(C, R, H, MaxC) Рис. 6.9. Основная программа и функция ввода матрицы 197 Функция Maximum также должна вызываться трижды, но чтобы не потерять значение максимального элемента матрицы A, нужно при вызове функции взять три различные переменные: MaxA, MaxB и MaxC для максимальных элементов матриц A, B и C соответственно. Для того чтобы найти произведение максимальных элементов, дополнительную функцию использовать не нужно, так как действие будет производиться один раз. При этом переменная P будет глобальной, поскольку она используется в основной программе. Последний этап решения задачи – составление программы по полученной блок-схеме. Следует учесть, что поскольку по условию матрицы разного размера, то для их описания необходимо использовать число строк и столбцов, которое удовлетворило бы размеры всех трех матриц. Можно взять, например, размеры 10 на 15. #include X[i][j] > max void Maximum(const int x[10][15], int y, int z, int &max) Выход i=0; i max = x[0][0] j=0; j 198 void vvod(int x[10][15], int &y, int &z, char name) { cout<<”\nInput count of rows”; cin< } } void maximum(const int x[10][15], int y, int z, int &max) { int max=x[0][0]; for (int i=0; i } int main() { int a[10][15], b[10][15], c[10][15], n, m, k, l, r, h; vvod(a,n,m,’A’); vvod(b,k,l,’B’); vvod(c,r,h,’C’); int maxA, maxB, maxC; maximum(a,n,m,maxA); maximum(b,k,l,maxB); maximum(c,r,h,maxC); int P=maxA*maxB*maxC; cout<<”\nP=”< } Теперь решим ту же задачу, но только используя для поиска максимума функцию, которая вернет его значение, поскольку именно функция лучше подходит для решения, так как от каждой матрицы надо получить, по сути, одно единственное число. Блок-схема несколько изменится. Поменяется основная программа (рис. 6.11, а) и изменится функция поиска максимума (рис. 6.11, б). Блок-схема ввода матрицы останется прежней (рис. 6.10, а). 199 Программа может быть записана следующим образом: #include { cout<<”\nInput count of rows”; cin< } } int maximum(const int x[10][15], int y, int z) { int max=x[0][0]; x[i][j] > max int maximum(const int x[10][15], int y, int z) Выход i=0; i max = x[0][0] j=0; j Конец Vvod(A, N, M, ‘A’) P:= Maximum(A, N, M)* *Maximum(B, K, L)* *Maximum(C, R, H) Vvod(B, K, L, ‘B’) Вывод P а) return max б) Vvod(C, R, H, ‘C’) Рис. 6.11. Решение задачи с помощью функции возвращающей не void 200 for (int i=0; i } int main() { int a[10][15], b[10][15], c[10][15], n, m, k, l, r, h; vvod(a,n,m,’A’); vvod(b,k,l,’B’); vvod(c,r,h,’C’); int P=maximum(a,n,m)*maximum(b,k,l)*maximum(c,r,h); cout<<”\nP=”< } Далее решим такую задачу: ПРИМЕР Даны две матрицы A Na×Na и B Nb×Nb ; найти сумму отрицательных элементов в каждой из матриц и заменить ей минимальный элемент на главной диагонали в противоположной матрице. Входные данные: 3 3 2 6 5 3 3 1 4 2 4 A , 4 4 2 0 1 3 5 6 7 4 8 1 2 0 11 3 6 10 B Промежуточные данные: SA=–13, SB= – 22 IminA = JminA=1; IminB= JminB=2. Выходные данные: 22 6 5 3 3 1 4 2 4 A , 2 0 1 3 5 13 7 4 8 1 2 0 11 3 6 10 B Для решения задачи вводим матрицы А и В, находим сумму отрицательных элементов SA и SB в каждой из них, координаты 201 минимальных элементов на главной диагонали (IminA и IminB) и далее, зная эти координаты, заменяем минимальные элементы полученными суммами в перекрестном порядке. Решение задачи начинается с составления блок-схемы основной программы и блок-схем функций. Сначала мы формируем общую последовательность выполнения алгоритма, набор и порядок вызова необходимых функций. Нужно определиться с набором входных и выходных данных для каждой функции. На основе этого выбираем формальные параметры и способы их передачи. Далее детализируем алгоритм работы каждой функции в отдельности. Полученная блок-схема основной программы показана на рис. 6.12. Следует отметить, что перед модификацией матриц выводим их на экран для того, чтобы иметь возможность проверить корректность введенных данных. Кроме того, дополнительный вывод позволяет наглядно представить исходные значения и потому достаточно легко самостоятельно убедиться в правильности промежуточных и выходных данных. Использование Начало Конец Vvod(A, Na, ‘A’) SA = Summa(A, Na) Vvod(B, Nb, ‘B’) SB = Summa(B, Nb) IminA = IM(A, Na) IminB = IM(B, Nb) Vivod(A, Na, ‘A’) Vivod(B, Nb, ‘B’) A[IminA, IminA] =SB B[IminB, IminB] =SA Vivod(A, Na, ‘A’) Vivod(B, Nb, ‘B’) Рис. 6.12. Основная программа 202 функций для решения задачи позволяет производить достаточно сложное действие по выводу двумерного массива всего одной строкой. void vvod(int x[10][10], int &n, char mname) Выход i=0; i Ввод x[i][j] а) void vivod(const int x[10][10], int n, char mname) Выход i=0; i б) Рис. 6.13. Ввод и вывод квадратной матрицы Замена минимального элемента – одно действие, поэтому для него дополнительную функцию не создаем. Функции ввода и вывода двумерного массива достаточно стандартны. Единственное отличие будет в том, что матрицы в данной задаче квадратные, значит, в качестве размерности достаточно передавать количество строк. Для поиска индекса минимального элемента воспользуемся функцией IM (рис. 6.14), передадим в нее матрицу и размерность, как параметры-константы. Результат работы функции Imin – значение индекса минимального элемента главной диагонали матрицы. Для поиска нужен только один цикл, так как индекс строки элементов главной диагонали совпадает с номером столбца. 203 Для поиска суммы отрицательных элементов воспользуемся функцией Summa (рис. 6.15), передадим в нее матрицу и ее размерность, так как они изменяться не будут, то передавать их будем как параметры- константы. x[i][i] < x[imin][imin] int IM(const int x[10][10], int n) Выход i=0; i return imin Рис. 6.14. Поиск минимума в квадратной матрице 204 Теперь составим программу: #include { cout<<”\nInput count of rows and columns”; cin< } } int IM(const int x[10][15], int n) { int imin=0; for (int i=0; i int summa (const int x[10][10], int n) Выход i=0; i S = 0 j=0; j Рис. 6.15. Сумма отрицательных элементов 205 int summa (const int x[10][15], int n) { int s=0; for (int i=0; i { cout<<”\nMatrix ”< } int main() { int a[10][10], b[10][10], na, nb; vvod(a,na,’A’); vvod(b,nb,’B’); int sa=summa(a,na); int sb=summa(b,nb); int iminA=IM(a,na); int iminB=IM(b,nb); vivod(a,na,’A’); vivod(b,nb,’B’); a[iminA,iminA]=sb; b[iminb][iminb]=sb; vivod(a,na,’A’); vivod(b,nb,’B’); } 206 7. ФАЙЛЫ 7.1. Основные определения и объявление файла Достаточно часто при решении тех или иных задач средствами ЭВМ возникает потребность в хранении и обработке больших объемов однотипных данных. Можно попытаться воспользоваться массивами. Однако это не всегда удается в силу того, что при обработке массивы хранятся в оперативной памяти, которая имеет относительно небольшой объем, а потому бывает нецелесообразно помещать их туда целиком. Кроме того, оперативная память в большинстве ЭВМ не обладает свойством энергонезависимости. Это означает, что при выключении питания компьютера несохраненная информация теряется. В качестве одного из методов решения вышеобозначенной проблемы были предложены так называемые файлы. Файл – именованная область на внешнем информационном носителе (диске), содержащая данные. Особенностью С++ является отсутствие в этом языке структурированных файлов. Все файлы рассматриваются как не структурированная последовательность байтов. При таком подходе понятие файла распространяется и на различные устройства. Одни и те же функции используются как для обмена данными с файлами, так и для обмена с устройствами. Библиотека Си поддерживает три уровня ввода-вывода: - потоковый ввод-вывод; - ввод-вывод нижнего уровня; - ввод-вывод для консоли портов (зависит от конкретной ОС). На уровне потокового ввода-вывода обмен данными производится побайтно, т. е. за одно обращение к устройству (файлу) производится 207 считывание или запись фиксированной порции данных. При вводе с диска или при считывании из файла данные помещаются в буфер ОС, а затем побайтно или порциями передаются программе пользователя. При выводе в файл данные также накапливаются в буфере, а при заполнении буфера записываются в виде единого блока на диск. Буферы ОС реализуются в виде участков основной памяти. Т.о. поток – это файл вместе с предоставленными средствами буферизации. Функции библиотеки Си, поддерживающие обмен данными на уровне потока позволяют обрабатывать данные различных размеров и форматов. При работе с потоком можно: 1. Открывать и закрывать потоки (при этом указатели на поток связываются с конкретными файлами); 2. Вводить и выводить строки, символы, форматированные данные, порции данных произвольной длины; 3. Управлять буферизацией потока и размером буфера; 4. Получать и устанавливать указатель текущей позиции в файле. Прототипы функций ввода-вывода находятся в заголовочном файле , который также содержит определения констант, типов и структур, необходимых для обмена с потоком. Таблица 7.1 Сравнение файлов и массивов Тип Скорость обработки Возможный Размер Энергонезависимость файлы Медленно Огромный Есть массивы Быстро Малый Отсутствует Прежде, чем начать работать с потоком, его надо инициировать, т. е. открыть. При этом поток связывается со структурой предопределенного 208 типа FILE, определение которой находится в файле FILE*f; //указатель на поток Указатель на поток приобретает значение в результате выполнения функции открытия потока: FILE* fopen(const char*filename,const char*mode); где const char*filename – строка, которая содержит имя файла, связанного с потоком (допустима как абсолютная так и относительная адресация), const char*mode – строка режимов открытия файла. ПРИМЕР f=fopen(“t.txt”,”r”); здесь t.txt – имя файла, r – режим открытия файла. Поток можно открывать в текстовом (t) или двоичном режиме (b). В текстовом режиме поток рассматривается как совокупность строк, в конце каждой строки находится управляющий символ ‘\n’. В двоичном режиме поток рассматривается как набор двоичной информации. Текстовый режим устанавливается по умолчанию. В файле stdio.h определена константа EOF, которая сообщает об окончании файла (отрицательное целое число). Файл связанный с потоком можно открыть в одном из 6 режимов (таблица 7.2). При открытии потока могут возникать следующие ошибки: - файл, связанный с потоком не найден (при чтении из файла); - диск заполнен (при записи); 209 - диск защищен от записи (при записи) и т. п. В этих случаях указатель на поток приобретет значение NULL (0). Указатель на поток, отличный от аварийного не равен 0. Таблица 7.2 Режимы открытия файла Режим Описание режима открытия файла R Файл открывается для чтения, если файл не существует, то выдается ошибка при исполнении программы. w Файл открывается для записи, если файл не существует, то он будет создан, если файл уже существует, то вся информация из него стирается. a Файл открывается для добавления, если файл не существует, то он будет создан, если существует, то информация из него не стирается, можно выполнять запись в конец файла r+ Файл открывается для чтения и записи, изменить размер файла нельзя, если файл не существует, то выдается ошибка при исполнении программы. w+ Файл открывается для чтения и записи, если файл не существует, то он будет создан, если файл уже существует, то вся информация из него стирается. a+ Файл открывается для чтения и записи, если файл не существует, то он будет создан, если существует, то информация из него не стирается, можно выполнять запись в конец файла Для вывода об ошибке при открытии потока используется стандартная библиотечная функция из файла Эта функция выводит строку символов, на которую указывает указатель s, за этой строкой размещается двоеточие пробел и сообщение 210 об ошибке. Текст сообщения выбирается на основании номера ошибки. Номер ошибки заносится в переменную int errno (определена в заголовочном файле errno.h). После того как файл открыт, в него можно записывать информацию или считывать информацию, в зависимости от режима. Открытые файлы после окончания работы рекомендуется закрыть явно. Для этого используется функция: int fclose(FILE*f); Изменить режим работы с файлом можно только после закрытия файла. |