7. Подпрограми. Видове подпрограми в Pascal. Параметри на подпрограмите. Подпрограма процедура. Подпрограма функция. Локални и глобални величини в програмите. Предварително деклариране на подпрограма. Ползване на готови библиотеки от подпрограми. Рекурсия.
Дефиниция 7.1
Подпрограма е част от програмата, в която се отделя някакво логически обособено действие. Подпрограмите се описват само веднъж и към тях се обръщат от много места в главната програма или в подпрограмите. 

Възможно е една подпрограма да вика себе си, което се нарича рекурсия. В Pascal една подпрограма може да има собствени подпрограми, т. е. получава се йерархия от подпрограми, което съответства на инженерния подход нещо сложно да се раздели на няколко по-прости неща, а те от своя страна също да се разделят на по-прости и т. н.
Могат да се посочат следните причини за създаване на подпрограми:

Една подпрограма обменя данни с останалата част от програмата по два начина: чрез параметри и чрез глобални по отношение на нея променливи и константи.

Когато една подпрограма се описва, параметрите и се наричат формални, защото нямат конкретна стойност, а служат само за нейното описание. Когато една подпрограма се вика, нейните параметри се наричат фактически и имат конкретни стойности. Параметрите имат тип, който задава типа на данните, обменяни между подпрограмата и останалата част на програмата. Параметрите на подпрограмите са два вида:

Когато подпрограмата се вика, броят на фактическите параметри е равен на броя на формалните в нейното описание. На мястото на фактическия параметър по стойност се поставя израз, чието стойност е от типа на параметъра и се подава към подпрограмата. На мястото на фактическия параметър по име се поставя променлива от тип еднакъв с типа на съответния формален параметър. Чрез тази променлива се осъществява обмена на стойности между подпрограмата и викащата програмна част. Редът на описание на параметрите е съществен, защото в същия ред се задават фактическите параметри при викане на подпрограмата. Както вече бе казано, една подпрограма може да бъде викана много пъти, като при всяко викане фактическите параметри са различни.

Ако като параметър се иска да се използва масив или диапазон, трябва да се дефинира съответен нов тип за масива или диапазона и параметъра да е от този тип.

Нека разгледаме общата структура на една програма на Pascal за да видим, къде се описват подпрограмите.

program заглавие
    uses списък от имена на библиотеки с готови подпрограми
    label списък от етикети
    const дефиниране на константи
    type описание на нови типове
    var деклариране на променливи

    описание на подпрограми

    begin

        тяло на програмата

    end.

В Pascal има два вида подпрограми: процедури и функции.

Подпрограма процедура. Този вид подпрограма отделя в себе си някакво логически обособено действие. Там където в програмата трябва да се осъществи това действие, се вика процедурата. Това обръщение към нея се реализира в езика като една отделна команда. Описанието на процедура става по следния начин:

    procedure име_на_процедура ( списък_от_формални_параметри );
        label списък от етикети
        const дефиниране на константи
        type описание на нови типове
        var деклариране на променливи

        описание на подпрограми вътрешни за процедурата

        begin

            тяло на процедурата

        end;

където име_на_процедура е идентификатор. Тялото на процедурата е също поредица от команди като тялото на програма. Описаните в процедурата подпрограми са вътрешни за нея и не могат да се викат извън нея. Същото се отнася и за етикетите, константите, новите типове и променливите зададени вътре в процедурата - те се ползват само вътре в нея. Ако процедурата няма параметри, то в заглавието и няма (списък_от_формални_параметри).

Отделните елементи на списъка от формални параметри се отделят един от друг чрез ; . Един формален параметър се описва по следния начин

    име : тип

ако е параметър по стойност, или

    var име : тип

ако е параметър по име. Типът може да е някой от вградените в езика типове като integer, real, char или да е някой от описаните вече в програмата нови типове. Ако имаме няколко еднотипни параметри всичките по стойност или по име, то те могат да се зададат в списък

    параметър1, параметър2, ... , параметърN : тип

Пример 7.1:

    type
        meseci = 1 .. 12;
         masiv = array[ meseci ] of real;

    procedure example (var a : masiv; var b, c : rael; d : real; n : integer);
        type
            sedmica = 1 .. 7;    { нов тип дефиниран в процедурата }
        var
            i: integer;
            m : sedmica;
        begin
             for i := 1 to 12 do
                 readln(a[ i ]);     { a се променя, защото е параметър по име }
            b := (b + c) / n;      { b и c се променят защото са параметри по име }
            c := (b - c) / d;
             d :=a[3] / n;           { грешка - d е параметър по стойност }
            m := n mod 7 + 1;
            writeln( m )
         end;

В тази примерна процедура параметрите a, b и c са по име и затова се променят вътре в нея. Параметрите d и n са по стойност и не би трябвало да се променят. Типът sedmica и променливите i и m са дефинирани вътре в процедурата и действат само вътре в нея.

Процедурата се вика като една отделна команда

    име_на_процедура(списък_от_фактически_параметри)

като списъкът от фактически параметри трябва да отговаря на съответния списък от формални параметри: по брой, по тип и по вид (по име или по стойност). Ако процедурата няма параметри, тя се вика само чрез своето име. Списъкът от фактически параметри има следния вид

    параметър1, параметър2, .. , параметърM

като отделните параметри са изрази, ако са по стойност или променливи, ако са по име.

Пример 7.2 (виж пример 7.1)

    var
        a, b : masiv;
        x , y :real;
        k : integer;
    begin
        ................
        x := 1;     y := 2;     k := 0;
        example(b, x, y, x + 2 * y, k + 6);
         { След процедурата x = 0.5, y = -0.2 }
       ................
        example(a, y, x, y - x / k, 20);
       ...................
    end.

В примера има две обръщения към процедурата example. Първите три параметъра на тази процедура са по име и затова фактическите параметри са променливи, които след излизане от процедурата имат нови стойности. Последните два параметъра са по стойност и затова фактическите параметри са изрази.

Задача 7.1. Да се състави програма за умножение на две матрици, ако е възможно.

Анализ.
Входни данни: Размерности на матрица A: n > 0 и m >0; на матрица B:  l > 0 и k > 0 - цели числа. Поради това, че при умножението на двете матрици се умножават елементите на ред от първата матрица със стълб от втората, то трябва m = l.

Матрицата A
a1,1, a1,2, ..., a1,M
a2,1, a2,2, ..., a2,M
.............
aN,1, aN,2, ..., aN,M - реални числа.

Матрицата B
b1,1, b1,2, ..., b1,K
b2,1, b2,2, ..., b2,K
.............
bM,1, bM,2, ..., bM,K - реални числа.

Изходни данни: Резултантната матрица C е с n реда и k стълба и елементи
за i=1, .. , n и j=1, .. , k

Програмата ще има 3 процедури: за въвеждане на двумерен масив, за извеждане в матричен вид на двумерен масив и за умножението на два масива.

Програма

program matrixmulty;
    uses WinCrt;
    const max = 50;
    type
        matrix = array[1 .. max, 1 .. max] of real;
    var
        a, b, c: matrix;
        k, l, m, n: integer;

    procedure vhod(var a: matrix; n, m: integer);
    { Процедура за въвеждане на двумерен масив
        a - масива, който се въвежда - параметър по име,
        n - брой редове, m - брой стълбове - параметри по стойност }

         var
             i, j: integer;
         begin
              for i:= 1 to n do
                  for j:= 1 to m do begin
                     writeln('Елемент от ред ', i, ' и стълб ', j, '=');
                     readln(a[i, j])
                  end
         end;

    procedure izhod(a: matrix; n, m: integer);
    { Процедура за извеждане на двумерен масив в матрична форма
        a - масива, който се извежда - параметър по стойност,
        n - брой редове, m - брой стълбове - параметри по стойност }

        var
            i, j: integer;
        begin
             for i:= 1 to n do begin
                 for j:= 1 to m do             { Извежда се ред от масива }
                    write(a[i, j]):8:2);
                writeln                              { Нов ред }
            end
        end;

    procedure multiply(a, b: matrix; var c: matrix; n, m, k: integer);
    { Процедура за умножение на матриците a и b - параметри по стойност,
        c - резултантна матрица - параметър по име,
        n и m - размерност на матрицата a,
        m и k - размерност на матрицата b,
        n и k - размерност на матрицата c }

        var
            i, j, p: integer;
        begin
             for i:= 1 to n do
                 for j:= 1 to k do begin
                    c[i, j]:= 0;                 { Сума на m събираеми }
                     for p:= 1 to m do
                        c[i, j] := c[i, j]+a[i, p] * b[p, j]
                end
        end;

    begin                                       { Главна програма }
        repeat
            writeln('Въведете брой редове и стълбове за матрица A:');
            readln(n, m)
         until (n > 0) and (n <= max) and (m > 0) and (m <= max);
        writeln('Въведете елементите матрица A:');
        vhod(a, n, m);                       { I обръщение към vhod }
        writeln('Матрица B трябва да има ', m, ' реда.');
        repeat
            writeln('Въведете брой стълбове за матрица B:');
            readln(k)
         until (k > 0) and (k <= max);
        writeln('Въведете елементите матрица B:');
        vhod(b, m, k);                      { II обръщение към vhod }
        multiply(a, b, c, n, m, k);
        { Обръщение към процедура multiply. В c се получава резултата
            от умножението на a и b. }

        writeln('Матрица A');
        izhod(a, n, m);                      { I обръщение към izhod }
        writeln('Матрица B');
        izhod(b, m, k);                     { II обръщение към izhod }
        writeln('Матрица C = A x B');
        izhod(c, n, k);                      { III обръщение към izhod }
    end.

Подпрограма функция. Функцията за разлика от процедурата освен, че извършва някакво логически обособено действие, изчислява някаква стойност. Затова функцията се вика вътре в изразите, където е необходима тази стойност. Функцията има тип - типа на изчислената от нея стойност. Описанието на функция става по следния начин

    function име_на_функция (списък_от_формални_параметри): тип;
         label списък от етикети
        const дефиниране на константи
        type описание на нови типове
        var деклариране на променливи

        описание на подпрограми вътрешни за функцията

        begin

            тяло на функцията

            .................

            име_на_функция := израз

            ..................

        end;

където име_на_функция е идентификатор, тип е типа на стойността изчислявана от функцията. Тази стойност трябва да е скаларна или от тип низ от символи и не може да е от тип масив, множество или запис. Типът може да е някой от вградените в езика скаларни типове като integer, real, char, тип string или да е някой от описаните вече в програмата нови типове. Описанието на формалните параметри е същото като при процедури. Ако функцията няма параметри, то в заглавието и няма (списък_от_формални_параметри).

Вътре в тялото на функцията на едно или няколко места трябва да има оператор за присвояване, където на нейното име се присвоява стойността на израз от тип еднакъв с този на типа на функцията. Това е стойността, която тя изчислява и връща при нейно извикване. Затова логиката на функцията трябва да е такава, че задължително да се премине през такъв оператор и тя да получи стойност. Ако функцията завърши без на нейното име да се присвои стойност, тя връща някаква случайна стойност - "боклук".

Пример 7.3:

    const max = 100;
    type
         masiv = array[1 .. max] of real;

    function fsin( x: real; a: masiv; n: integer; var err: boolean): real;
         const pi = 3.1416;
        var
            s: real;
            i: integer;
        begin
            err := false;
            if x < 0
                then begin
                    err:= true;
                    fsin := 0
                end
             else if (0 >= x) and (x <= pi) then
                begin
                    s:= 0;
                     for i := 1 to n do
                        s:= s + sin(a[i] * x);
                    fsin := s
                end
             else fsin := -sin(x)
         end;

Функцията fsin изчислява следната математическа функция

Понеже f(x) не е дефинирана за x < 0, в този случай fsin връща 0, защото все пак тя трябва да върне някаква стойност и параметърът по име err е true, а за всички останали стойности за x err е false. Така чрез параметъра err викащата fsin програмна част може да разбере, дали се изчислява коректна стойност.

Функцията се вика вътре в изразите, там където е необходима стойността, която тя изчислява. Това става по следния начин:

    име_на_функция(списък_от_фактически_параметри)

като списъкът от фактически параметри трябва да отговаря на съответния списък от формални параметри: по брой, по тип и по вид (по име или по стойност). Ако функцията няма параметри, тя се вика само чрез своето име. Задаването на фактическите параметри става по същия начин както при процедурите.

Пример 7.4 (виж пример 7.3):

    var
         a, b: masiv;
        x, y, z: real;
        undef: boolean;
    begin
        .................
        readln(x);
        y:= 5.3 + fsin(x, a, 10, undef) / 2;
         if udef then
            begin
                writeln('Функцията не дефинирана за x < 0');
                exit
            end;
        z := y + fsin(y, b, 15, unef) * x;
        writeln(fsin(z, a, 10, undef):10:4);
        ...................
    end.

В този пример функцията fsin се вика три пъти. Чрез променливата undef се проверява дали тя работи коректно. Библиотечната процедура exit прекъсва програмата.

Задача 7.2: Дадени са n реални числа. Да се изчисли формулата , за m - цяло число.

Анализ

Входни данни: n > 0 цяло,
                          a1, a2, ..., an - реални,
                            m - цяло число.
Изходни данни f = 
Знание: За да се реши задачата е необходимо да имаме функция за степенуване. Тази функция има следния алгоритъм

    Параметри a - реално, m - цяло.
        Начало
            1. Ако a = 0
                резултат 0
            иначе Ако m = 0
                резултат 1
            иначе Ако m < 0
                b <- 1 / a
                n <- -m
            иначе
                b <- a
                n <- m
                p <-1
                За i<-1 до n повтаряй
                    p <- p * b
                резултат p
        Край

Програма

program formula;
    uses WinCrt;
    const max = 100;
    type
        masiv = array[1 .. max] of real;
    var
        a: masiv;
         n, m, i: integer;

    function power(a: real; m: integer): real; { Функция за am }
        var
            i,;n: integer                { n от функцията няма нищо общо с n от главната програма }
            p, b: real;
        begin
             if a = 0
                 then power := 0
                 else if m = 0
                     then power := 1
                    else begin
                         if m < 0
                             then begin                    { am = (1/a)-m }
                                b := 1 / a;
                                n := -m
                            end
                              else begin
                                 b := a;
                                n := m
                            end;
                         p := 1;
                         for i := 1 to n do
                            p := p * b
                        power := p
                    end
         end;

    function f(a: masiv; n, m: integer): real;
    { Функция изчисляваща формулата }
        var
            i: integer;
            s: real;
        begin
            s := 0;
             for i:= 1 to n do
                s := s + power(a[i], m);
            f := s
         end;

    begin                             { Главна програма }
        repeat
            write('n =');
            readln(n)
         until (n > 0) and (n <= max);
        writeln('Въведете масива');
         for i := 1 to n do begin
            write('a', i, '=');
            readln(a[i])
        end;
        write('m =');
        readln(m);
        writeln('Резултат:', f(a, n, m):10:4);
    end.

Задача 7.3: Да се изчисли определен интеграл от непрекъсната функция f(x) за интервал [a, b].

Анализ
    Входни данни: a и b - реални и a < b;
                              f(x) - някаква непрекъсната функция на x
    Изходни данни: 
    Знание: За да се реши тази задача е необходимо да се избере някой от съществуващите числени методи. Избираме метода на правоъгълниците. При нега интервалът [a, b] се разделя на N части. За всяка част се изчислява лицето на правоъгълник с основа дължината на частта (b - a) / N и височина стойността на f(x) в средата на частта. Интегралът е сумата от тези правоъгълници , където . Точността зависи от N.

Алгоритъм: Да се напише програма за коректно въвеждане на математическа функция е твърде сложно и излиза извън рамките на това ръководство. Ще използваме, че компилатора може да провери за коректност един аритметичен израз и ще въвеждаме функцията f(x) направо в кода на програмата.

 Програма

program integral;
    uses WinCrt;
    var a, b, s: real;

    function f(x: real): real;     { Под интегралната функция f(x) }
        begin
            f:= ................             { На това място въведете функцията f(x) }
         end;

    function intergate(a, b: real): real;
         const N = 10000;
        var
            s, x1, x2: real;
            i: integer;
        begin
            x1 := a;
            s := 0;
             for i := 1 to N do begin
                x2 := x1 + (b - a) / N;
                s := s + f((x1 + x2) / 2);
                x1 := x2
             end;
             integrate := s
          end;

    begin
        repeat
            write('a = ');
            readln(a);
            write('b = ');
            readln(b)
         until b > a;
        writeln('Integral = ', integrate(a,b):10:4);
    end.

Упътване: Пробвайте програмата със следните примерни функции като внимавате интервала:[a, b] да е в дефиниционната област на съответната функция:

    f := sqrt(x) / sqr(x - 1)
    f := 1 / (x * sqrt(x) * (x + 1)
    f := cos(x) / (1 - sin(x))
   f := ln(x) / (x * x)

Локални и глобални величини. Всички величини, дефинирани вътре в една подпрограма: етикети, константи, нови типове, променливи, подпрограми и нейните формални параметри са локални, защото областта на тяхното действие е само подпрограмата и те нямат смисъл и са непознати извън нея. От друга страна всички величини, дефинирани извън дадена подпрограма в подпрограмата вътре, в която тя е дефинирана, или в главната програма са глобални по отношение на тази подпрограма. Величините дефиниране в главната програма са глобални по отношение на всички подпрограми в тази програма. Глобалните величини могат да действат в подпрограмата, спрямо която те са глобални.

Пример 7.5:

program p75;
    var
    a: real;                 { a - глобална за процедурата pr }

    procedure pr;
        var
            x, y: real;     { x, y - локални за процедурата pr }
        begin
            .............
            x:= 5; y:= 10;
            a:= x + y;     { a променя стойността си вътре в процедурата pr }
            ............
         end;

    begin
        ............
        a:= 0;
        pr;                 { След изпълнение на процедурата pr, a = 15 }
         x := a;            { Грешка "Непознат идентификатор", x е локална в pr и
                                 непозната в главната програма }

        .............
    end.

Когато една глобална променлива си сменя стойността в някаква подпрограма, се проявява така наречения страничен ефект при изпълнение на тази подпрограма, променливата не явно си изменя стойността при викане на подпрограмата (в примера променлива a). Когато подпрограмата се пише от един програмист, а се вика в програмни части писани от други програмисти, това може да доведе до трудно откриваеми грешки. Използването на глобални променливи в подпрограмите е оправдано в някои случаи поради големия брой параметри, което води до забавяне на програмата.

Възможно е да има съвпадение на имената на глобални и локални величини. В този случай действа правилото, че локалните имена отменят глобалните, т. е. глобална величина, чието име съвпада с име на локална величина, не действа в подпрограмата с тази локална величина.

Пример 7.6:

program pr76;
    type
        mas: array[1 .. 5] of real;     { Глобален тип }
    var
        a: mas;
         b, x: real;

    function fn(mas: real; var b: boolean): real;
        var
             c: mas;                     { Грешка, mas е параметър, а не тип }
            x: char;
        begin
            ...............
            x := 'Ж';                    { Локалната променлива x отменя глобалната x }
            b := true;                  { Параметърът b отменя глобалната променлива b }
            a[1] := mas + 2;         { Глобалният масив a се променя във функцията }
            ..............
         end;

Глобалните променливи b и x и типа mas не действат вътре във функцията fn.

Задача 7.4: Да се състави програма, която по зададена дата чрез ден, месец и година изчислява, кой ден от годината е тази дата и обратно по зададен ден от годината изчислява съответния месеца и ден от този месец.

Анализ
Входни данни: d - ден, m - месец, day - ден от годината, g - година - цели числа
Ограничения: g - всяко число,
                            1 Ј m Ј 12, 1 Ј d Ј 28, 29, 30 или 31 според месеца и годината,
                             1 Ј day Ј 365 или 366 според годината.
Изходни данни: day - ден от годината;
                            d - ден, m - месец.

Алгоритъм: В двумерен масив a (2 реда и 12 стълба) ще запишем броя на дните в месеците от високосна година (I ред) и обикновена година (II ред). Определянето дали g е високосна става по следния начин:

    Ако (g mod 400 = 0) или ((g mod 100 0) и (g mod 4 = 0))
        тогава k <- 1         ; I ред на масива
        иначе k <- 2         ; II ред на масива

Определянето на day от d и m:

    day <- d
    За i <- 1 до m - 1 повтаряй
        day <- day + a[k, i]

Определянето на d и m от day

    d <- day
    m <- 1
    Докато d > a[k, m] повтаряй
        d <- d - a[k, m]
         m <- m +1

Програма

program dates;
    uses WinCrt;
    var
        a: array[1 .. 2, 1 .. 12] of integer;
             { a - масив, в който са записани дните от месеците.
                 I ред - високосна година, II ред - не високосна година }

        day, d, m , g: integer;
             { day - ден от годината, d - ден от месеца, m - месец, g - година }
         b: boolean;

    function year_day: integer;
        { Функция изчисляваща ден от годината по зададени ден, месец и година. }
        var
            i, k, day: integer; { day - локална променлива отменяща съответната глобална }
        begin
             if (g mod 400 = 0) or ((g mod 100 <> 0) and (g mod 4 = 0))
                 then k := 1
                 else k := 2;
            day := d;
             for i := 1 to m-1 do
                day := day + a[k, i];
            year_day := day
         end;

    procedure day_month;
        { Процедура изчисляваща ден и месец по зададени ден от годината и година }
        var
            k, i: integer;
        begin
             if (g mod 400 = 0) or ((g mod 100 <> 0) and (g mod 4 = 0))
                 then k := 1
                 else k := 2;
            d := day;
            m := 1;
             while d > a[k, m] do begin
                day := day[k, m];
                m := m + 1
             end
         end;

    begin
        a[1, 1]:= 31; a[1, 2]:= 29; a[1, 3]:= 31; a[1, 4]:= 30; a[1, 5]:= 31; a[1, 6]:= 30;
        a[1, 7]:= 31; a[1, 8]:= 31; a[1, 9]:= 30; a[1, 10]:= 31; a[1, 11]:= 30; a[1, 12]:= 31;
        a[2, 1]:= 31; a[2, 2]:= 28; a[2, 3]:= 31; a[2, 4]:= 30; a[2, 5]:= 31; a[2, 6]:= 30;
        a[2, 7]:= 31; a[2, 8]:= 31; a[2, 9]:= 30; a[2, 10]:= 31; a[2, 11]:= 30; a[2, 12]:= 31;
        repeat
            write('Въведете дата:');
            readln(d, m, g);
            b := true;
             if (m < 1) or (m > 12) or (d < 1) or (d > 31)
                 then b := false
             else if (m in [4, 6, 9, 11]) and (d > 30)
                 then b := false
             else if m = 2
                 then if (g mod 400 = 0) or ((g mod 100 <> 0) and (g mod 4 = 0))
                    then begin
                          if d > 29
                              then b := false 
                    end
                      else if d > 28
                         then b := false
         until b;
        writeln('Тази дата отговаря на ден от годината:', year_day);
        repeat
            write('Въведете ден от годината и година:');
            readln(day, g);
            b := true;
             if (day < 1) or (day > 366)
                 then b := false
             else if not ((g mod 400 = 0) or ((g mod 100 <> 0) and (g mod 4 = 0))) and (day > 365)
                 then b := false
         until b;
        day_month;
        writeln('Дата:', d, '-', m, '-', g);
    end.

Забележка: Променливите a. day, d, m и g са глобални и действат в подпрограмите (day се отменя във функцията year_day от локална променлива със същото име). Логическата операцията in проверява дали елемент принадлежи на множество или не.

Предварително деклариране на подпрограма. Когато се вика подпрограма, която е описана по-надолу в програмата, е необходимо тя предварително да се декларира. Иначе компилаторът, който преглежда програмата отгоре надолу, не знае името на подпрограмата, нито броя, типа и вида на нейните параметри. Най-добре първо да си опишем подпрограмата, а след това да я викаме, но това не винаги е възможно - например при косвена рекурсия . Предварителното деклариране включва описание на заглавния ред следвано от думата forward. При процедури това изглежда така:

    procedure име_на_процедура ( списък_от_формални_параметри ); forward;

При функции:

    function име_на_функция (списък_от_формални_параметри): тип; forward;

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

Пример 7.7:

program pr77;
    procedure proc(var a, b: real; n: integer); forward; { Предварително деклариране }
    function func(var z: real; k: integer): real; forward; { Предварително деклариране }

    procedure call;
        var
            x, y, z:real;
        begin
            z:= func(x, 10) / 5.3;        { Викане на func преди да е описана. }
            proc(y, z, 15);                  { Викане на proc преди да е описана. }
         end;

    procedure proc; { Описание - не се описват формалните параметри }
        ....................
        begin
            { Описание на proc }
            .....................
         end;

    function func; { Описание - не се описват формалните параметри и типа }
        ....................
        begin
            { Описание на func }
            .....................
         end;

Библиотеки от готови подпрограми. Както бе казано в първа част, фирмата доставчик на средата за програмиране, а също така и специализирани фирми предлагат библиотеки от готови подпрограми, които могат да се ползват наготово в програмата. Тези библиотеки се поставят в специалната папка за библиотеки (обикновено units) на средата. С изключение на библиотеката system ако искаме да ползваме подпрограми от тези библиотеки, трябва да ги декларираме в началото на програмата след заглавния ред по следния начин:

    uses библиотека1, библиотека2, .. , библиотекаN;

т. е след uses в списък се изброяват имената на ползваните библиотеки. Тези имена са идентификатори и се взимат от документацията на съответната библиотека. Описанието на библиотеките на фирмата разработила средата за програмиране се намира в помощната система (help).

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

Ето някои библиотеки от Borland Pascal v.7.0:

Някои по-често използвани математически подпрограми от библиотеката system:

    function abs(x) - абсолютна стойност на x.
    function arctan(x: real): real - резултатът е в радиани.
    function cos(x: real): real - параметърът е в радиани.
    procedure dec(var k) - k е от изброим тип и се намалява с 1.
    function exp(x: real): real - ex.
    procedure exit - прекъсва блокът, в който се намира, ако блокът е тяло на цикъл, прекъсва се цикъла, ако е в тяло на подпрограма или на програмата, прекъсва се подпрограмата или програмата.
    function frac(x: real): real - дава дробната част на x.
    procedure halt - прекъсва програмата.
    procedure inc(var k) - k е от изброим тип и се увеличава с 1.
    function int(x: real): real - дава цялата част на x.
    function ln(x: real): real - натурален логаритъм.
    function pi: real - числото p.
    procedure randomize - стартира генератора на случайни числа.
    function random (k: integer) - намира случайно число. Тя може да се ползва без параметър и тогава резултатът е реално число в интервала [0, 1]. Ако се ползва параметър k > 0, резултатът е цяло число в интервала [0, k].
    function round(x: real): integer - закръгля x до цяло.
    function sin(x: real): real; - параметърът е в радиани.
    function sqr(x) - x2.
    function sqrt(x: real): real - корен квадратен от x.
    function trunc(x: real):integer - отрязва x до цяло.

Рекурсия.  

Дефиниция 7.2

Случаят, когато една подпрограма вика себе си, се нарича рекурсия. Рекурсията бива пряка и косвена.

Рекурсията е пряка, ако в тялото на подпрограмата има обръщение към нея. Косвена е тази рекурсия, когато една подпрограма вика друга, а тя вика първата. Може при косвена рекурсия една подпрограма да вика себе си чак след цяла верига от обръщения към други подпрограми, т. е. първата да вика втората, тя да вика трета, тя пък четвърта и т. н. и накрая последната да вика първата.

Когато една рекурсивна подпрограма започне да се изпълнява, то се достига пряко или косвено до обръщението към себе си. Тогава тя отново започва да се изпълнява и пак достига да това обръщение и т. н., т. е всъщност рекурсията е един не явен цикъл. Като при всеки цикъл трябва да съществува изход от този цикъл, иначе ще се получи зацикляне на програмата. В рекурсивната подпрограма би трябвало да има случай, когато тя не вика себе си. Когато се изпълни този случай, се казва, че се излиза от рекурсията. Броят пъти, когато една рекурсивна подпрограма вика себе си до излизането от рекурсията се нарича дълбочина на рекурсията. Програмистът трябва да следи тази дълбочина да не е твърде голяма, защото това води до препълване на служебната памет на програмата (програмния стек).

Всяка една програма с рекурсивна подпрограма може да се напише и без рекурсия чрез цикъл. В повечето случаи това е за предпочитане, защото цикълът се изпълнява по бързо от рекурсията и няма ограничения в дълбочината. Съществуват обаче задачи, където прилагането на рекурсия води до елегантно и лесно решение и за които намирането на решение чрез цикъл никак не е толкова лесно.

Задача 7.5: Да се състави рекурсивна функция за изчисляване на функцията на Акерман

където m и n са цели неотрицателни числа.

Анализ
    Параметри: m и n - цели и m,n і 0.
    Стойност на функцията - цяла.

Алгоритъм: Той е рекурсивен и точно следва дефиницията на функцията на Акерман.

Функция

function ack(n, m:integer): integer;
    begin
         if (m < 0) or (n < 0)                 { Грешни входни параметри }
            then begin
                ack := 0;
                exit         { Библиотечна процедура за прекъсване на подпрограма }
            end;
         if m = 0
             then ack := n + 1                 { Изход от рекурсията }
         else if n = 0
             then ack := ack(m - 1, 1)     { Рекурсия }
         else ack := ack(m - 1, ack(m, n - 1)     { Двойна рекурсия }
    end;

Задача 7.6: Да се състави програма реализираща играта "Ханойски кули". Играта е следната: Имате три стълба A, B, C и N диска с различни диаметри с отвор в центъра си, тъка че да могат да се надяват на стълбовете. Дисковете са наредени на стълб A в следния ред: най-отдолу е диска с най-голям диаметър, върху него е този с по-малък диаметър и т. н. Целта на играта е дисковете да се наредят в същия ред на стълб B, като се спазват следните правила: на едно местене може да се взема само един диск от тези най-отгоре на някой от стълбовете и не може да се поставя диск с по-голям диаметър върху диск с по-малък.

Анализ
    Входни данни: N > 0 - цяло - брой дискове.
    Изходни данни: поредица от команди към играча, кой диск да премести и къде.

Алгоритъм

    Ако броя дискове е 1
        тогава го преместваме от стълб A на стълб B.
    Иначе допускаме, че можем да решим задачата за N-1 диска.
        Тогава преместваме горните N-1 диска от стълб A на стълб C.
        Преместваме останалия N-ти диск от A на B.
        Преместваме N-1 диска от C на A.

Забележка. Именно допускането, че можем да решим задачата за N-1 диска означава, че имаме рекурсия.

Програма

program hanoi;
    uses WinCrt;
    var
        n: integer;        { Брой дискове }
         a, b, c: char;     { Имена на стълбовете }

    procedure kula(a, b, c: char; n: integer);
        begin
             if n = 1         { Изход от рекурсията }
                 then writeln('Премести диск 1 от стълб ', a, ' на стълб ', b)
            else begin
                kula(a, c, b, n-1);     { Рекурсия }
                writeln('Премести диск ', n, ' от стълб ', a, ' на стълб ', b);
                kula(c, b, a, n-1)     { Рекурсия }
             end
         end;

    begin
        repeat
            writeln('Въведете брой дискове:');
            readln(n)
         until n > 0;
        a := 'A'; b := 'B'; c := 'C';
        kula(a, b, c, n)
    end.


Съдържание


6. Деклариране на нови типове в Pascal. Тип диапазон. Масиви: едномерни, двумерни и тримерни масиви. Индексиране на масив. Обхождане на масив.


8. Обработка на символна информация в Pascal. Символен тип и тип низ от символи. ASCII таблица в DOS и ANSI таблица в Windows. Операции с отделни символи и с низове от символи. Вградени подпрограми в Borland Pascal за работа със символи.