Конспект лекций по программированию для начинающих. Гладков В.П. - 44 стр.

                                        46

   Расставим скобки в программируемом выражении так, чтобы отразить
порядок его выполнения: ((a+b)-c). Заменим внутренние скобки командой
робота, получим: (сум(a,b)-c). Заменим внешние скобки соответствующей
командой робота: раз(сум(a,b),c). Значения переменных должны быть введены,
поэтому заменим их соответствующей командой. Получим: раз(сум(?(),?()),?()).
Наконец, для вывода результата добавим соответствующую команду и
законченная программа будет иметь вид: !(раз(сум(?(),?()),?())).
   Другой вариант программы можно получить следующим образом.
Расставляем скобки: (a+(b-c)). Операции в полученном выражении
последовательно заменяем командами робота:
   (a+раз(b,c))
   сум(a,раз(b,c))
   сум(?(),раз(?(),?()))
   !(сум(?(),раз(?(),?()))).
   Заметим, что программа для нахождения значения выражения
a+b+c+d=(((a+b)+c)+d) будет иметь вид сум(сум(сум(a,b),c),d). Программы, в
которых при вычислениях команды обращаются сами к себе прямо или
косвенно, называются рекурсивными. О них речь пойдет далее.
   В дальнейших примерах будем считать, что все необходимые данные
введены и расположены в памяти робота в переменных, именами которых
являются буквы латинского алфавита.
   Пример 8.9. Составим для Кибика программу для вычисления значения
            a +b
выражения        − c . Здесь исходными данными являются числа a, b и c. В
              2
результате получаем число. Расставим в заданном выражении скобки,
отражающие порядок его вычисления (((a+b)/2)-c). Заменим каждую пару
скобок, начиная с внутренних, соответствующими командами робота.
Последовательно получаем программу для робота. Заменяем сумму -
((сум(a,b)/2)-c), заменяем деление на 2 - (пол(сум(a,b))-c), заменяем разность -
раз(пол(сум(a,b)),c).
    Программу, решающую эту же задачу, можно было получить из формулы:
a/2+b/2-c. Тогда последовательно получаем (((a/2)+(b/2))-c). Заменяем a/2 -
((пол(a)+(b/2))-c), заменяем b/2 - ((пол(a)+пол(b))-c), заменяем сумму -
(сум(пол(а),пол(b))-c), заменяем разность - раз(сум(пол(а),пол(b)),c).

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