Рекурсия: Методические указания по курсу ''Информатика''

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Н.И. АМЕЛИНА, А.А.ЧЕКУЛАЕВА

РЕКУРСИЯ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу

«ИНФОРМАТИКА» для студентов 1 курса дневного и вечернего отделений факультета математики, механики и компьютерных наук

Ростов-на-Дону 2008 3

Методические указания разработаны сотрудниками кафедры прикладной математики и программирования старшим преподавателем Н.И. Амелиной и старшим преподавателем А.А. Чекулаевой.

Печатается в соответствии с решением кафедры прикладной математики и программирования факультета математики, механики и компьютерных наук ЮФУ, протокол № 9 от 29 мая 2008 г.

4

СОДЕРЖАНИЕ 1 Рекурсия ...................................................................................................... 4 1.1 Рекурсивные описания и процессы ................................................ 4 1.2 Косвенная рекурсия.......................................................................... 5 1.3 Сравнение рекурсии и итерации..................................................... 6 2 Примеры рекурсивных подпрограмм ...................................................... 8 3 Задачи ........................................................................................................ 28 4 Индивидуальные задания........................................................................ 34 ЛИТЕРАТУРА.............................................................................................. 38

5

1 РЕКУРСИЯ

Рекурсия – это способ описания объектов или вычислительных процессов через самих себя. 1.1 Рекурсивные описания и процессы Многие математические функции можно описать рекурсивно:

⎧ 1, n != ⎨ ⎩(n − 1) !⋅ n,

если n = 0 если n > 0

⎧ 1, xn = ⎨ n −1 ⎩x ⋅ x ,

если n = 0 если

n>0

Рекурсивное программирование позволяет описать повторяющийся процесс без явного использования операторов цикла, например: function Fact(n: integer): integer; begin if n=0 then Fact:=1 else Fact:= Fact (n-1) * n end; Рекурсивное описание должно содержать хотя бы одну альтернативу, не использующую рекурсивный вызов, то есть явное определение для некоторых значений аргументов подпрограммы. Эта альтернатива – нерекурсивный случай – завершает последовательность рекурсивных вызовов. В противном случае процесс вычислений будет бесконечным. Другая форма рекурсии – рекурсивное обращение, когда процесс описывается через подпроцессы, один из которых идентичен основному процессу.

6

j

⎛ n i⎞ Например, нужно вычислить S = ∑ ⎜ ∑ x ⎟ Пусть функция Sum(n,x) j =1 ⎝ i =1 ⎠ m

n

вычисляет

∑x i =1

i

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

му : S := Sum (m, Sum (n,x)); Оба типа рекурсии могут присутствовать одновременно. Пример такого сочетания – функция Аккермана:

если m = 0, ⎧n + 1, ⎪ A(m, n) = ⎨ A(m − 1, 1), если m > 0, n = 0, ⎪ A(m − 1, A(m, n − 1)), если m > 0, n > 0. ⎩ Нерекурсивная реализация функции Аккермана потребует использования матрицы для хранения промежуточных значений. Рекурсия – очень мощный инструмент решения многих задач, но применять её следует только тогда, когда природа самой решаемой задачи рекурсивна. 1.2 Косвенная рекурсия Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. Согласно правилам языка Паскаль каждый идентификатор перед употреблением должен быть описан. Поэтому в случае взаимного обращения подпрограмм друг к другу необходимо использовать опережающее описание. Опережающее описание заключается в том, что объявляется только заголовок подпрограммы, а ее тело заменяется зарезервированным словом forward. Следовательно, далее можно использовать обращение к подпрограмме, так как известны ее формальные параметры. 7

Тело подпрограммы начинается заголовком без указания ранее приведенного списка формальных параметров (и типа результата в случае функции). Пример косвенной рекурсии (см. также раздел 2 Пример 12): procedure B( j:integer); forward; procedure A( i:integer); begin . . . . . . . . B(i); . . . . . . . . end; { конец A} procedure B ; begin . . . . . . . . A(j); . . . . . . . . end; { конец B } Опережающее описание нужно использовать всегда, когда вызывающая подпрограмма ( в приведенном примере процедура A ) описана текстуально раньше, чем вызываемая ( процедура B ). 1.3 Сравнение рекурсии и итерации Итерация и рекурсия основаны на управляющих структурах: итерация использует структуру повторения, рекурсия использует структуру ветвления. И итерация, и рекурсия подразумевают повторение: итерация использует структуру повторения явным образом, рекурсия – посредством повторных вызовов подпрограммы.

8

Итерация и рекурсия включают проверку на завершение: итерация завершается, когда перестаёт выполняться условие продолжения цикла, рекурсия завершается, когда распознаётся нерекурсивный случай. Как итерация, так и рекурсия приближаются к завершению постепенно. Итерация с её проверкой повторения продолжает выполнять тело цикла, пока условие продолжения цикла не будет нарушено. Рекурсия продолжает производить более простые варианты первоначальной задачи, пока не будет достигнут нерекурсивный случай. И итерация, и рекурсия может происходить бесконечно: итерация попадает в бесконечный цикл, если условие продолжения цикла никогда не становится ложным; рекурсия продолжается бесконечно, если шаг рекурсии не редуцирует задачу таким образом, что задача сходится к нерекурсивному случаю. Рекурсия имеет отрицательные стороны. Она многократно инициализирует механизм вызова подпрограммы и увеличивает связанные с ним расходы процессорного времени и памяти (каждое рекурсивное обращение создаёт копию её параметров и локальных объектов). Итерация обычно происходит в пределах подпрограммы, так что здесь нет расходов на повторные вызовы подпрограммы и дополнительное выделение памяти. Отладка рекурсивной подпрограммы вызывает большие трудности, чем отладка итерационной подпрограммы. Любая проблема, которая может быть решена рекурсивно, может быть также решена и итеративно ( не рекурсивно). Рекурсивный подход предпочтительнее итеративного в тех случаях, когда рекурсия более естественно отражает математическую сторону задачи и приводит к программе, которая проще для понимания. Другой причиной для выбора рекурсивного решения является то, что итеративное решение может не быть очевидным.

9

2 ПРИМЕРЫ РЕКУРСИВНЫХ ПОДПРОГРАММ Пример 1 Используя рекурсивную процедуру, вычислить сумму S =1+

1 1 1 + + ⋅⋅⋅ + n 2 3

program Rec_1; var n: integer; Sm: real; procedure SumRec( n:integer; var S: real); begin if n=1 then S:=1 else begin SumRec( n-1, S ); S:=S+1/n end end; begin write('n='); readln (n); SumRec( n, Sm ); writeln('Сумма =',Sm:10:8) end. Можно проследить, как работает процедура SumRec, например, для n=5. Оператор процедуры в этом случае будет таким: SumRec( 5, Sm );

10

При выполнении тела процедуры сформируются следующие два оператора: SumRec( 4, Sm ); Sm:=Sm+1/5; Новый оператор процедуры SumRec(4, Sm)заставляет снова обратиться к выполнению этой же процедуры, что приводит к появлению новой пары операторов: SumRec( 3, Sm ); Sm:=Sm+1/4; Sm:=Sm+1/5; После выполнения еще двух обращений ситуация окажется следующей: SumRec( 1, Sm ); Sm:=Sm+1/2; Sm:=Sm+1/3; Sm:=Sm+1/4; Sm:=Sm+1/5; Затем при очередном выполнении оператора процедуры SumRec(1, Sm) выполнится оператор присваивания Sm:=1 и рекурсивные обращения прекратятся. В результате сформируется следующая последовательность операторов: Sm:=1; Sm:=Sm+1/2; Sm:=Sm+1/3; Sm:=Sm+1/4; Sm:=Sm+1/5. Эта последовательность операторов и дает результат вычисления суммы: Сумма =2.28333333

11

Рекурсивную процедуру SumRec следует рассматривать как иллюстрацию аппарата рекурсии. Итеративная (нерекурсивная) процедура для нахождения суммы гораздо проще, эффективнее и естественнее: procedure Sum( n: integer; var S: real); var i: integer; begin S=1; for i:=2 to n do S:=S+1/n end; Пример 2 Описать рекурсивную функцию для возведения числа в целую положительную степень:

⎧ 1, xn = ⎨ n −1 ⎩x ⋅ x ,

если n = 0 если

n>0 3

Используя эту функцию, вычислить 2 . program Rec_2_1; function Pow( x:real; n:integer): real; begin if n=0 then Pow:=1 else Pow:=x*Pow(x,n-1) end; begin writeln('Pow(2,3)=',Pow(2,3)) end. Результат работы программы Rec_2_1: Pow(2,3)=8 12

Можно исследовать, как выполнятся рекурсивная функция: сколько прямых и обратных шагов выполняется, и при каких значениях параметров. При изменении функции в список параметров процедуры Pow добавляется параметр i – номер вызова функции. Значения параметров будут выводиться в начале очередного выполнения тела функции (прямой ход) и перед выходом из него (обратный ход). Программа с измененной функцией: program Rec_2_2; var i: integer; function Pow1(var i: integer; x: real; n: integer):real; begin i:=i+1; writeln('прямой ход','

i=',i,'

x=',x,'

n=',n);

if n=0 then begin writeln(' --------------------------------'); writeln('завершение рекурсивных вызовов', '

i=',i,'

n=',n);

writeln(' --------------------------------'); Pow1:=1 end else Pow1:=x*Pow1(i,x,n-1); writeln('обратный ход','

i=',i,'

n=',n); i:=i-1

end; begin i:=0; writeln('Pow1(i,2,3)=',Pow1(i,2,3)) end. 13

Результат работы программы Rec_2_2: прямой ход i=1 x=2 n=3 прямой ход i=2 x=2 n=2 прямой ход i=3 x=2 n=1 прямой ход i=4 x=2 n=0 ---------------------––––––––––завершение рекурсивных вызовов i=4 n=0 -----------------------––––––––– обратный ход i=4 n=0 обратный ход

i=3 n=1

обратный ход

i=2 n=2

обратный ход

i=1 n=3

Pow1(i,2,3)=8 Упражнения 1)

Проверить, как будет вести себя программа, если использовать вызов функции Pow1(0,2,3).

2)

Какое исправление нужно внести в описание функции, чтобы вызов Pow1(0,2,3) не давал сообщений об ошибке?

3)

Поставить в функции Pow1 строку выдачи writeln('прямой ход','

i=',i,'

x=',x,'

n=',n);

непосредственно перед рекурсивным вызовом и проанализировать изменения в выводе. 4)

Поставить в функции Pow1 строку выдачи writeln('прямой ход','

i=',i,'

x=',x,'

n=',n);

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

14

5)

Поставить в функции Pow1 строку выдачи writeln('обратный ход','

i=',i,'

n=',n); i:=i-1

непосредственно перед рекурсивным вызовом и проанализировать изменения в выводе. 6)

Описать рекурсивную функцию Pow(x,n) от вещественного x (x≠0) и целого n, которая вычисляет величину xn по формуле ⎧1 ⎪ n x = ⎨ 1/ x ⎪ x * x n −1 ⎩ n

при n = 0 при n < 0 при n > 0

Пример 3 Для решения задачи, рассмотренной в Примере 2, можно использовать более эффективное рекурсивное определение xn, охватывающее случай n < 0 :

если n = 0, ⎧1, ⎪ n/2 2 ⎪( x ) , если n > 0, n − четное, xn = ⎨ n −1 ⎪ x ⋅ x , если n > 0, n − нечетное, ⎪1 x n , если n < 0. ⎩ function Power(x: real; n: integer): real; begin if n=0 then Result:=1 else if n<0 then Result:=Power(x,-n) else if odd(n) then Result:=x*Power(x,n-1) else Result:=sqr(Power(x,n div 2)) end;

15

Недостаток этой функции состоит в том, что переменная x не меняется, но передается в каждый рекурсивный вызов. Чтобы устранить бесполезную передачу неизменяемого параметра в рекурсивный вызов, достаточно сделать переменную x глобальной по отношению к рекурсивной функции. Для этого следует вложить в нерекурсивную функцию Power рекурсивную функцию Power0(n): function Power(x: real; n: integer): real; function Power0(n: integer): real; begin if n=0 then Result:=1 else if n<0 then Result:=Power(x,-n) else if odd(n) then Result:=x*Power0(n-1) else Result:=sqr(Power0(n div 2)) end; begin Result:=Power0(n) end;

16

Пример 4 Описать и использовать функцию вычисления числа Фибоначчи с номером n. Как известно, определение чисел Фибоначчи рекурсивно:

⎧1, n = 0, 1 fn = ⎨ ⎩ f n −1 + f n−2 , n > 1. program Rec_4; var n, f: integer; function Fib(n: integer): integer; begin if (n=0) or (n=1) then Fib:=1 else Fib:= Fib(n-1)+ Fib(n-2) end; begin write('Введите целое число '); readln(n); f:= Fib(n); writeln(n, '-е число Фибоначчи равно ', f) end. Однако, такое решение крайне неэффективно, поскольку содержит большое количество повторяющихся вычислений.

17

Например, дерево рекурсивных вызовов для вызова Fib (7) будет иметь следующий вид:

Из рисунка видно, что, Fib(5) вычисляется дважды, Fib(4) – трижды, Fib(3) – 5 раз и т.д. То есть количество повторных вызовов представляет собой также последовательность чисел Фибоначчи! Пример 5 Выдать цифры заданного натурального числа в порядке их следования (слева направо). program Rec_5; var n: integer; procedure Digit_rec(n: integer); begin if n div 10 <> 0 then begin Digit_rec(n div 10) write(n mod 10,' '); end else writeln(n mod 10) end; 18

begin writeln('Введите натуральное число'); readln(n); Digit_rec(n); end. Упражнения 1)

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

2)

Выдать все нечётные цифры заданного натурального числа в порядке их следования (слева направо). Пример 6 Вводится с клавиатуры последовательность ненулевых целых

чисел, за которыми следует 0. Используя рекурсивную процедуру без параметров, выдать сначала все отрицательные числа, затем все положительные. program Rec_6; procedure Print; var x: integer; begin read(x); if x<>0 then begin if x<0 then write(x,' '); Print; if x>0 then write(x,' ') end end;

19

begin writeln('Введите последовательность ненулевых ', 'целых чисел, за которыми следует 0'); Print; writeln end. Пример 7 Последовательность положительных вещественных чисел, за которыми следует 0, вводится с клавиатуры. Используя рекурсивную функцию без параметров, найти их сумму. program Rec_7; function Sum: real; var x: real; begin read(x); if x=0 then Sum:=0 else Sum:=x+Sum end; begin writeln('Введите последовательность положительных ', 'чисел, за которыми следует 0'); writeln(Sum); end.

20

Пример 8 Вводится с клавиатуры без ошибок формула следующего вида: <формула> ::= <цифра> | (< формула > <знак> < формула >) <знак> ::= + | – | * <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Используя рекурсивную функцию без параметров, вычислить значение вводимой формулы. program Rec_8; function Formula: integer; var c, op: char; { op – знак операции } x, y: integer; begin read(c); if (c>='0') and (c<='9') then {цифра - формула} Formula:=ord(c)-ord('0') else { начало формулы вида (x op y) } begin x:=Formula; read(op); y:=Formula; case op of '+': Formula:=x+y; '-': Formula:=x-y; '*': Formula:=x*y; end; read(c) {пропуск скобки ')'} end end; 21

begin writeln('Введите формулу'); writeln('Значение = ',Formula) end. Контрольные примеры 1) 5

Значение = 5

2) (( 2 – 4 ) * 6 )

Значение = –12

3) ((( 2 + 4 )*3) – 5 ) Значение = 13 Пример 9 Вычислить квадратный корень y =

x из заданного положи-

тельного числа x. Для вычисления приближенного значения y можно использовать рекуррентную формулу:

1 x y n = y n−1 + ( − y n−1 ) , n = 1,2,... 2 y n−1 y0 – произвольное положительное число (например, 1, x, x / 2 ). Вычисления можно прекратить при выполнении условия | yn – yn-1 |< eps /2. Рекуррентную формулу и условие окончания процесса вычислений можно преобразовать:

yn = x y n−1

1 x ( + y n−1 ), 2 y n−1 − y n−1 < eps .

22

program Rec_9; var x, y, eps: real; function Sq(x,y,eps: real):real; begin if abs(x/y-y)<eps then Sq:=y else Sq:=Sq(x,(x/y+y)/2, eps) end; begin writeln('Введите x и eps'); readln(x,eps); y:=Sq(x,x/2,eps); writeln('Квадратный корень=',y:8:4) end. Пример 10 Описать рекурсивную функцию, которая n раз вызывает заданную функцию f (x): fn ( n , x )=f ( f (…f (x) ) ) Для сравнения описать нерекурсивную функцию, n раз вызывающую заданную функцию f (x). Используя рекурсивную и нерекурсивную функции, вычислить значение ( ( x2 ) 2 ) 2 . program Rec_10; type func = function (x:real):real; var x:real;

23

function f(x:real):real; begin f:=x*x end; function Fn(n:integer;x:real; f:func):real; begin if n>1 then Fn:=f(Fn(n-1,x,f)) else Fn:=f(x) end; function Fn1(n:integer;x:real; f:func):real; var i:integer; begin for i:=1 to n do x:=f(x); Fn1:=x end; begin write('Введите x '); readln(x); writeln(' Обращение к рекурсивной функции:'); writeln(Fn(3,x,f)); writeln(' Обращение к нерекурсивной функции:'); writeln(Fn1(3,x,f)) end.

24

Контрольные примеры 1) x = 2 ( ( x2 ) 2 ) 2 = 162 = 256 2) x = 3 ( ( x2 ) 2 ) 2 = 812 = 6561 Пример 11 Описать рекурсивную и нерекурсивную функции вычисления значения по формуле: 1 + 2 + 3 + ... + n

Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты. program Rec_11; var n:integer; function f_rec(n,i:integer):real; begin if i=n then f_rec:=sqrt(n) else f_rec:=sqrt(i+f_rec(n,i+1)) end; function f_nrec(n:integer):real; var i:integer; s:real; begin s:=0; for i:=n downto 1 do s:=i+sqrt(s); f_nrec:=sqrt(s) end; 25

begin write('n='); readln(n); writeln(f_rec(n,1)); writeln(f_nrec(n)) end. Пример 12 Вводится с клавиатуры посимвольно без ошибок выражение. Признак окончания ввода – точка. Вид выражения определен следующим образом: <выражение>::=<слагаемое> | <слагаемое> ± <слагаемое> <слагаемое>::=<множитель> | <множитель> * <множитель> <множитель>::=<идентификатор> | (<выражение>) <идентификатор>::=<буква> Преобразовать выражение в постфиксную форму записи. Постфиксная запись (польская инверсная запись – ПОЛИЗ) – бесскобочная запись арифметических выражений, при которой знак операции ставится после операндов. Примеры преобразований: (A+B)*(C-D)

→

AB+CD-*

A+B*(C-D)

→

ABCD-*+

A+B*C-D

→

ABC*+D-

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

26

В случае взаимного обращения подпрограмм (процедур или функций) друг к другу необходимо использовать опережающее описание. Опережающее описание подпрограммы состоит из ее заголовка, за которым идет зарезервированное слово forward. program Rec_12;

{ Иллюстрация косвенной рекурсии }

procedure Postfix;

{ Преобразование в ПОЛИЗ }

var ch: char;

{хранит символ}

procedure Find;

{процедура пропуска пробелов}

begin repeat read(ch) until ch<>' ' end; procedure Expression;

{выражение}

var op: char;

{знак операции}

procedure Factor; forward; {опережающее описание} procedure Term;

{слагаемое}

begin Factor; while ch='*' do begin Find; Factor; write('*')

{вывод *}

end end; {Term}

27

procedure Factor;

{множитель}

begin if ch='(' then begin Find; Expression; end else write(ch);

{вывод буквы - идентификатора}

Find end; {Factor} begin {Expression} Term; while (ch='+') or (ch='-') do begin op:=ch; Find; Term; write(op)

{вывод знака}

end end; {Expression} begin {Postfix} Find; write(' '); repeat Expression until ch='.'; writeln end; {Postfix} 28

begin {основная программа} Postfix end. Упражнения 1)

Можно ли поменять описание процедур Factor и Term местами? Необходимо ли при этом использовать опережающее описание?

2)

В программе Rec_13 процедуры Factor и Term описаны внутри процедуры Expression. Сделать все три процедуры одного уровня вложенности в процедуре Postfix.

29

3 ЗАДАЧИ 1.

Описать рекурсивную функцию C(m,n), где 0 ≤ m ≤ n, для вычисления биномиального коэффициента C nm по следующей формуле:

C n0 = C nn = 1; C nm = C nm−1 + C nm−−11 при 0 < m < n. 2.

Описать рекурсивную функцию NOD, которая возвращает наибольший общий делитель ( НОД ) чисел x и y. НОД для x и y определяется рекурсивно следующим образом: если y = 0 ⎧ x, ⎩ NOD( y, x% y ), если y ≠ 0

а) NOD( x, y ) = ⎨

где % – операция вычисления остатка от деления нацело; x ⎧ ⎪ б) NOD( x, y ) = ⎨ NOD( x − y, y ) ⎪ NOD( x, y − x) ⎩

3.

, если x = y , если x > y , если x < y

Описать рекурсивную функцию root(f,a,b,eps), которая находит приближенное значение корня заданной функции f(x) на отрезке [ a, b] методом деления отрезка пополам. Считать, что a < b, f (a) · f (b) <0 и f(x) – непрерывная и монотонная функция на отрезке [ a,b ].

4.

Функция f(n) определена для целых положительных чисел следующим образом:

1 , n =1 ⎧ ⎪ n n f ( n) = ⎨ f ( ), если n > 2 ∑ ⎪⎩ i = 2 i Описать рекурсивную функцию для вычисления f(n)и вычислить f(k) для

k=15, 16,…, 30.

30

5.

Описать рекурсивную функцию Аккермана: если m = 0, ⎧n + 1, ⎪ A(m, n) = ⎨ A(m − 1, 1), если m > 0, n = 0, ⎪ A(m − 1, A(m, n − 1)), если m > 0, n > 0. ⎩

Найти значение функции для некоторых (малых!) целых неотрицательных значений m и n. 6.

Функция Мак-Карти для целых n описывается так: function McC(n:integer): integer; begin if n > 100 then McC:=n-10 else McC:= McC (McC (n+11)) end; Вычислить McC(100), McC(99), McC(95), McC(105), McC(0), McC(–5). Проанализировав полученные результаты, получить нерекурсивное определение функции McC(n).

7.

Описать рекурсивную процедуру, которая выводит первые n строк числового треугольника Паскаля. Треугольником Паскаля называется числовой треугольник, в котором по краям стоят единицы, а каждое число внутри равно сумме двух стоящих над ним в ближайшей строке сверху. Например, ниже приведен числовой треугольник Паскаля для n=5. 1 1 1 1 2 1 1 1

3 4

3 1 6

4

1

Используя процедуру, выдать k различных треугольников Паскаля. 31

8.

Используя рекурсивную процедуру, выдать построчно следующие последовательности прописных латинских букв: AAAA············AAAA BBB············BBB CC············CC ······ XXXXXX YYYY ZZ YYYY XXXXXX ······ BBB············BBB AAAA············AAAA

9.

52 раза 50 раз 48 раз 6 раз 4 раза 2 раза 4 раза 6 раз 50 раз 52 раза

Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Проверить, является ли этот текст правильной записью формулы. Формула определяется следующим образом: <формула> ::= <цифра> | (< формула > <знак> < формула >) <знак> ::= + | – | * <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

10. Вводится с клавиатуры без ошибок логическое выражение вида: <логическое выражение> ::= true | false | <операция> (<операнды>) <операция> ::= not | and | or <операнды> ::= <операнд> | <операнд>, <операнды> <операнд> ::= <логическое выражение> Используя рекурсивную функцию без параметров, вычислить значение вводимого логического выражения.

32

Примечание. У операций and и or может быть любое число операндов, у not – только один. Например, значения выражений равны: not(and(true,or(true,false),false)) – true, and(or(false,not(false)),true,not(true)) – false. 11. Вводится с клавиатуры последовательность символов (текст), за которым следует точка. Проверить, является ли этот текст правильной записью логического выражения. Логическое выражение определяется следующим образом: <логическое выражение> ::= true | false | <операция> (<операнды>) <операция> ::= not | and | or <операнды> ::= <операнд> | <операнд>, <операнды> <операнд> ::= <логическое выражение> Примечание. У операций and и or может быть любое число операндов, у not – только один. Например, not(and(true,or(true,false),false)) – правильная запись, not(and(true,or(true,false),false) – неправильная запись, not(and(true,or(true,false)),false) – неправильная запись. 12. Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Проверить, удовлетворяет ли его структура следующему определению: <текст> ::= <элемент> | <элемент> <текст> <элемент> ::= a | b | (<текст>) | [<текст>] | {<текст>} Например, a({a(ba)bb[ab]}(aba)) – правильная запись, a({a(ba)bb[ab}](aba)) – неправильная запись, a({a(ba)bb[ab]}(aba) – неправильная запись. 33

13. Описать рекурсивную функцию, которая определяет, является ли заданное натуральное число простым. Используя эту функцию вывести все простые числа на заданном интервале [a, b]. 14. Вводится с клавиатуры последовательность из n символов – цифр. Описать рекурсивную функцию, которая превращает последовательность символов в целое число. Использовать функцию для вычисления нескольких чисел с различным количеством значащих цифр. 15. Описать рекурсивную и нерекурсивную функции вычисления значения по формуле: 1 + 3 + 5 + ... + 2n + 1

Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты. 16. Описать рекурсивную и нерекурсивную функции вычисления значения по формуле: 2 + 4 + 6 + ... + 2n

Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты. 17. Описать рекурсивную и нерекурсивную функции вычисления значения цепной дроби: 1 1

1+ 2+

1 3 + ... +

1 n

Используя эти функции, вычислить значения цепной дроби при различных

n > 5 и сравнить результаты. 34

18. Описать рекурсивную и нерекурсивную функции вычисления значения цепной дроби: 1 1

2+ 4+

1 6 + ... +

1 2n

Используя эти функции, вычислить значения цепной дроби при различных

n > 3 и сравнить результаты. 19. Описать функцию построения синтаксического анализатора для понятия идентификатор < буква > ⎧ ⎪ ⎧< цифра > < идентификатор >:= ⎨ < идентификатор > ⎨ ⎪ ⎩ < буква > ⎩

Использовать функцию для синтаксического анализа заданных слов.

35

4 ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ 1)

Используя рекурсивную функцию, найти n-ый элемент последовательности xn = 3 ∗ xn -1 , x0 = 1.

2)

Используя рекурсивную функцию, найти сумму первых n элементов последовательности xn = 3 ⋅ xn -1 , x0 = 1.

3)

Используя рекурсивную функцию, найти максимальный из первых n элементов последовательности

4)

Используя рекурсивную функцию, выдать первые n элементов последовательности

5)

xn = 5 ⋅ xn -1 + 1, x0 = 0 , которые меньше заданного числа m.

Используя рекурсивную функцию, выдать первые n элементов последовательности

6)

xn = 5 ⋅ xn -1 + 1, x0 = 0.

xn = 5 ⋅ xn -1 - 20, x0 = 2 , которые больше заданного числа m.

Используя рекурсивную функцию, найти максимальный элемент из n элементов последовательности целых чисел, вводимых с клавиатуры.

7)

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

8)

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

9)

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

36

10) Вводится с клавиатуры непустая последовательность положительных вещественных чисел, за которой следует отрицательное число. Используя рекурсивную

функцию

без

параметров,

найти

произведение

этих

положительных чисел. 11) Вводится с клавиатуры непустая последовательность положительных вещественных чисел, за которой следует отрицательное число. Используя функцию без параметров, найти среднее арифметическое этих положительных чисел. Примечание. Для нахождения среднего арифметического использовать нерекурсивную функцию, вызывающую в своем теле рекурсивную процедуру нахождения суммы и количества положительных вещественных чисел 12) Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Используя рекурсивную процедуру без параметров, выдать все символы текста (без точки) в обратном порядке. 13) Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Используя рекурсивную процедуру без параметров, выдать в обратном порядке все цифры, встречающиеся в тексте. 14) Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Используя рекурсивную процедуру без параметров, выдать в обратном порядке все латинские буквы, встречающиеся в тексте. 15) Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Используя рекурсивную функцию без параметров, подсчитать количество цифр, встречающихся в тексте. 16) Вводится с клавиатуры последовательность символов (текст), заканчивающаяся точкой. Используя рекурсивную функцию без параметров, подсчитать количество строчных латинских букв, встречающихся в тексте.

37

17) Описать рекурсивную функцию нахождения n-го члена арифметической прогрессии по первому члену прогрессии и разности прогрессии и номеру члена прогрессии n. Применить функцию для нахождения n-го члена арифметической прогрессии m раз, задавая каждый раз первый член прогрессии, разность прогрессии и целое число n. 18) Описать рекурсивную функцию нахождения суммы первых n членов арифметической прогрессии по первому члену прогрессии, разности прогрессии и номеру члена прогрессии n. Применить функцию для нахождения суммы

n членов арифметической прогрессии m раз, задавая каждый раз первый член прогрессии, разность прогрессии и целое число n. 19) Описать рекурсивную функцию для нахождения n-го члена геометрической прогрессии по первому члену прогрессии, знаменателю прогрессии и номеру члена прогрессии n. Применить функцию для нахождения n-го члена геометрической прогрессии m раз, задавая каждый раз первый член прогрессии, знаменатель прогрессии и целое число n. 20) Описать рекурсивную функцию нахождения суммы первых n членов геометрической прогрессии по первому члену прогрессии, знаменателю прогрессии и номеру члена прогрессии n. Применить функцию для нахождения суммы n членов геометрической прогрессии m раз, задавая каждый раз первый член прогрессии, знаменатель прогрессии и целое число n. 21) Описать рекурсивную и нерекурсивную функции вычисления значения по формуле: n + n − 1 + ... + 1

Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты.

38

22) Описать рекурсивную и нерекурсивную функции вычисления значения по формуле: 2n + 2n − 2 + ... + 2

Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты. 23) Описать рекурсивную и нерекурсивную функции вычисления значения по формуле:

2n + 1 + 2n − 1 + ... + 1 Используя эти функции, вычислить значения для различных n > 3 и сравнить результаты. 24) Описать рекурсивную и нерекурсивную функции вычисления значения цепной дроби: 1 1

n+

1

n −1+

n − 2 + ... +

1 2+

1 1

Используя эти функции, вычислить значения цепной дроби при различных n > 5 и сравнить результаты. 25) Описать рекурсивную и нерекурсивную функции вычисления значения цепной дроби: 1 1

2n + 2n − 2 +

1 2n − 4 + ... +

1 2

Используя эти функции, вычислить значения цепной дроби при различных n > 3 и сравнить результаты.

39

ЛИТЕРАТУРА

1 Абрамов С.А. Начала информатики / С.А. Абрамов, Е.В. Зима – М.: Наука, 1989. –256 с. 2 Баррон Д. Рекурсивные методы в программировании. – М.: Мир, 1974. – 80 с. 3 Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.–360 с. 4 Задачи по программированию / С.А. Абрамов и др. – М.: Наука, 1988. – 224 с. 5 Задачи по программированию / Н.И. Амелина и др. – М.: Вузовская книга, 2000. – 104 с. 6 Йенсен К. Паскаль. Руководство пользователя и описание языка / К. Йенсен, Н.Вирт. – М.: Финансы и статистика, 1982. – 151 с. 7 Методы программирования. Учебное пособие / Н.И. Минакова, Е.С. Невская, Г.А. Угольницкий, А.А. Чекулаева, М.И. Чердынцева. – М.: Вузовская книга, 1999. – 280 с. 8 Пильщиков В.Н. Сборник упражнений по языку Паскаль. – М.: Наука, 1989. – 160 с. 9 Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: учебное пособие. – М.: КНОРУС, 2006. – 576 с.

40