4777

Процедуры и функции в программировании

Реферат

Информатика, кибернетика и программирование

Процедуры и функции Описание процедур. Формальные параметры. Локальные и глобальные объекты. Оператор процедуры. Фактические параметры. Функции. Примеры описаний функций. Рекурсивно-определенные процедуры и функции. Примеры рекурсивных описаний проц...

Русский

2012-11-26

123.5 KB

23 чел.

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

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

Формальные параметры. Локальные и глобальные объекты.

Оператор процедуры. Фактические параметры.

Функции.

Примеры описаний функций.

Рекурсивно-определенные процедуры и функции.

Примеры рекурсивных описаний процедур и функций

Преимущества и недостатки рекурсивных алгоритмов.

Задачи и упражнения.

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

Технология программирования на языках программирования типа языка Pascal предлагает проектировать программы методом последовательных уточнений.

На каждом этапе - шаге уточнения программист разбивает задачу на некоторое число подзадач, определяя тем самым некоторое количество отдельных программ. Концепция процедур (подпрограмм) позволяет выделить подзадачу как явную подпрограмму.

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

Раздел процедур

и функций

Описание процедуры выглядит также, как и описание программы, но вместо заголовка программы фигурирует заголовок процедуры. Заголовок имеет вид:

Заголовок

процедуры

 

Примеры заголовка процедуры:

procedure Picture;

procedure Power(X: real; n: Integer; var u, v: Real);

procedure Integral( a, b, epsilon: Real; var S: Real);

2.Формальные параметры. Локальные и глобальные объекты.

Как видно из примеров, в разделе формальных параметров перечисляются имена формальных параметров, а затем указывается их тип. Таким образом, каждое описание формальных параметров с точки зрания синтаксиса выглядит также, как и описание переменных в разделе переменных. Перед некоторыми описаниями ставится служебное слово Var. Такие параметры называются параметрами-переменными. Если перед описанием служебное слово Var не стоит, это - параметры-значения. Различие между этими типами параметров описано ниже.   

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

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

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

3.Оператор процедуры. Фактические параметры.

Оператор процедуры имеет вид:

< имя > или < имя > (< список фактических параметров >)

Синтаксическая диаграмма оператора процедуры:

Оператор

процедуры

Примеры операторов процедуры:

 Picture

 Power(( a + b )/2, 3, degree, root )

 Integral ( 0, P/2, 1E-6, SUMMA)

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

 Пример 1. Рассмотрим заголовок процедуры и оператор этой процедуры:

Procedure Integral ( a, b, eps: real; var s: real );

   Integral ( -Pi/2, Pi/2, 1E-6, summa );

Соответствие:

            Формальный параметр             Фактический параметр

                Значение  a                           Выражение  - Pi/2

                Значение  b                           Выражение  Pi/2

                Значение  eps                        Данное  1E-6

                Переменная s      Переменная Summa

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

Если х1, х2,..., хn - фактические параметры-переменные, соответствующие формальным параметрам-переменным v1, ... , vn, то x1, x2, ..., xn должны быть различными. Фактическкими параметрами-значениями могут быть выражения или данные соответствующих типов.

Рассмотрим пример:

 

Пример 2. Программа вычисляет координаты точки (x0, y0) при последовательных поворотах и параллельных переносах системы координат.

Program Coordinates;

  Const Pi = 3.141592;

    Var Alfa, Beta : Real;

         x0, y0, x1, y1, x2, y2 : Real;

         x, y : Real;

 Procedure Rotate(x, y, Fi: Real; var u, v: Real );

        var cosFi, sinFi : Real; { локальные переменные }

       begin

         Fi := Fi*Pi/180 ;

         cosFi := Cos(Fi); sinFi := Sin(Fi);

         { параметры x, y защищены от глобальных переменных x, y }

          u := x * cosFi - y * sinFi ;

          v := x * sinFi + y * cosFi

        end ;

 Procedure Move(x, y, a, b : Real; var u, v: Real);

      begin

         u := x + a ; v := y + b

        end;

    begin

       Read (x0, y0);  Read (Alfa);  Rotate(x0, f0, alfa, x, y);

       Read (x1, y1);     Move(x, y, x1, y1, x, y);

       Read (Beta);       Rotate(x, y, Beta, x, y);

       Read ( x2, y2 );  Move(x, y, x2, y2, x, y);

       Writeln (‘================================’);

       Writeln (‘абсцисса точки : ‘, х);

       Writeln (‘ордината точки : ‘, y);

   end.

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

Пусть, например, переменная A типа Sequence - массив из 1000 действительных чисел и     Procedure MaxMin(X : Sequence; var Max, Min : Real) - поиск максимального и минимального элементов массива X. Тогда при обращении к процедуре MaxMin с помощью оператора MaxMin(A, Sup, Inf) компилятор выделит память (6 - 10 байт на каждый элемент массива - всего 6000 - 10000 байт ) и осуществит 1000 циклов пересылки чисел из A в X. Если же параметр X определить как параметр-переменную:  Procedure MaxMin(var X : Sequence; var Max, Min : Real)   ни памяти, ни пересылок не понадобится.

4.Функции.

Наряду со стандартными функциями, в языке можно определить и другие необходимые программе функции.  Функция - это подпрограмма, определяющая одно - единственное скалярное или ссылочное значение, используемое при вычислении выражения. Описание функции имеет, по существу, такой же вид, как и описание процедуры. Отличие заключается в заголовке, который имеет вид:  Function < имя > : < тип результата > ;

или Function < имя > (<список описаний формальных параметров>): < тип результата >;

Синтаксическая диаграмма заголовка функции:

Заголовок

функции

 

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

Таким образом, для функций определены все те понятия, которые были сформулированы для процедур.

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

Примеры описаний функций.

 Пример 3.Функция GCD (алгоритм Евклида) вычисляет наибольший общий делитель двух натуральных чисел x и y.

Function GCD (x, y : Integer) : Integer ;

   Begin

     While x <> y do

       If x < y

        then y := y - x

        else x := x - y ;

        GCD := x

    End;

Пример 4.   Функция IntPow возводит действительное число x в степень N. (Y = x N )

Function IntPow(x: Real; N: Integer) : Real;

     Var i: Integer;

   Begin

     IntPow := 1;

     For i:=1 to Abs(N) do IntPow := IntPow * x;

     If N < 0 then IntPow := 1/IntPow

    End;

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

Program GCD_of_Array;

   Const n = 100 ;

     Var i, D : Integer;

          A : Array[1..n] of Integer;

Function GCD (x, y : Integer) : Integer ;

  Begin

   While x <> y do

     If x < y

      then y := y - x

      else x := x - y;

      GCD := x

   End;

Begin { основная программа }

{Блок чтения массива натуральных чисел}

  D := GCD (A[1], A[2]);

  For i := 3 to n do D := GCD(D, A[i]);

  writeln ( ‘ НОД последовательности = ‘ , D )

 End.

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

    

 

Понятия локальных и глобальных объектов распространяются и на вложенные процедуры. Например, переменная, описанная в процедуре A локальна по отношению к основной программе и глобальна для процедур B и C, вложенных в A.

В некоторых случаях необходимо из процедуры осуществить вызов другой процедуры, описанной в том же разделе процедур и функций. Например, процедура C может содержать оператор вызова процедуры B. В этом случае компилятор правильно обработает текст программы, поскольку процедура B описана до процедуры C. Если же из процедуры B необходимо обратиться к C, для правильной обработки вызова C необходимо использовать механизм опережающего (предварительного) описания C. Опережающее описание процедуры (функции) - это ее заголовок, вслед за которым через “;” поставлено служебное слово Forward. В тексте программы опережающее описание должно предшествовать процедуре, в которой предварительно описанная процедура вызывается.

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

Procedure A (x : TypeX; Var y : TypeY); Forward;

Procedure B (z : TypeZ) ;

Begin

... A( p, q); ...

End;

Procedure A;

Begin

...

End;

5.Рекурсивно-определенные процедуры и функции.

Описание процедуры A, в разделе операторов которой используется оператор этой процедуры, называется рекурсивным. Таким образом, рекурсивное описание имеет вид

Procedure A(u, v : ParType);

...

Begin

...; A(x, y); ...

End;

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

Function F(u, v : ArgType) : FunType;

...

Begin

...; z := g(F(x, y)); ...

End;

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

 

Пример 6. Факториал.

Рассмотрим рекурсивное определение функции n!=1*2*...*n (n-факториал).   Пусть F(n) = n! Тогда

 1.F(1) = 1

 2.F(n) = n*F(n - 1)   при   n > 0

Средствами языка это определение можно сформулировать как вычисление:

If n = 1

then F := 1

else F := F(n - 1) * n

Оформив это вычисление как функцию и изменив имя, получим:

Function Fact(n: Integer): Integer;

  Begin

   If n = 1

    then Fact := 1

    else Fact := Fact(n - 1) * n

   End;

Вычисление функции Fact можно представить как цепочку вызовов новых копий этой функции c передачей новых значений аргумента и возвратов значений функции в предыдущую копию.

 

                n-1   n-2                n-3          2            1

 

      n!  (n-1)!   (n-2)!                                   2          1

Цепочка вызовов обрывается при передаче единицы в новую копию функции. Движение в прямом направлении (разворачивание рекурсии) сопровождается только вычислением условия и вызовом. Значение функции вычисляется при сворачивании цепочки вызовов. Сложность вычисления Tfact(n) функции Fact можно оценить, выписав рекуррентное соотношение:

Tfact(n) = Tfact(n-1) + Tm + Tl + Tс

Для того, чтобы вычислить Tfact(n), нужно осуществить одну проверку, одно умножение и один вызов Tfact(n-1). Вызов Tfact требует затрат времени Tc на “административные” вычисления: передачу параметра, запоминание адреса возврата и т.п. Положив С = Tm+Tl+Tс, получим Tfact(n) = Tfact(n-1) + С. Нетрудно теперь показать, что  Tfact(n) = Сn.

.

Пример 7. Перестановки. Сгенерировать все перестановки элементов конечной последо-вательности, состоящей из букв.

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

Пусть S = [ s1, s2, ..., sn ] - конечный набор символов.

Через Permut(S) обозначим множество всех перестановок S, a через  Permut(S,i) - множество всех перестановок, в которых на последнем месте стоит элемент si. Тогда

Permut(S) = Permut(S,n) Permut(S, n-1) ... Permut(S,1)

Элемент множества Permut(S, i) имеет вид [sj2,..., sjn,si]где j2,..., jn - всевозможные перестановки индексов, не равных I. Поэтому Permut(S, i) = (Permut(S \ si), si) и  Permut(S)=(Permut(S \ s1),s1)+...+ (Permut(S \ sn), sn).

Полученное соотношение выражает множество Permut(S) через множества перестановок наборов из (n-1) символа. Дополнив это соотношение определением Permut(S) на одноэлементном множестве, получим:

1. Permut({s}) = {s}

2. Permut(S) = (Permut(S\s1), s1) + ... + (Permut(S\sn), sn)

Уточним алгоритм, опираясь на представление набора S в виде массива S[1..n] of char.

Во первых, определим параметры процедуры Permut:

 k - количество элементов в наборе символов;

 S - набор переставляемых символов.

Алгоритм начинает работу на исходном наборе и генерирует все его перестановки, оставляющие на месте элемент s[k]. Если множество перестановок, в которых на последнем месте стоит s[j], уже порождено, меняем местами s[j-1] и s[k], выводим на печать полученный набор и применяем алгоритм к этому набору. Параметр k управляет рекурсивными вычислениями: цепочка вызовов процедуры Permut обрывается при    k = 1.

Procedure Permut(k : Integer; S : Sequence);

      Var j : integer;

    Begin

      if k <> 1 then Permut(k - 1, S);

      For j := k - 1 downto 1 do begin

      Buf := S[j]; S[j] := S[k]; S[k] := Buf;

      WriteSequence(S); Permut(k - 1, S)

      end

    End;

    Begin { Раздел операторов программы}

    {Генерация исходного набора S}

      WriteSequence(S); {Вывод первого набора на печать}

       Permut(n, S)

     End.

Оценим сложность алгоритма по времени в терминах C(n): Каждый вызов процедуры Permut(k)  содержит k вызовов  процедуры Permut(k-1) и 3(k-1) пересылки. Каждый вызов Permut(k-1) сопровождается передачей массива S как параметра-значения, что по времени эквивалентно n пересылкам. Поэтому имеют место сооотношения

C(k) = kC(k-1) + nk + 3(k-1),  C(1) = 0,  откуда  С(n) = (n+3)n!

Оценим теперь размер памяти, требуемой алгоритму. Поскольку S - параметр-значение, при каждом вызове Permut резервируется n ячеек (байтов) для S, а при выходе из этой процедуры память освобождается. Рекурсивное применение Permut приводит к тому, что цепочка вложенных вызовов имеет максимальную длину (n - 1):

Permut(n) --> Permut(n-1) --> ... --> Permut(2)

Поэтому данные этой цепочки требуют n2 - n ячеек памяти, т.е алгоритм требует память размера O(n2). Количество перестановок - элементов множества Рermut(S) равно n!. Поэтому наш алгоритм “тратит” C(n)/n! = O(n) действий для порождения каждой перестановки. Разумеется, такой алгоритм нельзя назвать эффективным. (Интуиция нам подсказывает, что эффективный алгоритм должен генерировать каждую перестановку за фиксированное, не зависящее от n количество действий.) Источник неэффективности очевиден: использование S как параметра-значения. Это позволило нам сохранять неизменным массив S при возврате из рекурсивного вызова для того, чтобы правильно переставить элементы, готовя следующий вызов.

Рассмотрим другой выриант этого алгоритма. Используем S как глобальную переменную. Тогда при вызове Permut S будет изменяться. Следовательно при выходе из рекурсии массив S нужно восстанавливать, используя обратную перестановку!

Program All_permutations;

  Const n = 4;

   Type Sequence = array[1..n] of char;

    Var S : Sequence;

         Buf : char;

            i : Integer;

Procedure WriteSequence;

     begin

      For i := 1 to n do Write(S[i]); Writeln

      end;

Procedure Permut(k : Integer);

      Var j : integer;

Procedure Swap(i, j : Integer);

     begin  Buf := S[j]; S[j] := S[i]; S[i] := Buf  end;

    Begin

      if k > 1 then Permut(k - 1);

      For j := k - 1 downto 1 do begin

       Swap(j, k); {Прямая перестановка}

       WriteSequence; Permut(k - 1);

       Swap(k, j) {Обратная перестановка}

      end

    End;

 Begin

    {Генерация исходного набора S}

    WriteSequence;  Permut(n)

   End.

Теперь оценка C(n) получается из соотношений

C(k) = kC(k-1) + 3(k-1), C(1) = 0 , т.е. C(n) = O(n!)

Интересно, что этот вариант не требует и памяти размера O(n2) для хранения массивов. Небходима только память размера O(n) для хранения значения параметра k.

6.Примеры рекурсивных описаний процедур и функций.  

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

Пример 8. Возвратные последовательности.

Рассмотрим последовательность V(n), заданную рекуррентно:

 1.V(0) = V0, V(1) = V1, ..., V(k) = Vk;

 2.V(n+k) = F( V(n+k-1), ... V(n+1), V(n), n )

Такое определение задает последовательность V(n) фиксированием первых ее нескольких членов и функции F, вычисляющей каждый следующий член, исходя из предыдущих. Рекуррентное определение “дословно переводится” в функцию, вычисляемую рекурсивно:

Function V(n: Integer) : Integer;

  Begin

   Case n of

     0:  V := V0;

      . . . . .

     k:  V := Vk

    else V := F(V(n+k-1), ... V(n+1), V(n), n)

   end    End;

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

Function RF(n: Integer) : Integer;

  Begin

   Case n of

     0,1: RF := 1

     else RF := RF(n-1) + RF(n-2)

    end

   End;

К сожалению, эта красивая и прозрачная версия крайне неэффективна: ее сложность определяется из соотношения  Trf (n) = Trf (n-1) + Trf (n-2) + 1.

Функция Trf(n) равна функции RF(n). Нетрудно показать, что  Tr f (n) = RF(n) > 2 n-2   при   n > 5.

Таким образом, сложность вычисления RF(n) эспоненциальна. Сложность же итеративного алгоритма вычисления Fib линейна. В общем случае ситуация точно такая же: можно построить итеративный алгоритм вычисления возвратной последовательности линейной сложности, рекурсивная же версия при k >= 1 имеет экспоненциальную сложность.

 

Пример 9. Ханойские башни.

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

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

  Рис А

1 стержень    2 стержень    3 стержень

Пусть N - количество колец на стержне, I - номер кольца, с которого осуществляется перестановка и J - номер кольца, на которое кольца требуется переставить. Переменные N, I, J - параметры процедуры HanojTower, управляющей перестановками. Шаг решения - процедура Step с параметрами I, J.

HanojTower( N, I, J) - процедура, переставляющая N колец с I-того стержня на J-тый.

Step(I, J) - процедура, переставляющая 1-но кольцо с I-того стержня на J-тый.

Заметим, что если I и J - номера 2-стержней, то 6-I-J - номер третьего стержня.

Предположим, что мы переместили N-1 кольцо с I-того стержня на 6-I-J стержень. ( рис B )

Рис B

   (n-1) кольцо

I cтержень    J стержень    6-I-J стержень

 

Тогда можно переместить кольцо со стержня I на J.(рис C)

Рис C

1 кольцо

I cтержень    J стержень    6-I-J стержень

 

Заметим теперь, что на стержне J лежит кольцо с наибольшим диаметром, т.е. этот стержень можно использовать без нарушения ограничений, связанных с величинами диаметров. Поэтому можно теперь переставить всю пирамиду из N-1 кольца со стержня 6-I-J на J, (рис D) и задача решена!

Рис D

   n-1 кольцо

I cтержень    J стержень    6-I-J стержень

Заметив, что при N = 1 задача решается с помощью процедуры Step(I, J), опишем процедуру HanojTower(N, I, J):

Procedure HanojTower(N, I, J: Integer);

   Begin

     If N = 1

      then Step(I, J)

      else begin

       HanojTower(N-1, I, 6-I-J);

       Step(I, J);

       HanojTower(N-1, 6-I-J, J)

     end

    End;

Процедуру Step(I, J) можно реализовать, используя представление данных в массиве Rings[1..N, 1..3] и графическую визуализацию перемещения колец.

Определим сложность алгоритма по времени C(n) в терминах количества шагов (вызовов Step), выписав рекуррентное соотношение:  С(n) = 2C(n-1) + 1

Легко теперь показать, что С(n) = 2 n - 1. Доказано, что это количество шагов является минимальным возможным, поэтому наш алгоритм оптимален.

 

Пример 10. Линейные диафантовы уравнения. Перечислить все неотрицательные целые решения линейного уравнения  a1x1 + a2x2 + ... + anxn = b  c целыми положительными коэффициентами.

Как и в предыдущих примерах, опишем алгоритм рекурсивно, осуществив сведение исходной задачи к задаче меньшего размера.

Перепишем исходное уравнение в виде: a1 x1 + a2 x 2 + ... + a n-1 x n-1 = b - a n x n

Организуем перебор всевозможных значений xn, при которых правая часть  b - a n x n > 0.    xn = 0, 1, ... y,  где y = b div an.  Тогда первые n-1 компонент решения (x1, ... , x n-1, x n) исходного уравнения - решение уравнения a1 x1 + a2 x2 + ... + a n-1 x n-1 = b - a n x n  .

Таким образом мы свели решение исходного уравнения к решению y +1 уравнения с n-1 неизвестным, и, следовательно, можем реализовать алгоритм рекурсивно. Определим условия выхода из рекурсии:

при b = 0  существует единственное решение - (0, 0, ..., 0)

при n = 1  если b mod a1 = 0 то x1 = b div a1 иначе решений нет.

Таким образом, выходить из рекурсивных вычислений нужно в двух (крайних) случаях. Мы установили и параметры процедуры: n и b.

Procedure Solution(n, b : integer);

     Var i, j, y, z : Integer;

   Begin

     If   b = 0

      then begin

       For j := 1 to n do X[j] := 0; WriteSolution end

       else If (n = 1) and (b mod a[1] = 0)

          then begin X[1]:= b div a[1]; WriteSolution end

         else If n > 1

           then begin

              z := a[n]; y := b div z;

              For i := 0 to y do begin

              X[n] := i; Solution(n - 1, b - z*i)

          end

     end

 End;

 Program AllSolutions;

     Const n = 4;

      Type Vector = array[1..n] of Integer;

       Var a, X : Vector; b : Integer;  i : Integer;

    {Procedure WriteSolution распечатывает решение X[1..n] }

    {Procedure Solution}

    Begin

      {Ввод массива коэффициентов a[1..n] и св. члена b}

      Solution(n, b)

    End;

Пример 11. Возведение числа в натуральную степень. Возвести вещественное число a в натуральную степень n.

Ранее эта задача была решена методом последовательного домножения результата на a. Однако ее можно решить эффективнее, если применить метод половинного деления степени n. Именно: an = (a n/2) )2. Поскольку число n не обязательно четное, формулу нужно уточнить:

a^n = (a n  div 2) 2   * a n  mod  2. Дополнив определение a n определением a1 = a и заменив домножение на  a n mod 2  разбором случаев чет-нечет, получим:

Function CardPower(a : Real; n : Integer) : Real; var b : Real;

  Begin

    If n = 1

     then CardPower := a

      else begin

        b := Sqr(CardPower(a, n div 2));

        If n mod 2 = 0

         then CardPower := b

         else CardPower := a*b

      end

    End;

Докажите, что функция CardPower использует не более O(log 2 n) умножений и возведений в квадрат.

Разумеется, функцию CardPower можно реализовать без циклов и рекурсий,с помощью формулы: при a > 0 a n  = e n* ln a ,  но этот метод не годится, например, если в натуральную степень возводится многочлен.

 

Пример 12. Пересечение возрастающих последовательностей.

Пусть A = [a1, a2,...,an] и B = [b1, b2, ... , bm] - две возрастающие числовые последовательности. Пересечением этих последовательностей называется возрастающая последовательность С = [с1, с2,..., сk] состоящая из тех и только тех чисел, которые принадлежат обеим последовательностям. Требуется найти C = AB.

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

A = [a1]A2;   B = [b1] B2,   где A 2 = [a 2,...,a n],  B 2 = [b 2,...,b n]

Тогда   AB = (a1  A2) (b1 + B2)  =  a1b1  a1B2 A2b1  A2B2 

(Скобки в обозначениях одноэлементных множеств опущены)

Так как последовательности A и B возрастают, имеем:

Если a1 = b1 то AB = a1b1 A2B2 = a1 A2B2

Если a1 < b1 то AB = b1A2 A2B2 = A2B

Если a1 > b1 то AB = a1B2 A2B2 = AB2

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

Процедура Intersect поиска пересечения зависит от параметров i и j - номеров начальных элементов подпоследовательностей A[i..m] и B[j..n], представленных массивами A[1..m] и B[1..n]. Найденный элемент пересечения распечатывается.

Procedure Intersect(i, j : Integer);

   Begin

     If (i <= m) and (j <= n)

      then If a[i] = b[j]

       then begin Write(a[i]); Intersect(i+1, j+1) end

        else If a[i] < b[j]

          then Intersect(i+1, j)

          else Intersect(i, j+1)

      End;

7.Преимущества и недостатки рекурсивных алгоритмов.

Рассмотренные примеры показывают, что применение рекурсивных определений само по себе не приводит к хорошим решениям задач. Так, задачи примеров 6, 8, 12 допускают более эффективные и достаточно простые итеративные решения. В примере 12 это продемонстрировано особенно наглядно. В примерах 6 и 8 рекурсия моделирует простой цикл, тратя время на вычисления, связанные с управлением рекурсивными вызовами и память на динамическое хранение данных. То же самое можно сказать и о примере 11. Мы уже рассматривали итеративную версию метода деления пополам в других примерах.

Несомненным достоинством алгоритмов из примеров 8, 11, 12 является их простота и обоснованность. При программировании мы по-существу одновременно обосновывали правильность алгоритма.  В примерах 7, 9, 10 рассматривались комбинаторные задачи, решение которых не сводится к простому применению цикла, а требует перебора вариантов, естественным образом управляемого рекурсивно. Итеративные версии решений этих задач сложнее по управлению. Можно сказать, что основная вычислительная сложность комбинаторной задачи заключена не в реализации алгоритма ее решения, а в самом методе решения.

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

8.Задачи и упражнения.

Упражнения I.

1.Опишите процедуры сложения и перемножения n*n матриц, состояших из действительных чисел. С помощью этих процедур составьте программу вычисления матрицы B = AX + XA + E по данным матрицам A и X.

2.Опишите процедуру поиска наибольшего и наименьшего элементов в массиве. С помощью этой процедуры составьте программу, определяющую, совпадают ли наибольший и наименьший элементы двух массивов А[1..n] и B[1..n].

3.Опишите процедуры поиска среднего по величине элемента в массиве A[1..2n+1] и среднего арифметического элементов этого массива. С помощью этих процедур составьте программу, сравнивающую по величине среднее по величине и среднее арифметическое в массиве A[1..99].

4.Опишите процедуру поиска наибольшего и наименьшего элементов в массиве А[1..n]. С помощью этой процедуры составьте программу, определяющую координаты вершин наименьшего прямоугольника со сторонами, параллельными осям координат и содержащего в себе множество точек Т1(X1,Y1), ... , Tn(Xn,Yn).

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

6.Опишите функцию проверки простоты числа. Опишите функцию проверки числа на разложимость в сумму вида 1+2а.  Составьте программу, которая выбирает из данного массива чисел те и только те его элементы, которые удовлетворяют обоим свойствам.

7.Опишите процедуру перевода целого числа из десятичной системы в p-ичную систему счисления. Опишите процедуру перевода правильной десятичной дроби в p-ичную с заданным количеством разрядов. Составьте программу перевода произвольного действительного числа из 10-чной в p-ичную систему счисления.

8.Опишите процедуру поиска наименьшего элемента в строке матрицы. Опишите функцию проверки на максимальность данного элемента в столбце матрицы. Составьте программу поиска седловой точки матрицы.

Упражнения II.

1.Опишите функцию f(x) - наибольший собственный делитель числа х. Составьте программу поиска всех собственных делителей числа N.

2.Опишите функцию y = arcsin(x). Составьте программу решения уравнения sin(ax+b) = c.

3.Опишите функцию f(x) = max (t*sin(t)).

                                                         t [0,x]

Составьте программу табулирования функции f(x) на отрезке [a,b].

4.Опишите функцию f(x) - число, которое получается из натурального числа x перестановкой цифр в обратном порядке.  Составьте программу, которая распечатывает симметричные числа из массива натуральных чисел.

5.Опишите функции L(x,y) и (x,y), которые  определены  формулами L(x,y) = |x + iy|,  (x, y) = arg(x + iy). Составьте программу перевода последовательности комплексных чисел z1, ..., zn,  zj = xj + iyj,  в тригонометрическую форму.

Упражнения III.

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

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

3.Реализуйте алгебру - конечное поле GF(p) вычетов по простому модулю p как библиотеку процедур и функций, содержащую арифметические  действия  над вычетами. GF(p) = ( 0, 1, ..., p-1 )

 

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

Задачи.

1.Перечислить все выборки по K элементов в массиве A из N элементов. Массив содержит первые N натуральных чисел: A[i] = i.  Найти их количество и оценить сложность алгоритма.

2.Перечислить все подмножества множества (массива A) из задачи 1. Найти их количество и оценить сложность алгоритма.

3.Дан массив A[1..n] целых положительных чисел и целое число b. Перечислить все наборы индексов j1, j2, ..., jk такие,что  A[j1] + A[j2] + ... + A[jk] = b. Оценить сложность алгоритма.

4.Дан массив A[1..n] целых чисел и целое число b. Перечислить все наборы индексов j1, j2, ... , jk такие, что A[j1] + A[j2] + ... + A[jk] = b. Оценить сложность алгоритма.

5.Известная в теории алгоритмов функция Аккермана А(x, y) определена на множестве натуральных чисел рекурсивно:

A(0, y) = y + 1,

A(x, 0) = A(x - 1, 1),

A(x, y) = A(x - 1, A(x, y - 1));

a)Опишите функции A(1, y), A(2, y), A(3, y), A(4, y) явным образом;

б)Реализуйте рекурсивную программу вычисления A(x, y);

в) Реализуйте программу вычисления A(x, y) без рекурсии.


 

А также другие работы, которые могут Вас заинтересовать

55672. Вивчення схильностей учнів до небажаних вчинків 7.01 MB
  Вивчити причини, що спонукають підлітків до вчинення протиправних дій та найбільш поширені шкідливі звички. За основу даного дослідження взято анкету «Молодь і протиправна поведінка» (автор Пачковський, І. Корнієнко).
55674. Натхненна спадщина. З історії розвитку культури м.Сміли Черкаської області 291 KB
  Факти такі. У 19 ст. в містечку існувало дві типографії, в одній із них 1885 року граф Олександр Олексійович Бобринський надрукував своє генеалогічне дерево. 1895 року почала діяти публічна бібліотека при Смілянському народному училищі. На ці ж роки припадає розквіт театру Бобринських.
55675. Використання міжпредметних зв’язків, як один із за 251.5 KB
  Специфіка викладання іноземної мови відкриває широкі можливості у використанні міжпредметних зв’язків з метою підвищення зацікавленості учнів до вивчення іноземної мови. Коли учні вчать іноземну мову, вони мимохідь знайомляться з новою для них країною, з її культурою, історією, літературою, новим способом життя.
55676. Розробка системи уроків геометрії у 9 класі профільної школи з теми: «Геометричні перетворення» 275.5 KB
  При вивченні цієї теми розглядаються деякі конкретні приклади перетворення фігур а також загальне питання руху. Перетворення геометрії є основою для введення подібності фігур. Поняття про перетворення фігур...
55677. Методи накладання покривних (бинтової, косинкової, пращоподібної і пластирної) пов’язок і давлючої бинтової пов’язки 188 KB
  Мета: дати поняття про загальні вимоги щодо накладання покривних пов’язок: бинтової косинкової пращоподібної пластирної та пояснити правила накладання давлючої бинтової пов’язки...
55678. Методи групової роботи при вивченні математики 169 KB
  Групові форми навчання основні відомості та загальні рекомендації Групова форма навчання – це така форма організації навчальних занять за якої певній групі студентів ставиться єдине навчальне завдання для розв’язання якого потрібне об’єднання...
55679. ДІЯЛЬНІСНИЙ ПІДХІД ЯК ТЕХНОЛОГІЯ ОПРАЦЮВАННЯ СТАТЕЙ ПІДРУЧНИКА 116.5 KB
  Завдяки сучасним змінам в освітній системі держави стало актуальним звернення педагогів до проблем застосування активних та інтерактивних методів навчання. Завдяки чисельним публікаціям і системі додаткової освіти у свідомості людей поступово формується думка...
55680. Організація проектної діяльності на уроках біології 307.5 KB
  У ході здійснення проекту школярі навчаються надавати допомогу своїм товаришам по роботі в них формується вміння самостійно орієнтуватися в інформаційному просторі виробляється обов’язковість і відповідальність.