 |
 |
 |
 |
|
 |
 |
95
г) подсчет членов геометрической прогрессии.
2. Для последовательности чисел х1, х2,..., х
N
, приведите постановку, алгоритм решения и разбор правильно-
сти следующих задач:
а) подсчет суммы всех чисел;
б) вычисление среднего арифметического чисел;
в) определение наибольшего из чисел;
г) определение наименьшего из чисел.
3. Для данных о росте и весе учеников приведите постановку задачи, алгоритм решения и разбор правильно-
сти для следующих задач:
а) нахождение самого высокого ученика;
г) нахождение самого легкого ученика;
д) нахождение среднего роста учеников;
е) нахождение суммарного веса учеников.
4. Для прямоугольной матрицы Anm приведите постановку, алгоритм решения и разбор правильности сле-
дующих задач:
а) подсчет сумм элементов матрицы по столбцам;
в) нахождение минимального значения в каждом столбце;
е) нахождение максимального значения в каждой строке;
ж) нахождение наибольшего из минимальных значений в столбцах;
з) нахождение наименьшего из максимальных значений в строках.
5. Для N точек на плоскости, заданных случайным образом, приведите постановку, метод решения, сценарий,
алгоритм и программу решения следующих задач:
а) найти точку, наиболее удаленную от центра координат;
б) соединить пару наиболее удаленных точек;
в) найти три точки, образующие треугольник с наибольшим периметром;
г) найти три точки, образующие треугольник с наибольшей площадью.
5.5. Решение сложных задач
Большинство практических задач обработки данных относится к числу сложных. Слож-
ность задач оценивается сложностью обрабатываемых данных и сложностью алгоритмов их ре-
шения. Сложность данных обычно оценивается их количеством. Сложность алгоритмов оценива-
ется объемом вычислений, необходимых для получения требуемых результатов.
При решении сложных задач, требующих составления сложных алгоритмов, особенно ска-
зываются преимущества доказательного программирования. Для этого программы решения слож-
ных задач составляются из вспомогательных алгоритмов и подпрограмм, решающих более про-
стые подзадачи.
Анализ правильности сложных алгоритмов и программ распадается на анализ правильно-
сти каждого из вспомогательных алгоритмов и на анализ правильности программ в целом. Необ-
ходимым условием для этого является составление спецификаций для каждого из вспомо-
гательных алгоритмов и каждой подпрограммы,
При таком подходе доказательство правильности сложных алгоритмов и программ под-
разделяется на доказательство ряда лемм о правильности вспомогательных алгоритмов и подпро-
грамм и доказательство правильности программ в целом.
В качестве иллюстрации рассмотрим две задачи, которые можно отнести к сложным про-
блемам обработки данных. Для каждой из этих задач приведем спецификации, алгоритмы и дока-
зательства правильности.
Первая задача: упорядочение массивов данных. Пример, для чисел 3, 7, 9, 1,
4 упорядо-
ченная последовательность имеет вид: 1, 3, 4, 7, 9.
Существует несколько способов и методов упорядочения массивов и последовательностей.
Простейший из них называется методом «пузырька».
Метод «пузырька» состоит в нахождении в массиве наименьшего числа и перестановке
его на первое место. Это как бы «пузырек», поднимающийся к началу массива. Затем в остатке
массива находится наименьшее число, которое перемещается на второе место, и так далее - до ис-
черпания всего массива.
Для рассматриваемых чисел метод «пузырька» дает следующие перестановки:
исходные числа:
3, 7, 9, 1, 4.
перестановка1:
1, 7, 9, 3, 4.