Вопрос 38: Рекурсия в Паскале.

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

Любое рекурсивное определение состоит из двух частей. Одна определяет понятие через него же. Другая – через иные понятия. Рекурсивный алгоритм – это алгоритм, который при вычислении обращается сам к себе. Например: вычисление функции f(n) может потребовать вычислениеf(n-1) и еще каких-то операций. Т.е. часть алгоритма вычисления функции, есть вычисление это же функции с другими аргументами. Рекурсивные алгоритмы записываются с помощью рекурсивных процедур. Процедура называется рекурсивной, если она обращается сама к себе, прямо или косвенно.

Пример: Рекурсивное вычисление факториала.

Functionfactorial(n:integer):integer;

Begin

If n=1 then factorial:=1

Else factorial:= factorial(n-1)*n;

End;

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

Пример: Возведение действительного числа в целую степень.

Procedure power(x:real;n:integer;var y:real);

Begin

If n=0 then y:=1

Else begin

Power(x,n-1,y);

Y:=y*n;

End;

End;

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

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

Вопрос 39: Представление чисел с плавающей точкой и операции с ними.

С помощью чисел с плавающей точкой представляются действительные числа.

мантисса		порядок
Знак мантиссы	Разряды мантиссы	Знак порядка	Разряды порядка

Любое число Rможет быть представлено в виде

R=v*T^p,

где |v|<1 – мантисса (дробное число со знаком),p-порядок, Т – основание числа. Мантисса и порядок представляют в дополнительном коде, в качестве основания берется Т=2.

Например, 5=0,625*2³, тогда если для представления отведено 8 разрядов, под мантиссу и под порядок отведено по 4 разряда (старший – знаковый), получим 5=0,625*2³=0101|0011³

Одно и то же число Rможет быть представлено различными мантиссами и порядками. Например:

2=0,5*2²=0100|0010

2=0.25*2³=0010

Чтобы избежать неоднозначности, на мантиссу накладывают ограничение 0,5|V|<1, т.е. за мантиссу берется максимальное возм. По модулю другого числа.

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

Процедура сложения чисел с плавающей точкой:

1. Сравнение порядков слагаемых

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

3. Мантиссы чисел складываются

4. При необходимости выполняется нормолизация суммы.

При умножение чисел с плавающей точкой выполняется:

1. Перемножить мантиссы и округлить результат до имеющегося числа разрядов (6=0,75*2)

2. Сложить порядки 6=0,75*2=01100011

3. При необходимости выполнить нормализацию произведения.

Точность представления чисел с плавающей точкой зависит количества разрядов мантиссы, а диапазон – от количества разрядов порядка.

Типичная ситуация, когда под число отводится 32 разряда, из них 24 – старший знаковый – под мантиссу, 8 под порядки.