5. Рекурсия
151. Написать рекурсивную функцию для нахождения биномиальных коэффициентов, пользуясь их определением:
= 1,
при m = 0, n>0 или m = n 0;
= 0, при m > n 0;
= 
.
Вычислить
для k =2, 4, б, 8.
152. Задано конечное множество имен жителей некоего города, причем для каждого из жителей перечислены имена его детей. Жители Х и У называются родственниками, если
а) либо Х - ребенок У,
б) либо У - ребенок Х,
в) либо существует некий Z такой, что Х является родственником Z, а Z является родственником У.
Перечислить все пары жителей города, которые являются родственниками.
153. Подсчитать количество различных представлений заданного натурального n в виде суммы не менее двух попарно различных положительных слагаемых.Представления, отличающиеся лишь порядком слагаемых, различными не считаются.
154. Напечатать поле для игры в шахматы, в котором черные поля изображаются квадратами, заполненными 55=25 звездочками (символами '*').
155. Вычислить опрелелитель заданной
матрицы, пользуясь формулой разложения
по первой строке:
,
где матрица
получается из
вычеркиванием первой строки и k-го
столбца.
156. Напишите две функции вычисления i-го числа Фибоначчи - рекурсивную и нерекурсивную - и напечатайте таблицу для сравнения времен вычисления i-го числа Фибоначчи для с = 4, 6, 8, 10, 12 с помошью зтих функций. Используйте для этого стандартную функцию CLOCK - функцию без параметров, которая выдает целое число, равное времени (в миллисекундах) центрального процессора, уже использованного паскаль-программой.
157. Функция f(n) определена для целых положительных чисел следуюшим образом:
Вычислить f(k) для k = 15, 16, ..., ЗО.
158. Построить синтаисический анализатор для понятия простое-выражение.
простое выражение ::=
(простое-выражение знак-операции простое-выражение)
простой-идентификатор ::= буква
знак-операции::= 
159. Построить синтаксический анализатор для понятия идентификатор.
идентификатор ::=
буква
цифра
буква
идентификатор
160. Построить синтаксическнй анализатор для понятия вещественное-число.
вещественное-число ::=
целое-число . целое-без-знака
целое-число . целое-без-знака
Е целое-число
целое-число Е целое-число
целое-без-знака ::= цифра { цифра }*
целое-без-знака
целое-без-знака
целое-число::=
161. Построить синтаксический анализатор для понятия простое-логическое.
простое-логическое::=
TRUE
FALSE
простой-идентификатор
NOT простое-логическое
(простое-логическое знак-операции
простое-логическое)
простой-идентификатор::= буква
знак-операции::= 
162. Написать программу, которая по заданному простому-логическому выражению (определение понятия содержится в формулировке предыдущей задачи), не содержащему вхождений простых идентификаторов, вычисляет и печатает значение этого выражения.
163. Построить синтаксичский аналиэатор для понятия константное-выражение.
константное-выражение::=
цифра { цифра }*
(константное-выражение
знак-операции)
164. Написать программу, которая но заданному константному-выражению (определение понятия содержится в формулировке предыдущей задачи) вычисляет и печатает либо значение этого выражения, либо сообщение “при вычислении константного выражения получен промежуточный результат, превосходящий по модулю миллион”.
165. Используя рекурсивную процедуру, распечатать на устройстве вывода следующую картинку:
АААААААААА ..............................АААААААААА (120 раз)
ВВВВВВВВ.................................ВВВВВВВВ (116 раз)
СССССС................................СССССС (112 раз)
DDDD................................DDDD (108 раз)
................................
YYYY............YYYY (24 раза)
ZZ............ZZ (20 раз)
YYYY............YYYY (24 раза)
ХХХХХХ............ХХХХХХ (28 раз)
................................
ВВВВВВВВ................................ ВВВВВВВВ (116 раз)
АААААААААА ............................... АААААААААА (120 раз)
166. Построить синтаксический анализатор для понятия скобки.
квадр
кругл
скобки::=
[кругл кругл]
+
[квадр квадр]
‑
167. Построить синтаксический анализатор для понятия список-списков.
список-списков::= список {; список }
список::= элемент {; элемент} *
элемент::= буква
168. Функция Ф преобразования текста определяется следующим образом:
Ф(a) = Ф(, если , где текст не содержит вхождений символа “;”
или
Ф() = , если в нет вхождений символа “;”.
Реализовать функцию Ф с помощью рекурсивной процедуры.
169. Функция Ф преобразования вектора целых определяется следующим образом:
Ф(a) = , если =1;
Ф(a) = ab, если =2, =ab и a b;
Ф(a) = ba, если =2. =ab и b < a;
Ф(a) = Ф()Ф(), если >2, = и = или = + 1.
Отметим, что функция Ф преобразует вектор, не меняя его длину. Реализовать функцив Ф с помощью рекурсивной процедуры.
Пример: Ф(1, 2, 3, 4, 5, 6, 7) = 1, 2, 3, 4, 5, 6, 7.
170. функция Ф преобразования вектора целых определяется следуюшим образом:
Ф(a) = , если <2;
Ф(a) = Ф()Ф(), если = , = , >2;
Ф(a) = Ф(a)Ф(a), если = a, = , >2, =1.
Отметим, что функция Ф может удлинять вектор. Реализовать функцию Ф с помощью рекурсивной процедуры.
Примеры:
Ф (1,2,3,4,5,6,7,8,9) = 1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9
Ф (1,2,3,4,5,6,7,8) = 1,2,3,4,5,6,7,8.
171. Построить синтаксический анализатор для понятия список-параметров.
список-параметров::= параметр { , параметр }*
имя = цифра цифра
имя= (список-параметров)
параметр::=
имя::= буква буква буква
172. Для заданного целого N вычислить значение суммы:
с помощью рекурсивной функции.
173. Построить синтаксический анализатор для понятия скобки.
квадр
кругл
скобки::=
[кругл кругл]
+
квадр::=
[квадр квадр]
‑
кругл::=
167. Построить синтаксический анализатор для понятия список-списков.
список-списков::= список {; список }
список::= элемент {; элемент} *
элемент::= буква
174. Построить синтаксический анализатор для понятия сумма.
сумма::= целое {знак-операции} *
целое::= цифра {цифра} *
знак-операции::=
Например, 021 + 16 и 22 - суммы, а+1 - не сумма.
175. Написать программу, которая по заданной сумме (определение понятия содержится в формулировке предыдущей задачи) вычисляет и печатает либо значение этой суммы, либо сообщение “при вычислении суммы получен промежуточный результат, превосходящий по модулю миллион”.