Пример 2. 3. Требуется вычислить по заданному натуральному n  1 число Фибоначчи F(n). Если число F(n) выходит за диапазон стандартных целых чисел (для типа Integer F(n) > MaxInt), то вычислить максимальное F(i) как в примере 2.2 (i  n).

B цикла while-do следует заменить на конъюнкцию условий продолжения из примеров 2. 1 и 2. 2: B  (i < n) & (a  (MaxInt – b)).

Соответственно, условием завершения цикла будет

Not B  (i  n) or (a > (MaxInt – b)),

т. е. дизъюнкция условия (i  n), означающего достижение переменной i последнего (требуемого) значения n, и условия (a > (MaxInt – b)), означающе-го превышение границы MaxInt следующим числом Фибоначчи F(i + 1), равным a + b. С учётом того, что переменная i в теле цикла изменяется ровно на 1, дизъюнкт (i  n) в условии окончания может быть заменен на (i = n).

{Вычисл чисел Фибоначчи с контролем диапазона типа Integer }

program Fib;

const MaxNat = MaxInt; {наиб полож число типа Integer}

var a, b, c, i, n : Integer;

begin

Writeln('Программа для нахождения N-го числа Фибоначчи');

{Ввод числа n>0}

n := 0;

while ( n <= 0 ) do { ввод полож номера числа }

begin Write('Введите номер числа Фибоначчи: '); ReadLn(n) end;

{Конец ввода n}

a := 1; b := 0; i :=1; { присваивание начальных значений a=F(1) и b=F(0)}

Write(' F ( ',i:2,' ) = ',a:7);

while ( i < n ) and ( a <= (MaxNat - b) ) do

begin{(a=F(i))&(b=F(i-1))& (a+b=F(i+1)<=MaxNat) &(1<=i<n)}

i := i + 1; c := a; a := a + b; b := c; {a - новое число Фибоначчи}

Write(' F ( ',i:2,' ) = ',a:7);

if (i mod 3 = 0) then WriteLn; { вывод чисел в 3 колонки }

{(a=F(i))&(b=F(i-1))&(a<=MaxNat) &(1<i<=n)) }

end;

{ a=F(i)) & (b=F(i-1)) & (a<=MaxNat) & ((i=n) or (i<n) & (a+b>MaxNat) }

WriteLn;

if i = n then WriteLn(N,'-е число Фибоначчи =',a)

else

begin

WriteLn(i,'-е число Фибоначчи =',a);

WriteLn(N,'-е число Фибоначчи вне диапазона типа integer')

end;

ReadLn { ожидание нажатия <Enter>}

end.

При использовании типа Integer данная программа обеспечивает расчет чисел Фибоначчи с номерами от 1 до 23 включительно.

Пример 2. 4. Для заданного целого n ≥ 0 вычислить S(n) =_i=0...n a(i) , где a(i) = A(i | m) , m — заданное целое (m ≥ n) и A(i | m) = m! / (m–i)! = =  m (m–1) … (m – i + 1).

Cумму S(i) вычислять рекуррентно: S(i + 1) = S(i) + a(i + 1). Разумно попытаться и каждое слагаемое вычислять рекуррентно, т. е. через предыдущее слагаемое. Для этого рассмотрим отношение q = a(i + 1) / a(i) = [m! / (m – i – 1)!] [(m – i)! / m!] = m – i. Таким образом, имеем рекуррентную формулу a(i + 1) = (m – i) a(i). При i = 0 имеем a(0) = m! / (m – 0)! = 1 и S(0) = 1. В программе слагаемое a(i) будет представлено переменной A, его номер i — переменной i, а формируемая сумма S(i) — переменной S. Условием прекращения вычислений является достижение i значения n или определение того, что произойдет выход за верхнюю границу диапазона представления целых чисел при вычислении очередного значения S(i), т. е. S(i) может быть вычислено только при выполнении нер-ва S + (m – i)A  MaxInt (при использовании типа Integer). Прямая проверка нер-ва невозможна, так как сумма S + (m –i) A  может превысить MaxInt, поэтому заменим нер-во на A  (MaxInt –S) / (m – i). Следует заметить, что эта замена допустима, ибо по условию задачи (n  m и i  n) в знаменателе значение m – i = 0 может быть только при проверке возможности вычисления “лишнего” S(n + 1), которую проводить не нужно. При невыполнении нер-ва булевской переменной fl присваивается значение false и выполнение цикла завершается.

{ Программа вычисляет сумму S=Sum (i=0...n) (m!/(m-i)!), m>=n>=0 }

program Summa;

const MaxNat = MaxInt; {наибольшее положительное число типа Integer}

var A, i, m, n, S : Integer; fl : Boolean;

begin N := -1;

WriteLn(' Вычисление суммы S= Sum (i=0...n) (m!/(m-i)!), m>=n>=0 ');

while ( n < 0 ) do { ввод неотрицательного числа слагаемых }

begin Write('Введите число n: '); ReadLn(n) end;

m := n-1;

while ( m < n ) do { ввод числа mn }

begin Write('Введите число m: '); ReadLn(m) end;

A := 1; S := 1; i := 0;

fl := ( m <> MaxNat );

while ( i < n ) and fl do

begin {A=a(i) & S(i)+(m-i)*A<=MaxNat }

WriteLn('i=',i:3,' a(',i,')=',A:7,' S=',S:7);

A := (m-i)*A; S := S+A; i := i+1;

if ( i < n ) then { проверка отсутствия 0 в знаменателе }

if ((MaxNat - S) div (m-i) < A) then fl := false;

{ A=a(i) & S=S(i)=a(0)+...+a(i) }

end;

Write('При i=',i,' последнее слагаемое равно ',A);

WriteLn(' Сумма равна ',S);

if fl = false then

WriteLn('При i=',i+1,' сумма вне диапазона типа Integer');

ReadLn { ожидание нажатия <Enter>}

end.

Билет №8 Вычисления с вещественными числами и машинное эпсилон №8

Вещественное число x имеет в машине двоичное представление x = ± (a₁2^–1 + a₂2^–2 + …+ a_t2^–t) 2^p , (3.3)

где a_i{0, 1} при i = 1, 2, …, t. Обычно это представление используется в нормализованном виде так, что a₁ = 1

Число  = ±(a₁2^–1 + a₂2^–2 + …+ a_t2^–t) называют мантиссой числа x. Число бит t в каждой реализации фиксировано и называется разрядностью мантиссы. Целое число p в (3.3) называют двоичным порядком. Оно, в свою очередь, также представляется в двоичном виде, и его значения находятся в некотором диапазоне L  p  U. Система чисел в представлении (3.3) задается параметрами t, L, U и будет обозначаться далее F(t, L, U). Так как мантисса  вещ. числа представляет его в усеченном виде (только t двоичных разрядов), а двоичный порядок ограничен диапазоном L...U, то представление с плавающей точкой S_i = _j = 0...i u_j.(последовательность частитичных сумм) имеет ряд важных особенностей:

1. Имеется конечное мн-во полож. чисел, представимых в системе F(t, L, U), а именно 2^t – 1(U – L + 1). Если учесть отрицательные числа и нуль, то всего имеется 22^t – 1(U – L + 1) + 1 чисел.

2. Среди чисел системы F(t, L, U) имеется макс. по величине число  = (1 – 2^–t) 2^U . Попытка вычислить в системе F(t, L, U) число x >  (или x < –) приводит к ошибке переполнения.

3. В окрестности нуля имеется зазор, где отсутствуют числа системы F(t, L, U). Самое маленькое полож. число  = 2^L – 1. Попытка вычислить в системе F(t, L, U) число x  0, такое, что |x| < , приводит к ошибке, называемой антипереполнением или исчезновением порядка.

4. Числа системы F(t, L, U) на вещественной оси расположены неравномерно. При этом отдельные группы чисел (с фиксированным порядком) располагаются равномерно. Например, зазор между числами в интервале 2^–1  x < 1 равен 2^–t. Числа в соседнем справа интервале 1  x < 2 имеют зазор в два раза больший, т. е. 2^1 – t , а числа в соседнем слева интервале 2^–2  x < 2^–1 – в два раза меньший, т. е. 2^–1 – t. В общем случае числа в интервале 2^p – 1 x < 2^p имеют зазор 2^p – t. Таким образом, с ростом порядка p растет и зазор между соседними числами системы F(t, L, U) на вещественной оси. Отсюда следует, что абсолютная ошибка представления числа x числом fl(x) системы чисел F(t, L, U) есть x = |fl(x) – x| и удовлетворяет неравенству x  2^p – t при округлении отбрасыванием всех цифр (a_t + 1, a_t + 2, …) после a_t или неравенству x  2^{p – t – 1} при округлении к ближайшему числу fl(x). Для характеристики зазора между числами в системе F(t, L, U) обычно используют параметр  = 2^1 – t (величину зазора на интервале 1  x < 2). Относительная ошибка представления числа x есть (x) = x / |x|. Значение (x) не зависит от интервала и удовлетворяет или неравенству (x)   или неравенству (x)  2^–1 соответственно при округлении отбрасыванием или при округлении “к ближайшему”.

В компьютерах существуют 3 стандартные формы представления чисел с плавающей точкой, а именно:

1. формат одинарной точности (вПаскале – тип Single);

2. формат двойной точности (в Паскале – тип Double);

3. формат расширенной точности (в Паскале – тип Extended).

Стандартный тип Real - предназначен для работы с числами в режиме эмуляции арифметических операций

Типы Single, Double, Real, Extended отличаются параметрами t, L, U и нек-ми особенностями реализации. Характеристики этих типов приведены в табл.

Назван типа	Длина,байт	Число явных бит мантиссы	Кол-во знач цифр	Диапазон десятичного порядка
Single	4	23	7,  8	–45…+38
Real	6	39	11,  12	–39…+38
Double	8	52	15,  16	–324…+308
Extended	10	64	19,  20	–4951..+4932

Отметим также, что тип Extended предназначен в основном для представления промежуточных результатов, получающихся при вычислении ф-ций с числами типа Double, чтобы упростить получение гарантированных по точности окончательных результатов. Все основные вычисления производятся в формате Extended, а затем результаты округляются до используемого в программе типа Single, Real или Double.

Обычно в качестве характеристики точности представления вещ чисел в ЭВМ используют так называемое машинное эпсилон, определяемое как eps = min { : fl( + 1) > 1 }.

Эта величина учитывает особенности реализации системы F(t, L, U) в конкретном компьютере.