Решение задачи 17.
Заведем два массива: E[0..N+1] и S[0..N+1]. Элементы массивов - байты. В E будем хранить текущую частичную сумму
En=1+1/1!+1/2!+ ... +1/(k-1)!, (*)
вычисленную с точностью N+1 знаков после запятой
(в ячейке E[i] хранится значение i-го разряда после запятой, то есть коэффициент при 10(-i)). В массиве S будет храниться последнее слагаемое частичной суммы, т.е. 1/(k-1)! (опять же в S[i] находится i-я цифра после запятой, все незначащие цифры, разумеется, нули).
Оценим погрешность формулы (*) c учетом равенства e=1+1/1!+1/2!+ ... +1/(k-1)!+...
Погрешность представления числа е будет
Fn = e-en = 1/(n+1)! + 1/(n+2)!+ ...
= 1/(n+1)! * (1 + 1/(n+2) + 1/(n+2)(n+3) + ...)
< 1/(1+n)! * (1 + 1/(n+2) + 1/(n+2)^2 + ...)
Т.к. F450 < 10(-10002), то для вычисления, например, 1000 знаков после запятой необходимо 450 итераций. По точности N и вышеприведенной формуле вычисляем количество итераций С (можно взять грубо С=N).
Будем делить число, представленное массивом S, на очередное число k. Результат 1/k! прибавим к массиву E. Сложение реализуется так:
perenos:=0; { перенос из предыдущего разряда }
for i:=N+1 downto 0 do
begin
E[i]:=E[i]+S[i]+perenos;
perenos:=E[i] div 10; { формируем новый перенос }
E[i]:=E[i] mod 10; { корректируем E[i] }
end;
Вычисление новых слагаемых и суммирование проводится С раз.
Рассмотрим процедуру деления S на k. Делить будем так, как это обычно делается вручную - "столбиком":
m:=0; { m - текущее делимое, m - Longint }
for i:=0 to N+1 do begin
m:=m*10+a[i]; { дописываем к делимому сзади
еще одну цифру }
a[i]:=m div k; { находим очередную цифру частного }
m:=m mod k; { и очередное делимое }
end;
|
