Глава 5. Технология решения задач

 

Решение задач на ЭВМ

 

Решение задач должно начинаться с их точной постановки. Постановка задач — это четкое выделение того, что требуется, и того, что дано:

 

 

Следующий этап — определение способа решения задачи. Способ решения — это набор действий, позволяющих получить требуемое из исходного:

 

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

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

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

 

 

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

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

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

 

 

Приведенная схема представляет основной принцип систематических методов составления алгоритмов и программ для решения различных прикладных задач — экономических, математических, физических, инженерных и т. д.

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

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

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

 

 

 

Постановка

Дано: а, b, с — длины сторон.

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

При: a > 0, b > 0, с > 0,

a < b + c, b < a + c, c < a + b.

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

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

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

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

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

нач сls

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

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

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

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

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

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

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

инес не (а < b + с и b < а + c 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:= 0 S = 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 строк:

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

Иванов
Петрова
Сидоров

 

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

Дано: (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: = 0 n = 0

цикл do

чтение (Fam, r, v) read fam, 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

 

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

 

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

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

¯ ¯

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

¯ ¯

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

¯ ¯

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

 

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

Четвертая задача: Определить суммы элементов столбцов в матрице A_nxm:

 

 

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

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

Дано: Матрица <N>´<M>

(a₁₁ … a_1N) < a₁₁>... < a_1N >

(.........) - матрица Anxm.........

(a_Ml … a_MN) < a_Ml > … < a_MN >

Треб.: Суммы элементов:

(S₁..., S_N) - суммы столбцов <S₁>... <S _N >

Где:

S_i = а_i1 +...+ а_iM

[i = (1… N)]

При: N > 0, М > 0.

 

Метод вычисленийПредставление данных

sk0 = 0 matr: ' матрица Anm:

s_k1 ⁼ a_k1⁺ s_k1-1 data 3, 4

[1 = (1... M)] data I, 2, 3, 4

S_k = S_kN data 0, 1, 2, 3

[k = (1... N)] data 0, 0, 1, 2

 

В предлагаемой ниже программе для представления матриц ис­пользуются операторы data. В первом из этих операторов записаны размеры, а в каждом последующем операторе - строки матрицы:

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

алг «сумма строк матрицы» ' сумма строк матрицы

нач cls

чтение (п, т) read n, m

если п > 0 и т > 0 то if N > 0 and М > 0 then

массив А[1:п,1:т] dim A (N,M)

массив S[1:n] dim S(n)

ввод-вывод_матрицы gosub vvod 'ввод-матрицы

суммирование_строк gosub sum 'суммирование

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

выв (s[k])? s[k]

кцикл next k

все end if

кон end

 

алг «суммирование строк» sum: 'суммирование строк

нач ' нач

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

s[k]:= 0 s[k] = 0

от l = 1 до М цикл for I = 1 to m

s[k]:= s[k] + A[k,l] s[k] = s[k] + a[k,l]

кцикл next I

кцикл next k

кон return

 

алг «ввод-вывод_матрицы» vvod: 'ввод-вывод_матрицы

нач ' нач

вывод («Матрица», N, «х», М)? «Матрица»; m; «х»; m

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

от I = 1 до М цикл for l = 1 to m

чтение (A [k,l]) read A (k,l)

вывод (A [k,l])? A (k,l)

кцикл next 1

нов_строка?

кцикл next k

кон return

 

Вопросы

1. Что такое постановка задачи?

2. Что включается в постановку задач?

3. Что такое способ решения?

4. Что такое метод решения?

5. Каков порядок решения новых задач?

6. Что такое систематическая разработка алгоритмов и программ?

 

Задачи

1. Приведите постановку задачи, сценарий, алгоритм и программу подсчета сумм:

а) нечетных чисел;

б) квадратов целых чисел;

в) кубов целых чисел.

2. Приведите постановку задачи, сценарий, алгоритм и программу подсчета сумм:

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

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

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

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

б) вычисления среднего арифметического чисел;

в) определения наибольшего из чисел;

г) определения наименьшего из чисел.

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

а) самого высокого ученика; г) самого легкого ученика;

б) самого низкого ученика; д) средний рост учеников;

в) самого тяжелого ученика; е) средний вес учеников.

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

а) определения ровесников;

б) определения людей, родившихся в один день;

в) самого молодого из своих друзей и родных;

г) самого старшего из своих родных и друзей.