Написать программу, которая упорядочивает строки прямоугольной целочисленной матрицы по возрастанию сумм их элементов.
I. Исходные данные, результаты и промежуточные величины.
Исходные данные. Поскольку размерность матрицы неизвестна, придется использовать динамический массив элементов целого типа. Ограничимся типом
int.
Результаты. Результатом является та же матрица, но упорядоченная. Это значит, что не следует заводить для результата новую область памяти, а необходимо упорядочить матрицу in situ, то есть на том же месте.
Промежуточные величины. Кроме конечных результатов, в любой программе есть промежуточные, а также служебные переменные. Следует выбрать их тип и способ хранения.
Если требуется упорядочить матрицу по возрастанию сумм элементов ее строк, эти суммы надо вычислить и где-то хранить. Поскольку все они потребуются при упорядочивании, их надо записать в массив, количество элементов которого соответствует количеству строк матрицы, а i-й элемент содержит сумму элементов i-й строки. Количество строк заранее неизвестно, поэтому этот массив также должен быть динамическим. Сумма элементов строки может превысить диапазон значений, допустимых для отдельного элемента строки, поэтому для элемента этого массива надо выбрать тип 1ong.
II. Алгоритм работы программы. Для сортировки строк воспользуемся одним из самых простых методов - методом выбора. Он состоит в том, что из массива выбирается наименьший элемент и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом и так далее п - 1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива). Одновременно с обменом элементов массива выполняется и обмен значений двух соответствующих строк матрицы.
Любой алгоритм можно первоначально разбить на этапы ввода исходных данных, вычислений и вывода результата.
Вычисление в данном случае состоит из двух шагов: формирование сумм элементов каждой строки и упорядочивание матрицы. Упорядочивание состоит в выборе наименьшего элемента и обмене с первым из рассматриваемых. Разветвленные алгоритмы и алгоритмы с циклами полезно представить в виде обобщенной блок-схемы.
III. Когда алгоритм полностью прояснился, можно переходить к написанию программы. Одновременно с этим продумываются и подготавливаются тестовые примеры. Рекомендуется придумать переменным понятные имена и сразу же при написании аккуратно форматировать текст программы, чтобы по положению оператора было видно, на каком уровне вложенности он находится. Функционально завершенные части алгоритма отделяются пустой строкой, комментарием или хотя бы комментарием.
Сначала пишется и отлаживается фрагмент, содержащий ввод исходных данных. Затем можно переходить к следующему функционально законченному фрагменту алгоритма. Для отладки полезно выполнять программу по шагам с наблюдением значений изменяемых величин. Все популярные оболочки предоставляют такую возможность. Ниже приведен текст программы сортировки.
Листинг 6.4
#include <fstream.h>
#include <iomanip.h>
int main()
{
setlocale(LC_ALL, "Russian");
ifstream fin(“input.txt”, ios:: in | ios:: nocreate);
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 того же типа, что и элементы массива.
Как и в предыдущем примере, данные читаются из файла. Рекомендуется пользоваться именно этим способом, а не стандартным вводом, поскольку при формировании файла легче продумать, какие значения лучше взять для исчерпывающего тестирования программы. В данном случае для первого теста следует подготовить массив не менее чем из четырех строк с небольшими значениями элементов для того, чтобы можно было в уме проверить, правильно ли вычисляются суммы.
Для контроля вместе с исходным массивом рядом с каждой строкой выводится сумма её элементов, отделенная вертикальной чертой.
В качестве второго тестового примера рекомендуется ввести значения элементов массива, близкие к максимальным для типа int. Дополнительно следует проверить, правильно ли упорядочивается массив из одной и двух строк и столбцов, поскольку многие ошибки при написании циклов связаны с неверным указанием их граничных значений.
Рекомендации по порядку создания программы.
1. Выбрать тип и способ хранения в программе исходных данных, результатов и промежуточных величин.
2. Записать алгоритм сначала в общем виде, стремясь разбить его на простую последовательность шагов, а затем детализировать каждый шаг.
3. Написать программу. При написании программы рекомендуется:
- давать переменным понятные имена;
- не пренебрегать содержательными комментариями;
- использовать промежуточную печать вычисляемых величин в удобном формате;
- при написании вложенных циклов следить за отступами;
- операторы инициализации накапливаемых в цикле величин задавать непосредственно перед циклом, в котором они вычисляются.
4. Параллельно с написанием программы задать тестовые примеры, которые проверяют все ветви алгоритма и возможные диапазоны значений исходных данных. Исходные данные удобнее формировать в файле (по крайней мере, при отладке), не забывая проверять в программе успешность его открытия.