- •Билет №8 Вычисления с вещественными числами и машинное эпсилон №8
- •Машинное эпсилон может быть вычислено с помощью следующей программы:
- •Билет №9 Общая схема итерации и №9 рекуррентные вычисления
- •Вычисления с целыми числами
- •Билет№10 Схема интерации. Вычисление частичной суммы (вещ числа) №10
- •Общая формулировка задания
- •Пример выполнения задания
- •Вопрос №12 . Основные правила аналитической верификации программ №12
- •Вопрос №14 Ограничивающая ф-ция оператора цикла.Примеры №14
- •Билет№15. Теорема о цикле, его инварианте и ограничивающей функции №15
- •Билет №17 Теорема о цикле repeat- until ,его инварианте и ограничивающей его ф-ции. Аннотирование цикла и понимание аннотации №17
- •Вопрос№18 Алгоритм анализа двоичной записи натурального числа в двоичной сист счисления №18
- •Последовательности и файлы
- •Индуктивные функции
- •Стационарные значения индуктивных функций
- •Индуктивные расширения функций
- •Примеры задач с индуктивными функциями
- •Кванторы и запись утверждений о массивах
- •Правила вывода для цикла с параметром
- •Примеры программ работы с массивами
- •Решение последовательными обменами
- •Задача перестановки сегментов разной длины (второе решение)
- •Задача перестановки сегментов разной длины (третье решение)
- •Билет№35 Задача о равнинах (с испол массива) №35
- •Линейный поиск
- •Оптимизация программы бинарного поиска
- •Билет№44 Массивы в качестве параметров:открытые массивы №44 Сведения о массивах в языке Паскаль
- •Билет№45 Двумерные (многомерные массивы). Индексация. Исполбзование процедур. Задача: о МиниМаксе(матрица как массив строк) №45 обработка двухмерных массивов
Пример 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 { ввод числа mn }
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 = ± (a12–1 + a22–2 + …+ at2–t) 2p , (3.3)
где ai{0, 1} при i = 1, 2, …, t. Обычно это представление используется в нормализованном виде так, что a1 = 1
Число = ±(a12–1 + a22–2 + …+ at2–t) называют мантиссой числа x. Число бит t в каждой реализации фиксировано и называется разрядностью мантиссы. Целое число p в (3.3) называют двоичным порядком. Оно, в свою очередь, также представляется в двоичном виде, и его значения находятся в некотором диапазоне L p U. Система чисел в представлении (3.3) задается параметрами t, L, U и будет обозначаться далее F(t, L, U). Так как мантисса вещ. числа представляет его в усеченном виде (только t двоичных разрядов), а двоичный порядок ограничен диапазоном L...U, то представление с плавающей точкой Si = j = 0...i uj.(последовательность частитичных сумм) имеет ряд важных особенностей:
Имеется конечное мн-во полож. чисел, представимых в системе F(t, L, U), а именно 2t – 1(U – L + 1). Если учесть отрицательные числа и нуль, то всего имеется 22t – 1(U – L + 1) + 1 чисел.
Среди чисел системы F(t, L, U) имеется макс. по величине число = (1 – 2–t) 2U . Попытка вычислить в системе F(t, L, U) число x > (или x < –) приводит к ошибке переполнения.
В окрестности нуля имеется зазор, где отсутствуют числа системы F(t, L, U). Самое маленькое полож. число = 2L – 1. Попытка вычислить в системе F(t, L, U) число x 0, такое, что |x| < , приводит к ошибке, называемой антипереполнением или исчезновением порядка.
Числа системы F(t, L, U) на вещественной оси расположены неравномерно. При этом отдельные группы чисел (с фиксированным порядком) располагаются равномерно. Например, зазор между числами в интервале 2–1 x < 1 равен 2–t. Числа в соседнем справа интервале 1 x < 2 имеют зазор в два раза больший, т. е. 21 – t , а числа в соседнем слева интервале 2–2 x < 2–1 – в два раза меньший, т. е. 2–1 – t. В общем случае числа в интервале 2p – 1 x < 2p имеют зазор 2p – t. Таким образом, с ростом порядка p растет и зазор между соседними числами системы F(t, L, U) на вещественной оси. Отсюда следует, что абсолютная ошибка представления числа x числом fl(x) системы чисел F(t, L, U) есть x = |fl(x) – x| и удовлетворяет неравенству x 2p – t при округлении отбрасыванием всех цифр (at + 1, at + 2, …) после at или неравенству x 2p – t – 1 при округлении к ближайшему числу fl(x). Для характеристики зазора между числами в системе F(t, L, U) обычно используют параметр = 21 – t (величину зазора на интервале 1 x < 2). Относительная ошибка представления числа x есть (x) = x / |x|. Значение (x) не зависит от интервала и удовлетворяет или неравенству (x) или неравенству (x) 2–1 соответственно при округлении отбрасыванием или при округлении “к ближайшему”.
В компьютерах существуют 3 стандартные формы представления чисел с плавающей точкой, а именно:
формат одинарной точности (вПаскале – тип Single);
формат двойной точности (в Паскале – тип Double);
формат расширенной точности (в Паскале – тип 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) в конкретном компьютере.