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

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

Постановка

Задача

требуется?

дано?

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

Решение

Задача

исходное ® способ ® результаты

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

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

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

Решение на ЭВМ

Задача

Программа

данные ® ЭВМ ® результаты

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

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

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

Составление программ

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

¯ ¯

сценарий   ® алгоритмы
¯                       ¯
ЭВМ    ¬ программа
Приведенная схема представляет основной принцип систематических методов составления алгоритмов и программ для решения различных прикладных задач - экономических, математических, физических, инженерных и т. д.
Особенностью систематических методов является возможность полного устранения ошибок из алгоритмов и программ. При этом подходе программы сверяются с описаниями алгоритмов, а алгоритмы - с описаниями сценариев и методов решения.
Такой систематический подход к составлению алгоритмов и программ может применяться к решению на ЭВМ любых прикладных задач с использованием самых различных языков программирования - Бейсик, Паскаль, Си и им подобные. Приведем примеры систематического решения задач.
Первая задача: подсчет площади треугольника по длинам сторон.

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 чисел х1, х2, ..., хN. Приведем постановку, метод решения и сценарий диалога для решения этой задачи.
Постановка задачи                                                                     Сценарий

Дано: N - количество чисел, среднее N чисел
x1, х2, .., хN - числа, чисел =? <N>

Треб.: s - среднее N чисел.                                                                                        *
Где: s = (х1, + х2 +...+ хN )/ N.                                                               1: <х1>
При: N > 0.                                                                                         2: <х2>
………..
Метод решения                                                                                 N: <хN>

S0 = 0 среднее = <s>

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

       s = SN / 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 строк:
фамилия                    рост                            вес

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

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

Дано: (D1, ..., DN) - данные учеников. Данные об учениках
где D = [Fam, R,V] - состав данных, фамилия вес

Fam - фамилия, R - рост, V -вес
Треб.: Famm
- фамилия ученика.                                                                  <Fam1> <V1>                *
Где: m: Vm = Min (V1
..., VN).                                                                               … …
При: N > 0.                                                                                                     <FаmN> <VN>

Метод решения                                                                                             самый легкий:
Min (V1,.. Vn):                                                                                                Fam m > <Vm >
min = V1
от k = 1 до п цикл                                                                             Представление данных
если Vk < min то                                                                                dan: 'данные учеников:
min: = Vk                                                                                             data «Иванов», «Вова», 180,80
кцикл                                                                                                  data «»,»»,0 ,0
Выбранному сценарию, методу решения и представлению данных соответствуют следующие алгоритм и программа на Бейсике.

Алгоритм                                                                              Программа
алг «самый легкий ученик»                                                            ' самый легкий ученик
нач                                                                                          cls
вывод («Данные об учениках»)                                        ? «Данные об учениках»
вывод («фамилия вес»)                                                       ? «фамилия вес»
N: = 0                                                                                    n = 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
В общем случае систематический подход к решению задач на ЭВМ требует для проверки правильности алгоритмов и программ не только математической постановки задач, но и обязательного описания выбранных методов решения.

Систематический подход:
задача              ®    способы
¯                               ¯
постановка    ®     методы
¯                               ¯
сценарий          ®     алгоритмы
¯                                ¯
ЭВМ                ¬       программа
Рассмотрим пример систематического составления алгоритма и программы для решения на ЭВМ достаточно сложной задачи обработки данных.
Четвертая задача: Определить суммы элементов столбцов в матрице Anxm:

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

Дано:                                                                          Матрица <N>´<M>
(a11 … a1N)                                                                   < a11> ... < a1N >
(... ... ... ) - матрица Anxm                                              ... ... ...
(aMl
… aMN)                                                                 < aMl > … < aMN
>
Треб.:                                                                          Суммы элементов:
(S1
..., SN) - суммы столбцов                                     <S1> ... <SN>
Где:

      Si
= аi1 + ...+ аiM
      [i = (1… N)]
При: N > 0, М > 0.
Метод вычислений                                     Представление данных

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

       sk1 = ak1
+ sk1-1                                           data 3, 4
       [1 = (1 ... M)]                                           data I, 2, 3, 4
   Sk = SkN                                                        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. Для последовательности чисел х1, х2 ..., хN приведите постановку задачи, составьте сценарий, алгоритм решения и программу:
а) подсчета суммы всех чисел;
б) вычисления среднего арифметического чисел;
в) определения наибольшего из чисел;
г) определения наименьшего из чисел.
4. Для данных об учениках, содержащих сведения об их росте и весе, приведите постановку задачи, составьте сценарий, алгоритм и программу определения:
а) самого высокого ученика;                                   г) самого легкого ученика;
б) самого низкого ученика;                      д) средний рост учеников;
в) самого тяжелого ученика;                    е) средний вес учеников.
5. Для данных о днях рождения своих друзей и родных приведите постановку задачи, составьте сценарий, алгоритм решения и программу:
а) определения ровесников;
б) определения людей, родившихся в один день;
в) самого молодого из своих друзей и родных;
г) самого старшего из своих родных и друзей.

Содержание раздела