Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


А д а ч и




1. Приведите постановку, алгоритм решения и разбор правильности для следующих задач:

а) подсчет суммы целых чисел;

б) подсчет суммы нечетных чисел;

в) подсчет членов арифметической прогрессии;

г) подсчет членов геометрической прогрессии.

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.

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

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

 

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

Постановка задачи

Упорядочение последовательности чисел.

Дано: x1, х2, ..., хN - исходные числа.

Треб.: x1', x2', ..., хN' - упорядоченные числа.

Где: х1' £ х2' £ ... £ хN'.

При: N > 0.

Упорядочение чисел по методу «пузырька» в общей форме имеет вид:

Способ «упорядочение чисел»

нач

от k=1 до N-1 цикл

хтп := xk

imn := k

от i=k+1 до N цикл

если xi < хтп то

хтп := xi

imn : = i

кесли

кцикл

xmn = Min (хk, ..., хN)

xk' = хтп

ximn ' = xk

кцикл хk¢ = Min (хk, ..., хN)

кон x1 < х2 < ... < хk¢

 

Приведенный алгоритм можно рассматривать как алгоритм, сло­женный из нескольких фрагментов - вспомогательных алгоритмов, решающих определенные подзадачи.

Первый фрагмент (внутренний цикл) решает подзадачу нахожде­ния минимального значения в подмассиве x[k:N]. Второй фрагмент решает подзадачу перемещения k-го минимального значения на k-e место в массиве.

Лемма 1. Для вспомогательного алгоритма

алг «поиск минимума»

Нач

хтп := xk

imn := k

от i = k + 1 до N цикл

если xi < хтп то

хтп := xi

imn := i

Кесли

кцикл { xmn = Min (хk, ..., х1) }

Кон

конечным результатом вычислений будет значение

xmn = Min (хk, ..., хN).

Доказательство. Применим индуктивную схему рассуждений. Первое присваивание дает

xmnk = xk.

Далее на первом шаге цикла при i = k + 1 будет получен минимум первых двух чисел:

xk+1 при xk+1 < xmnk,

xmnk+l =

xmnk при xk+1 ³ xmnk.

На втором шаге цикла будет получен минимум первых трех чисел:

xmnk+2 = min (xk+2, min (хk+1, хk)) = Min (хk+2, хk+1, хk).

Теперь можно утверждать, что на третьем и последующих шагах цикла результатом будет минимальное значение среди чисел xk , ..., xi

хmni = Min (хk, ..., хi).

Данное утверждение доказывается с помощью математической индукции. На первых двух шагах при i = k + 1, k + 2 оно уже уста­новлено. Покажем, что оно будет выполняться на (i + 1)-м шаге. Действительно, на следующем шаге цикла результатом будет:

xi+1 при хi+1 < xmni = min(xi+1, хmni)

хmni+1 =

хmni при хi+1 ³ хmni = min(xi+1, xmni)

= min (xi+1, Min (хk , ..., хi)) = Min (хk, ..., хi, xi+1).

Что и требовалось показать. Следовательно, в силу принципа мате­матической индукции конечным результатом выполнения рассмат­риваемого цикла будет значение:

xmnN = Min (xk, ..., хN)

Что и требовалось доказать.

Лемма 2. Для вспомогательного алгоритма

алг «перестановки»

нач { xmn = Min (хk, ..., хN) }

xi¢mn= xk

Кон

конечным результатом будет значение хk' = Min (хk, ..., хN).

Доказательство.В силу леммы 1 xmn = Min (xk, ..., хN). А так как в этом алгоритме хk' = xmn, то в итоге получим

хk' = xmn = Min (хk, ..., хN).


Поделиться:

Дата добавления: 2014-11-13; просмотров: 80; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты