lab12 (Готовые ЛР и ДЗ (ИУ5))
Описание файла
Файл "lab12" внутри архива находится в следующих папках: Готовые ЛР и ДЗ (ИУ5), задания. Документ из архива "Готовые ЛР и ДЗ (ИУ5)", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "lab12"
Текст из документа "lab12"
Лабораторная работа 12
Обработка и печать числовой матрицы.
Задание. Создать квадратную матрицу A размером N*N (где n вводится с клавиатуры), имеющую элементы A i,j = 1 / (j!)I . В зависимости от размера матрицы обеспечить удобное для пользователя отображение матрицы на экране.
Цели работы:
- создание двухмерных динамических массивов;
- обработка матриц;
- демонстрация технологии структурного программирования на примере программы сортировки строк матрицы;
- использование файлов для хранения исходных данных;
- форматированный вывод матриц на экран.
Прежде чем программировать задание, разберите и выполните приведенный в работе пример.
Создание двухмерных динамических массивов.
В динамической области памяти можно создавать двумерные массивы с помощью операции new или функции mаllос. Остановимся на первом варианте, поскольку он более безопасен и прост в использовании.
Обращение к элементам динамических массивов производится точно так же, как к элементам «обычных», с помощью конструкции вида a[i ][j].
Универсальный способ выделения памяти под двумерный массив, когда обе его размерности задаются на этапе выполнения программы, приведен ниже:
int nrow, ncol;
cout << " Введите количество строк и столбцов :";
cin >> nrow >> ncol;
int **a = new int *[nrow]; // 1
for(int i = 0; i < nrow; i++) // 2
a[i] = new int [ncol]; // 3
Для того чтобы понять, отчего динамические массивы описываются именно так, нужно разобраться в механизме индексации элемента массива. Поскольку для доступа к элементу массива применяется две операции разъименования, то переменная, в которой хранится адрес начала массива, должна быть указателем на указатель.
В операторе 1 объявляется переменная типа «указатель на указатель на int » и выделяется память под массив указателей на строки массива (количество строк — nrow). В операторе 2 организуется цикл для выделения памяти под каждую строку массива. В операторе 3 каждому элементу массива указателей на строки присваивается адрес начала участка памяти, выделенного под строку двумерного массива. Каждая строка состоит из ncol элементов типа int (рис. 1).
Освобождение памяти из-под массива с любым количеством измерений выполняется с помощью операции delete [].
Рис. 1. Схема динамической области памяти, выделяемой под массивы
Программа сортировки строк матрицы.
Написать программу, которая упорядочивает строки прямоугольной целочисленной матрицы по возрастанию сумм их элементов.
Давайте на этом примере формализуем общий порядок создания структурной программы, которому мы ранее следовали интуитивно. Этого порядка полезно придерживаться при решении даже простейших задач
I. Исходные данные, результаты и промежуточные величины. Как уже неоднократно упоминалось, начинать решение задачи необходимо с четкого описания того, что является ее исходными данными и результатами и каким образом они будут представлены в программе.
Исходные данные. Поскольку размерность матрицы неизвестна, придется использовать динамический массив элементов целого типа. Ограничимся типом int, хотя для общности следовало бы воспользоваться максимально длинным целым типом.
Результаты. Результатом является та же матрица, но упорядоченная. Это значит, что нам не следует заводить для результата новую область памяти, а необходимо упорядочить матрицу на том же месте. В данной задаче такое требование может показаться излишним, но в общем случае, когда программист работает в команде и должен передавать результаты коллеге, это важно. Представьте себе ситуацию, когда коллега думает, что получил от вас упорядоченную матрицу, а на самом деле вы сформировали ее в совершенно другой области памяти.
Промежуточные величины. Кроме конечных результатов, в любой программе есть промежуточные, а также служебные переменные. Следует выбрать их тип и способ хранения.
Очевидно, что если требуется упорядочить матрицу по возрастанию сумм элементов ее строк, эти суммы надо вычислить и где-то хранить. Поскольку все они потребуются при упорядочивании, их надо записать в массив, количество элементов которого соответствует количеству строк матрицы, а i-й элемент содержит сумму элементов i-й строки. Количество строк заранее неизвестно, поэтому этот массив также должен быть динамическим. Сумма элементов строки может превысить диапазон значений, допустимых для отдельного элемента строки, поэтому для элемента этого массива надо выбрать тип 1ong.
После того как выбраны структуры для хранения данных, можно подумать и об алгоритме (именно в таком порядке, а не наоборот — ведь алгоритм зависит от того, каким образом представлены данные).
II. Алгоритм работы программы. Для сортировки строк воспользуемся одним из самых простых методов — методом выбора. Он состоит в том, что из массива выбирается наименьший элемент и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом и так далее n - 1 раз. Одновременно с обменом элементов массива выполняется и обмен значений двух соответствующих строк матрицы.
Алгоритм сначала записывается в самом общем виде (например, так, как это сделано выше). Пренебрегать словесным описанием не следует, потому что процесс формулирования на естественном языке полезен для более четкого понимания задачи. При этом надо стремиться разбить алгоритм на простую последовательность шагов. Например, любой алгоритм можно первоначально разбить на этапы ввода исходных данных, вычислений и вывода результата.
Вычисление в данном случае состоит из двух шагов: формирование сумм элементов каждой строки и упорядочивание матрицы. Упорядочивание состоит в выборе наименьшего элемента и обмене с первым из рассматриваемых. Разветвленные алгоритмы и алгоритмы с циклами полезно представить в виде обобщенной блок-схемы.
Когда алгоритм полностью прояснился, можно переходить к написанию программы. Одновременно с этим продумываются и подготавливаются тестовые примеры. Не ленитесь придумать переменным понятные имена и сразу же при написании аккуратно форматировать текст программы, чтобы по положению оператора было видно, на каком уровне вложенности он находится. Функционально завершенные части алгоритма отделяются пустой строкой, комментарием или хотя бы комментарием вида
//-------------------------------------------------------------
При написании программы рекомендуется всегда включать в нее промежуточную печать вычисляемых величин в удобном для восприятия формате. Это простой и надежный способ контроля хода выполнения программы.
Не нужно стремиться написать сразу всю программу. Сначала пишется и отлаживается фрагмент, содержащий ввод исходных данных. Затем промежуточную печать можно убрать и переходить к следующему функционально законченному фрагменту алгоритма. Для отладки полезно выполнять программу по шагам с наблюдением значений изменяемых величин. Все популярные оболочки предоставляют такую возможность
Ниже приведен текст программы сортировки.
#include <fstream.h>
#include <iomanip.h>
//using namespace std;
int main()
{
ifstream fin("input.txt", ios::in);
if (!fin)
{ cout <<" Файл input.txt не найден " << endl;
return 1;
}
int nrow,ncol;
fin>>nrow>>ncol; // ввод размерности массива
int i, j;
int **a = new int *[nrow]; // выделение памяти под массив
for(i = 0; i < nrow; i++)
a[i] = new int [ncol];
for (i = 0; i < nrow; i++) // ввод массива
for (j = 0; j < ncol; j++)
fin >> a[i][j];
long *sum = new long [nrow]; // массив сумм элементов строк
for (i =0; i < nrow; i++)
{
sum[i] = 0;
for (j = 0; j < ncol; j++) sum[i] += a[i][j];
}
for (i = 0; i < nrow; i++)
{ // контрольный вывод
for (j = 0; j < ncol; j++)
cout << setw(4) << a[i][j] << " ";
cout << "| " << sum[i] << endl;
}
cout << endl;
long buf_sum;
int nmin, buf_a;
for (i = 0; i < nrow - 1; i++) // упорядочивание
{
nmin = i;
for (j = i + 1; j < nrow; j++)
if (sum[j] < sum[nmin]) nmin = j;
buf_sum = sum[i];
sum[i] = sum[nmin];
sum[nmin] = buf_sum;
for (j = 0; j < ncol; j++)
{
buf_a = a[i][j];
a[i][j] = a[nmin][j];
a[nmin][j] = buf_a;
}
}
for (i = 0; i < nrow; i++)
{ // вывод упорядоченной матрицы
for (j = 0; j < ncol; j++) cout <<setw(4) << a[i][j] << " ";
cout << endl;
}
return 0;
}В программе используются две буферные переменные: buf_sum, через которую осуществляется обмен двух значений сумм, имеет такой же тип, что и сумма, а для обмена значений элементов массива определена переменная buf_a того же типа, что и элементы массива.
Как и в предыдущем примере, данные читаются из файла. Мы рекомендуем пользоваться именно этим способом, а не стандартным вводом, поскольку при формировании файла легче продумать, какие значения лучше взять для исчерпывающего тестирования программы. В данном случае для первого теста следует подготовить массив не менее чем из четырех строк с небольшими значениями элементов для того, чтобы можно было в уме проверить, правильно ли вычисляются суммы.
Ввод размерности массива и его элементов выполняется из файла input.txt, расположенного в том же каталоге, что и программа, а результаты выводятся в файл output. txt. В программе определены объект f i n класса входных файловых потоков и объект fout класса выходных файловых потоков. Файловые потоки описаны в заголовочном файле <fstream.h>. Работа с этими объектами аналогична работе со стандартными объектами cin и cout, то есть можно пользоваться теми же операциями помещения в поток << и извлечения из потока >>.
Предполагается, что файл с именем input.txt находится в том же каталоге, что и текст программы, иначе следует указать полный путь, дублируя символ обратной косой черты, так как иначе он будет иметь специальное значение:
ifstream fin("c:|\\A_Worker\\input.txt". ios::in | ios::nocreate);
Обратите внимание, что для контроля вместе с исходным массивом рядом с каждой строкой выводится сумма ее элементов, отделенная вертикальной чертой.
Дополнительно следует проверить, правильно ли упорядочивается массив из одной и двух строк и столбцов, поскольку многие ошибки при написании циклов связаны с неверным указанием их граничных значений.
Давайте повторим основные правила работы с двухмерными массивами.
-
В массивах, определенных с помощью операторов описания, обе размерности должны быть константами или константными выражениями.
-
Массив хранится по строкам в непрерывной области памяти.
-
Первый индекс всегда представляет собой номер строки, второй — номер столбца. Каждый индекс может изменяться от 0 до значения соответствующей размерности, уменьшенной на единицу.
-
При описании массива можно в фигурных скобках задать начальные значения его элементов.
-
При выделении динамической памяти сразу под весь массив самую левую размерность можно задавать с помощью переменной, все остальные размерности должны быть константами. Для двумерного массива это означает, что первая размерность может быть константой или переменной, а вторая — только константой.
-
Для выделения динамической памяти под массив, в котором все размерности переменные, используются циклы.
-
Освобождение динамической памяти из-под массива с любым количеством измерений выполняется с помощью операции del ete [ ].
Ниже в сжатом виде приведены рекомендации по порядку создания программы.
-
Выбрать тип и способ хранения в программе исходных данных, результатов и промежуточных величин.
-
Записать алгоритм сначала в общем виде, стремясь разбить его на простую последовательность шагов, а затем детализировать каждый шаг.
-
Написать программу. При написании программы рекомендуется:
-
давать переменным понятные имена;
-
не пренебрегать содержательными комментариями;
-
использовать промежуточную печать вычисляемых величин в удобном формате;
-
при написании вложенных циклов следить за отступами;
-
операторы инициализации накапливаемых в цикле величин задавать непосредственно перед циклом, в котором они вычисляются.
4. Параллельно с написанием программы задать тестовые примеры, которые проверяют все ветви алгоритма и возможные диапазоны значений исходных данных. Исходные данные удобнее формировать в файле (по крайней мере, при отладке), не забывая проверять в программе успешность его открытия.