А д а ч и

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, 7, 9, 3, 4.

перестановка₂: 1, 3, 9, 7, 4.

перестановка₃: 1, 3, 4, 7, 9. упорядочено.

Приведем точную математическую постановку задачи.

Поиск по сайту: