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

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

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

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

a b

c

Постановка Сценарий

Дано: а, b, с - длины сторон, площадь треугольника

Треб.: S - площадь треугольника, длины сторон:

При: а > 0, b > 0, с > 0, а =? <а>

a < b +c, b < a + c, c < a + b. b =? <b>

с =? <с>

Метод решенияплощадь = <S>

S = недопустимы длины

р = (а + b + с)/2

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

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

Алгоритм Программа

алг «площадь треугольника»' площадь треугольника

начcls

вывод («площадь треугольника»)? «площадь треугольника»

вывод («длины сторон:»)? «длины сторон:»

запрос («а=», a) input«a=», a

запрос («b=», b) inpnt «b=», b

запрос («с=», с) input «c=», c

если не (а > 0 и b > 0 и с > 0) то if a<=0 or b<=0 or c<=0 then

вывод («недопустимы длины»)? «недопустимы длины»

инеc не (а < b + с и b < а + elseif not (a < b+ с and b < а + с

+с и с<а+b)то and с < а + b) then

вывод («недопустимы длины») ? «недопустимы длины»

иначе else

р := (а + b + с)/2 р = (а+ b +с)/2

S :=

S = sqr (p*(p-a)*(p-b)*(p-c))

вывод («площадь=», S) ? «площадь=», S

все end if

кон end

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

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

1) дано: перечень исходных данных;

2) треб: перечень требуемых данных;

3) где: требования к результатам;

4) при: условия допустимости данных.

Вторая задача: определение среднего арифметического последовательности из N чисел х₁,х₂, ..., х_N. Приведем постановку, метод решения и сценарий диалога для решения этой задачи.

Постановка задачиСценарий

Дано: N - количество чисел, среднее N чисел

x₁, х₂, .., х_N - числа, чисел =? <N>

Треб.: s - среднее N чисел. *

Где: s = (х₁, + х₂ +...+ х_N)/ N. 1: <х₁>

При: N > 0. 2: <х₂>

………..

Метод решения N:<х_N>

S₀ = 0 среднее = <s>

S_k= S_k-1+ х_k

[k = 1, ..., N]недопустимо N

s = S_N / N

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

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

АлгоритмПрограмма

алг «среднее арифметическое»' среднее арифметическое

нач cls

вывод («среднее N чисел»)? «среднее N чисел»

запрос («чисел=», N) input «чисел=», N

S := 0S = 0

если N <= 0 то if N <= 0 then

вывод («недопустимо N»)? «недопустимо N»

инеc N > 0 то elseif N > 0 then

от k = 1 до N цикл for k = 1 to N

вывод (k, «:»)? k, «:»

запрос (x) input x

S :=S + x S = S + x

кцикл next k

s :=S/N s = S/N

вывод («среднее =», s)? «среднее=», s

все end if

кон end

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

Приведем пример разработки программы обработки данных с математической постановкой задачи и полным описанием метода решения.

Третья задача: определение самого легкого из учеников по данным из таблицы, содержащей N строк:

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

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

Постановка задачиСценарий

Дано: (D₁, ..., D_N) - данные учеников. Данные об учениках

где D= [Fam, R,V] - состав данных, фамилия вес

Fam - фамилия, R - рост, V -вес

Треб.: Fam_m - фамилия ученика. <Fam₁> <V₁> *

Где:m: V_m = Min (V₁ ..., V_N). … …

При: N > 0. <Fаm_N> <V_N>

Метод решениясамый легкий:

Min (V1,.. Vn): Fam m > <Vm >

min = V₁

от k = 1до п циклПредставление данных

если V_k < min то dan: 'данные учеников:

min: = V_k data «Иванов», «Вова», 180,80

кцикл data«»,»»,0 ,0

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

АлгоритмПрограмма

алг «самый легкий ученик»' самый легкий ученик

нач cls

вывод («Данные об учениках»)? «Данные об учениках»

вывод («фамилия вес») ? «фамилия вес»

N: = 0n = 0

цикл do

чтение (Fam, r, v) read famS, r, v

при Fam = «» выход if fam$ = «» then exit do

вывод (Fam, v)? fam$, v, r

N:=N+1 n = n+1

если N == 1 или V < Vmin то if n=l or v < vmin then

Vmin: = V vmin = v

Fmin: = Fam fmin$ = fam$

все end if

кцикл loop

вывод («самый легкий:»)? «самый легкий:»

вывод (Fmin, Vmin) ? fmin$, vmin

кон end

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

Систематический подход:

задача ® способы

¯¯

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

¯¯

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

¯¯

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

Рассмотрим пример систематического составления алгоритма и программы для решения на ЭВМ достаточно сложной задачи обработки данных.