Лекции по информатики 2 (стр. 23 из 43)

= (-b +

)²/(4×а) + b× (-b + )/(2×a) + с = (b + )× (-b + )/(4×а) + с =

= (-b² + D)/(4×a) + с = (-b² + b² - 4×а×с)/(4×а) + с = -4×а×с/(4×а) + с = 0.

Аналогичные результаты получаются и при подстановке формулы второго корня

х₂ = (-b -

)/(2×a). После выполнения аналогичных преобразований будет получено такое же тождество. И на основании этих проверок можно сделать заключение, что рассмотренный метод дает правильные результаты для любык допустимых данных.

Однако саму постановку задачи необходимо дополнить условием: b² - 4×а×с ³ 0. При нарушении этого условия не только уравнение не имеет решений, но и метод решения также не дает результатов из-за необходимости вычисления корней от отрицательного дискриминанта: D < 0.

В силу выбранного метода решения и принятой постановки алгоритм решения квадратных уравнений приобретает следующий вид:

алг «квадратное уравнение»Результаты вычислений

нач

если а ¹ О топри а ¹ 0

D:= b*b - 4*а*с D = b² - 4×а×с

если D > = 0 топри D >= 0

х1: = (-b+

)/(2*a)х1 = (-b +

)/(2×a)

х2: = (-b -

)/(2*a)х2 = (-b -

)/(2×a)

все

инеc а = 0 топри а = 0

если b¹ 0при b ¹ 0

х 1: = -c/b xl = -c/b

все

кон

Результаты выполнения алгоритма приведены справа. Можно заметить, что результаты выполнения совпадают с описанием выбранного метода решения с помощью дискриминанта. Это позволяет утверждать, что алгоритм - правильный.

Алгоритм содержит ошибки, если можно указать допустимые исходные данные, при которых либо будут получены неправильные результаты, либо результаты не будут получены вовсе. Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.

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

Первый способ - проверка основных этапов построения алгоритма:

задача ® постановка ® метод ® алгоритм

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

задача ¬ постановка ¬ метод ¬ алгоритм

Приведем пример построения алгоритма с одновременным анализом его правильности.

Задача: Определить периметр треугольника, заданного на плоскости координатами вершин.

X_С,У_С

X_А,У_АXв,Ув

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

Определение периметра треугольника, заданного на плоскости.

Дано: А = (Х_А, У_А)

В= (Х_В, У_В) - координаты вершин треугольника

С = (X_С,У_С)

Треб.: Р - периметр

Метод решения

Р = L_АВ +L_ВС+L_СА

L_АВ =

L_ВС=

L_СА=

Где: Р = L(A,B) + L(B,C) + L(C,A);

здесь L[(x,y),(u,v)] =

.

Приведем алгоритм, полученный из описания метода упорядочением операций вычисления длин сторон треугольника с завершающим вычислением периметра. Результаты выполнения алгоритма приведены справа.

алг «периметр треугольника»

нач

LAB: =

LBC : =

LCA : =

Р := LAB + LBC + LCA

кон

Результаты

Р = LAB + LBC + LCA

Сравнение результатов выполнения алгоритма с описанием метода решения показывает, что это одна и та же система формул, что подтверждает правильность алгоритма.

Систематические методы анализа правильности алгоритмов и программ опираются на сопоставление тех же самых описаний, которые используются при их систематическом составлении.

Анализ правильности:

задача ¬ способ

¯¯

постановка ¬ методы

¯¯

сценарий ¬ алгоритмы

¯¯

ЭВМ ® программа

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

· ошибки в выбранных методах решения;

· ошибки в постановке решаемых задач;

· дефекты в сценариях диалога с ЭВМ;

· ошибки организации ввода данных;

· неправильная реализация методов решения.

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

Будем считать, что программа правильная, если она дает правильные результаты для любых допустимых исходных данных. Такого рода программы вполне можно использовать для решения прикладных задач.

Программа считается надежной, если она не дает сбоев и отказов ни при каких исходных данных. Надежность - обязательное условие для всех программ, которые используются людьми для решения практических задач на ЭВМ.

В качестве иллюстрации приведем пример систематического составления алгоритма и программы задачи определения суммарного веса учеников по данным из таблицы:

фамилия рост вес

Иванов	185	85
Петрова	165	65
Сидоров	170	80

Рассмотрим постановку задачи и метод вычисления суммарного веса.

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

Определение суммарного веса.

Дано:Метод вычисления

(D₁,.., D_N) - данные об учениках, S₀= 0

где D = [Fam,R,V] - состав данных, S_k = S_k-1 + v_k

Fam - фамилия, R - рост, V - вес. [k = (1 ... N)]

Треб.: V_sum - суммарный вес. V_sum = S_N

V_sum = v₁ + v₂ + ... + v_N

При: N > 0.

Правильность метода вычислений можно доказать по индукции. Рассмотрим результаты вычислений на 1-м, 2-м и k-м шагах. Отметим, что начальное значение S₀ = 0.

На первом шаге при k = 1 результат вычисления

S₁ = S₀+v₁ = v₁

На следующем втором шаге при k = 2 результат

S₂= S₁ + v₂= v₁+ v₂.

На третьем шаге при k = 3 результат

S₃= S₂ + v₃= v₁ + v₂+ v₃.

В общем случае можно предположить, что к k-му шагу результат вычисления

S_k-1=v₁+...+v_k-1.

Тогда результат вычислений после k-го шага (исходя из описания метода)

S_k = S_k-1 +v_k= v₁ + … + v_k-1 + v_k.

В силу принципа математической индукции утверждение верно для всех k = 1, 2,.... N. Следовательно, на последнем шаге при k = N конечный результат:

S_N= v₁ + ... + v_N.

Что и требовалось. Следовательно, метод правильный.

Приведем сценарий диалога решения поставленной задачи на ЭВМ. Для представления данных в программе примем последовательность операторов data.

Сценарий Представление данных

Данные об учениках

фамилия вес рост

dano:'данные учеников