Лекция: Процедурный подход к разработке программ

В качестве примера рассмотрим следующую задачу.

Имеется числовая матрица размера n на m. Необходимо вывести на экран индексы всех седловых точек. Седловой точкой является элемент матрицы со значением минимальным в строке и максимальным в столбце, в котором находится элемент, или наоборот – максимальным в строке и минимальным в столбце.

Общий план решения этой задачи может быть, например, таким:

1. Подготовка данных для решения задачи.

2. Решение задачи и вывод результатов.

В соответствии с этим планом, разбиваем задачу на две соответствующие подзадачи, и для их реализации используем две соответствующие функции. И вот первый вариант будущей программы:

#include «stdafx.h»

#include <iostream>

using namespace std;

const int n = 5, m = 5; // n — количество строк, m — количество столбцов матрицы

int A[n][m]; // А — исходная матрица

void Подготовка_данных()

{

}

void Решение_и_вывод_результатов()

{

}

int _tmain(int argc, _TCHAR* argv[])

{

Подготовка_данных();

Решение_и_вывод_результатов();

system(«Pause»);

return 0;

}

Теперь можно перейти к последовательной реализации каждой из этих функций.

Для подготовки исходных данных необходимо:

1. заполнить массив A некоторыми данными и

2. вывести содержимое матрицы на экран, для того чтобы в дальнейшем проконтролировать правильность решения задачи.

Реализуем эти действия также с помощью соответствующих функций:

void Заполнение_массива()

{

}

void Вывод_массива()

{

}

void Подготовка_данных()

{

Заполнение_массива();

Вывод_массива();

}

Для заполнения данными матрицы воспользуемся датчиком случайных чисел, сама процедура заполнения двумерного массива значениями настолько проста, что дальнейшей детализации не требует:

void Заполнение_массива()

{

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

A[i][j] = rand() % 3; // Генерация сл. чисел в диапазоне [0, 2]

}

Здесь мы заполнили матрицу значениями 0, 1 и 2. При таких значениях элементов матрицы легче получить матрицу, содержащую седловые точки.

Вывод значений двумерного массива на экран также не должно вызывать затруднений:

void Вывод_массива()

{

for (int i = 0; i < n; ++i)

{

for (int j = 0; j < m; ++j)

cout << setw(4) << right << A[i][j];

cout << endl;

}

}

Вывод значений матрицы мы оформили в виде таблицы. Для задания ширины каждого столбца этой таблицы использован манипулятор вывода setw. Для использования этого манипулятора необходимо включить заготовочный файл iomanip.

Теперь мы получили следующую программу:

#include «stdafx.h»

#include <iostream>

#include <iomanip>

using namespace std;

const int n = 5, m = 5; // n — количество строк, m — количество столбцов матрицы

int A[n][m]; // А — исходная матрица

void Заполнение_массива()

{

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

A[i][j] = rand() % 3;

}

void Вывод_массива()

{

for (int i = 0; i < n; ++i)

{

for (int j = 0; j < m; ++j)

cout << setw(4) << right << A[i][j];

cout << endl;

}

}

void Подготовка_данных()

{

Заполнение_массива();

Вывод_массива();

}

void Решение_и_вывод_результатов()

{

}

int _tmain(int argc, _TCHAR* argv[])

{

Подготовка_данных();

Решение_и_вывод_результатов();

system(«Pause»);

return 0;

}

Если запустить эту программу на выполнение, на экран будет выведена матрица, содержащая 5 строк и 5 столбцов с элементами, значения которых принадлежат диапазону [0, 2] .

Переходим к реализации функции Решение_и_вывод_результатов(). Общий алгоритм работы этой функции: необходимо выполнить проверку каждого элемента исходной матрицы – является ли этот элемент седловой точкой. Если проверяемый элемент является седловой точкой, то вывести на экран значения индексов этого элемента. Если проверяемый элемент не является седловой точкой, то перейти к проверке следующего элемента.

Перебор элементов матрицы можно выполнить с помощью двух вложенных циклов.

Предположим, что имеется функция bool Это_седловая_точка(int i, int j), которая возвращает значение true, если элемент матрицы А [i] [j] является седловой точкой. Тогда реализация функции Решение_и_вывод_результатов()будет выглядеть так:

void Решение_и_вывод_результатов()

{

cout << endl;

int Счетчик = 0; // Счетчик седловых точек

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

if (Это_седловая_точка(i, j))

{

cout << setw(4) << i << setw(4) << j << endl;

++ Счетчик;

}

cout << "\nКоличество седловых точек: " << Счетчик << endl;

}

Реализуем функцию Это_седловая_точка. Для того чтобы определить является ли элемент матрицы с индексами i и j седловой точкой, необходимо знать минимальное и максимальное значения в строке с индексом i значения, а также минимальное и максимальное значения в столбце с индексом j. Допустим, что у нас имеются четыре функции: