Задание 16

  • Процедура (функция)– это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
    • Предназначена для:
  • выполнения одинаковых действий в различных местах одной и той же программы;
  • разбивки программы (или другой процедуры или функции) на подзадачи для улучшения читаемости кода;
    • Особенности программирования процедур (функций):
  • подпрограммы располагаются всегда выше основной программы:

    • процедура

  • сначала составляется заголовок процедуры или функции, в котором перечисляются формальные параметры, они обозначаются идентификаторами, как переменные (т.к. формальные параметры могут меняться, также как переменные):
    • var x,y:integer;
{ заголовок процедуры 
с формальными переменными x и y:}
procedure Sum(x,y:integer); 
begin
 ...
end;
// основная программа
begin
  ...
end.
    var x,y:integer;
{ заголовок функции 
с формальными переменными x и y:}
function Sum(x,y:integer): integer; 
begin
  ...
end;
// основная программа
begin
 ...
end.
  • в месте вызова процедуры в круглых скобках указываются фактические параметры (числовые значения либо арифметические выражения) в том же порядке:

    • вызов процедуры

  • функция вызывается немного иначе:
    • { заголовок процедуры 
с формальными переменными x и y:}
procedure Sum(x,y:integer); 
begin
 ...
end;
// основная программа
begin
  Sum(100,200)
end.
    { заголовок функции 
с формальными переменными x и y:}
function Sum(x,y:integer): integer; 
begin
  ...
end;
// основная программа
begin
 write (Sum(100,200))
end.
  • компилятор не будет выполнять процедуру (функцию) до момента ее вызова в основной программе;
  • пример работы процедуры и функции для сложения двух значений (порядок действий компилятора указан числами):
    • var x,y:integer;
procedure Sum(x,y:integer); 
begin
//3. Выводим сумму двух запрошенных чисел
  write(x+y); 
end;
begin
// 1. запрашиваем два числа
 readln(x,y);
// 2. передаем запрошенные числа в процедуру 
 Sum(x,y)  
end.
    var x,y:integer;
function Sum(x,y:integer): integer; 
begin
{3. Суммируем два числа и присваиваем 
значение функции:}
  Sum:=x+y;
end;
begin
// 1. запрашиваем два числа
 readln(x,y);
{2. передаем запрошенные числа 
в функцию и выводим результат:} 
 write (Sum(x,y))
end.

    Подробное описание работы с процедурами можно найти, перейдя по ссылке.

  • Рекурсивной называется процедура, вызывающая сама себя:
    • procedure row(n:integer);
begin
     if n >=1 then begin
        write (n, ' ');
        row(n-1)
     end;
end;
begin
    row(10);
end.

    Для использования рекурсии, необходимо задать:

    • условие остановки рекурсии (обычно, в виде условного оператора):
      •  if n >=1 then begin
    • рекуррентную формулу (обычно, вызов самой себя с измененным параметром):
      • row(n-1)



    Решение по рекуррентной формуле

    16_1:

    Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

    F(1) = 1
F(n) = F(n–1) * (n + 2), при n > 1

    Чему равно значение функции F(5)? В ответе запишите только целое число.
      
    Типовые задания для тренировки

    :
    ✎ Решение с использованием программирования:
    PascalABC.NET (решение №1):

    1
2
3
4
5
6
7
8
9
10
11

    function F(n: integer): integer;
begin
  if n = 1 then
    F := 1
  else if n > 1 then
    F := F(n - 1) * (n + 2)
end;
 
begin
  print(F(5))
end.

    PascalABC.NET (решение №2):

    1
2
3
4
5
6
7

    function F(n:integer):integer:=
 n=1 ? 1
 :  F(n-1) * (n+2);
 
begin
  print(F(5))
end.

    Питон:

    1
2
3
4
5
6

    def F( n ):
    if n == 1: 
        return 1
    elif (n > 1):
        return F(n-1)*(n+2)
print (F(5))

    C++:

    1

     

    ✎ Решение теоретическое (методом с конца к началу):

    • Из условия задания мы имеем рекуррентную формулу: F(n–1) * (n + 2) и условие остановки рекурсии: n > 1.
    • Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 5:
      • F(5) = F(4) * 7
    • Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(1) (при котором «сработает» остановка рекурсии). Получим:
      • F(5) = F(4) * 7
       F(4) = F(3) * 6
              F(3) = F(2) * 5
                     F(2) = F(1) * 4
                              1
    • На F(2) необходимо остановиться, так как действует условие остановки рекурсии: формула работает для n > 1. Также учтем, что по условию F(1) = 1.
    • Теперь с конца к началу перепишем все получившиеся сомножители и перемножим их:
      • 1 * 4 * 5 * 6 * 7 = 840

    Результат: 840

    16_2:

    Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

    F(0) = 1, F(1) = 1
F(n) = 2 * F(n–1) + F(n-2), при n > 1

    Чему равно значение функции F(6)? В ответе запишите только целое число.


    ✎ Решение с использованием программирования:
    PascalABC.NET (решение №2):

    1
2
3
4
5
6
7
8

    function F(n:integer):integer;
begin
  if (n = 0) or (n = 1) then result:=1
  else if n>1 then result:=2*F(n-1) + F(n-2);
end;
begin
  print(F(6))
end.

    ✎ Решение 1. Теоретическое (метод решения с начала к концу):

    • Из условия задания мы имеем рекуррентную формулу: 2 * F(n–1) + F(n-2) и условие остановки рекурсии: n > 1.
    • Из заданной рекуррентной формулы видим, что функция зависит от предыдущей функции (F(n–1)) и от пред-предыдущей функции (F(n-2)).
    • Так как первые два значения заданы (F(0) = 1, F(1) = 1), то можно построить таблицу последующих значений, двигаясь к числу 6:
      • n0123456
      F(n)
      2*F(n – 1)+F(n — 2)      		112*1+1 =32*3+1 =72*7+3 =172*17+7 =412*41+17 =99
    • Таким образом, получаем, что при вызове функции F(6) результатом будет число 99

    ✎ Решение 2. Теоретическое (метод решения с конца к началу):

    • Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 6:
      • F(6) = 2*F(5) + F(4)
    • Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(2) (F(1) и F(0) известны из условия задачи). Получим:
      • F(6) = 2*F(5) + F(4)
       F(5) = 2*F(4) + F(3)
              F(4) = 2*F(3) + F(2)
                     F(3) = 2*F(2) + F(1)
                              F(2) = 2*F(1) + F(0) = 2*1+1 = 3
                                        1       1
    • Теперь с конца к началу перепишем все получившиеся значения функций:
      • F(6) = 2*F(5) + F(4) = 2*41 + 17 = 99
       F(5) = 2*F(4) + F(3) + 2*17+7 = 41 ↑
              F(4) = 2*F(3) + F(2) = 2*7+3 = 17 ↑
                     F(3) = 2*F(2) + F(1) = 2*3+1 = 7 ↑
                              F(2) = 2*F(1) + F(0) = 2*1+1 = 3 ↑  
                                        1       1

    Результат: 99

Комментарии

Отправить комментарий