Программирование на ЭВМ

    Пусть P(n) – некоторое проверяемое условие.

    Схема метода математической индукции:

1. непосредственной подстановкой проверяем, что P(n₀)  выполняется;
2. предполагаем, что P верно для некоторого n=k, k≥n₀;
3. доказываем, что из предположения п.2) следует, что P будет верно для n=k+1.

    Пример.

    Докажем, что вычисление по рекуррентной последовательности

    f (0) = 1,

    f (n) = f (n-1)*n,

 где  n>0, даст в результате значение f(n)=n!.   

1. f (0) =1  0! = 1 - выполняется.
2. предполагаем, что f (k) = k!
3. убедимся, что из п.2 следует f (k+1) = (k+1)!

Действительно, f (k+1) = f (k)*(k+1) = k!*(k+1) = (k+1)!, что и требовалось доказать.

    Для циклических алгоритмов под величиной  n обычно понимают количество повторений цикла. В частном случае оно может быть равно нулю.

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

        n = 0. D ≤ Eps. Цикл не работает ни разу. Сравним пред- и постусловия. Они отличаются именно на это неравенство. Непосредственной проверкой мы убедились, что при n =0 предусловие переходит в постусловие.

        Предположим, что цикл проработал  k раз (n = k ≥ 0), после чего постусловие стало истинным.

        Положим n = k +1. Докажем истинность постусловия.

    Так как цикл проработал на 1 раз больше k, то после k выполнений цикла еще сохранялось условие D>Eps, а часть постусловия совпадала с предусловием:

          (f (C-D)*f (C+D)≤0) AND (D>0) AND (Eps>0)   (***)

    После (k+1)-го выполнения цикла условие (***) сохраняется (доказали методом перечисления). И, кроме того, так как цикл после (k+1)-го раза больше работать не будет, то должно выполниться D ≤ Eps. Таким образом получили (после k +1-го шага):

          (D ≤ Eps) AND (***) – совпадает с заданным постусловием.

    Ценность  методов верификации состоит  в том, что мы получаем доказательство правильности для всего комплекса допустимых значений данных. При этом успех методов зависит от того, насколько правильно и полно мы задали пред- и постусловия.

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

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

     Например, отрицательный  интервал d в программе поиска корней функции. Или функция, которая не имеет корня (рис. 1.5).

        

Рис. 1.5 – Пример функции, не имеющей корня 

    Для избежания таких ошибок целесообразен следующий подход.

    На  входе программы делаются специальные  проверки на правильность данных. Затем либо выдаётся сообщение о том, что данные неверны, либо проводятся вычисления. Схема такой проверки выглядит следующим образом.

    IF  данные верны

    THEN выполнить алгоритм

    ELSE выдать сообщение о неправильности данных.

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

    1.7. Процедуры и функции

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

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

    Процедура – автономно выделенный алгоритм, который можно использовать как в разных местах одной программы, так и в разных программах.

    Различают две разновидности процедур.

    Процедуры,  вычисляющие  одно    значение.   Их   называют    процедурами-функциями или просто функциями. Стандартные (встроенные) функции присутствуют в любом языке: ABS(X), SQR(X), SQRT(X) и т.д. Имена функций используются в выражениях.

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

    Процедуры и функции в Паскале оформляются  как соответствующие описания. Эти описания располагаются в программе в разделе определения данных после описания переменных. Пользоваться процедурой в Паскале можно только внутри той программы,  в которой она определена.

    Описание  процедуры (функции) состоит из заголовка  и тела процедуры.

       

    Функция:

    FUNCTION <имя> (<список переменных и типов>): <тип>;

    <описание внутренних (локальных) переменных>;

      BEGIN

          --------------

          --------------

          <имя> :=<значение>;

          END;

    В заголовке функции обязательно  должно присутствовать служебное слово FUNCTION и после списка переменных (аргументов) – тип самой функции, то есть тип возвращаемого ею значения. Переменные в заголовке функции называются формальными параметрами (ФРП). Это аргументы функции. Локальные переменные – это те, которые нужны для организации вычислительного процесса в самой процедуре и не являются ее входами.

    Пример.

    FUNCTION Y (x, z : REAL):REAL;

    BEGIN

          Y := x * x + z * z;

    END;

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

    A := Y (25.5, T);

    B := 2*Y(C, D) / (Y (3.2, 2.7)+1);

    Те  значения, которые используются при  вызове процедуры-функции, называются фактическими параметрами (ФКП). Ими могут быть константы, переменные (их значения должны быть определены к моменту вызова процедуры-функции), выражения, имена некоторых других функций.

    Формальные  и фактические параметры обязательно должны совпадать по количеству и по типу.

    Входом  алгоритма процедуры-функции является список параметров, выходом – вырабатываемое его значение.

        Процедура:

    PROCEDURE <имя>(<список параметров и их типов>);

    <описание внутренних переменных>;

    BEGIN

    --------------

    --------------

    END;

    Особенность процедуры состоит в том, что  как ее вход, так и выход  определяются непосредственно списком формальных параметров. Часть из них входные, часть – выходные. Запись их в списке ФРП несколько различается. Дело в том, что ФРП могут быть нескольких разновидностей:

    а) параметры-значения.

    Для них в списке ФРП указывается: <список имен>:<имя типа>. По окончании работы процедуры их значения утрачиваются. Поэтому для выходных переменных такой тип непригоден;

    б) параметры-переменные.

    Для них в списке ФРП предусмотрена конструкция:

          VAR <список имен> : <имя типа>.

    К этой разновидности относятся выходные переменные;

      в) параметры-функции и параметры-процедуры. 
 

    Описываются в списке следующим образом:

    FUNCTION <имя> (<список имен и типов>):<имя типа>

    или

          PROCEDURE <имя> (<список имен и типов>)

    Пример. Процедура обмена значениями между двумя переменными.

    PROCEDURE OB (VAR X,Y : REAL);

    VAR Z: REAL;

    BEGIN

          Z:=X; X:=Y; Y:=Z;

    END;

    Для того чтобы использовать в программе  процедуру (вызвать ее), существует так называемый оператор процедуры. Его структура: <имя процедуры> (<список ФКП>). Принципиальное отличие от вызова функции – место оператора процедуры в программе. Он записывается в последовательности инструкций как полноправный оператор, например,

    A:=2.5; B:=3*(C-D/2);

    OB(A, B);

    После вызова переменные А и В поменяются значениями. Смысл понятий ФРП и ФКП для процедуры тот же, что и для функции.

    Замечание.  Процедуры или функции могут вообще не иметь формальных параметров.

    При использовании процедур или процедур-функций общая схема программы:

          PROGRAM …;

          Описания переменных

          Описания процедур

          BEGIN

          -------------

          END.

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

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

    Пусть нужно вычислить сумму: , (где f – некоторая функция), описав вычисления как процедуру-функцию. Описание функции:

          FUNCTION SUM (A, B : INTEGER; FUNCTION F (I :INTEGER): REAL): REAL;

          VAR I :INTEGER; S: REAL;

          BEGIN

                S:=0;

                FOR I:=A TO B DO

                      S:=S+F(I);

                SUM:=S;

          END;

    Для того чтобы  использовать функцию  SUM, нужно описать функцию f(i). Пусть . Тогда возможно следующее описание функции:

          FUNCTION T (I: INTEGER): REAL;

          BEGIN

                T:=1/I/I

          END;

    Для вычисления конкретной суммы, например ,  в основной программе используем оператор

          Z:= SUM (1, 10, T);  или

    Z1:= SUM (1, N, T1); где T1 – другая функция, например Т1= .

    В одной программе может быть много  разных вызовов функции со своими конкретными ФКП.

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

          TYPE proc = PROCEDURE (список ФРП и типы);

          TYPE func = FUNCTION (список ФРП и типы): тип функции;

    Обязательное  правило: программа при использовании данных процедурного типа должна компилироваться с ключом {$F+}.

    Программа для нашего примера.

    PROGRAM SUMMA;

    VAR W: INTEGER; Z1, Z2: REAL;

    TYPE func = FUNCTION (I: INTEGER): REAL;