Консультации по основам программирования

Тема. Подпрограммы - функции                                 15.01.17                                
     

   Необходимость в подпрограммах возникает по мере нарастания сложности решаемой задачи.  Подпрограмму можно рассматривать как относительно самостоятельную программу решения некоторой частной задачи, написанную и оформленную так, что ее можно многократно выполнять с различными входными данными. 
В Паскале есть встроенные функции, такие, как sqr(x), sqtr(x) и др. Программист может написать и свои функции. Описание функций должно быть помещено в тексте программы  после раздела описания переменных. 
Подпрограммы-функции обладает следующими свойствами:

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

Описание функции выглядит так:

function  имя_функции (параметр_1:тип_1; параметр_2:тип_2;...параметр_N):тип функции;

раздел описаний функции

begin

раздел операторов функции
имя_функции:=выражение
end;

          Тема. Подпрограммы процедуры                                            29.01.17

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

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

В общем виде описание процедуры выглядит так:

procedure имя_процедуры (параметр_1:тип_1....; var параметр_2: тип_2; var параметр_3:тип_3...)

раздел описаний процедуры

begin

раздел операторов процедуры

end;

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

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

При использовании процедур следует соблюдать следующие правила:

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

          Тема. Рекурсивные алгоритмы                                            07.05.17

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

  Натуральные числа:

•  1 есть натуральное число;
• целое число, следующее за натуральным, есть натуральное число.

 Следующий пример - функция факториал n! для неотрицательных целых чисел:

• 0!=1,
•  если n>0, то n!=n*(n-1)!

Определение степени  с целочисленным показателем тоже является рекурсивным:

                          a*a^(k-1), если k>0,

a^k={ 1, если k=0,

                            1/a*a^(k+1), если k<0

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

   В общем виде рекурсивную программу Р можно изобразить как композицию Р базовых операторов Si  и самой Р :

Р=Р [Si,Р]

 Необходимое и достаточное средство для рекурсивного представления программ- это описание процедур и функций, так как оно позволяет присваивать какому-либо оператору имя, с помощью которого можно вызвать этот оператор. Если процедура P содержит явное обращение к самой себе, то она называется прямо рекурсивной; если Р содержит обращение к процедуре Q, которая содержит (прямо или косвенно) обращение к Р, то Р называется косвенно рекурсивной.    

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

P=if B then  Р [Si,Р]

или

Р= Р [Si, if B then P]

   Основной способ доказать, что выполнение операторов цикла когда-либо заканчивается, - определить, функцию f(x) (x- множество переменных программы), такую, что f(x)<=0 удовлетворяет условию окончания цикла (с предусловием или с постусловием), и доказать, что при каждом повторении f(x) уменьшается. Точно также можно доказать, что выполнение рекурсивной процедуры Р когда-либо завершится, показав, что каждое выполнение Р уменьшает f(x). Наиболее надежный способ обеспечить окончание процедуры - связать с Р параметр (значение), скажем n, и рекурсивно вызывать Р со значением этого параметра n-1. Тогда замена условия В на n>0 гарантирует окончание работы.

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

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

Пример рекурсивной функции -

функции вычисление целой степени вещественного числа а (y=a^x)

function pow (a:real;x:ineger): real;

begin

if x=0 then 

pow:=1 

else

if x>0 then

pow:=pow(a,x-1)*a

else

pow:=pow(a,x+1);

end;

Задание на тему "Рекурсивные алгоритмы" 

Задача
Для вычисления кубического корня из положительного числа А пользуются
следующим рекуррентным соотношением:
X(n)=1/3*(2*X(n-1)+A/X(n-1)^2)
Напишите программу вычисления кубического корня. Поэкспериментируйте для различных
А, на каком шаге получается приемлемое значение кубического корня.