3. Цель, требования и рекомендации к выполнению задания

Цель выполнения задания:

1. приобретение навыков программирования циклических процессов (включая формирование условий их корректного окончания) с использованием конструкции цикла while-do и с предварительным преобразованием вычислений к рекуррентной форме;

2. ознакомление с особенностями вычислений с целыми числами.

Требования и рекомендации к выполнению задания:

1. при выполнении задания использовать цикл while-do и переменные только целых типов (и, возможно, типа Boolean), а также стандартные операции с ними;

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

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

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

5. использовать различные версии программы, отличающиеся типами данных, представляющих целые числа в Турбо Паскале;

6. реализовать вычислительную часть программы с учетом особенностей представления и диапазонов применяемых целых типов;

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

8. определить (экспериментально) диапазон значений входных данных (возможно, при некоторых характерных сочетаниях между ними), для которых программа выдает корректные выходные данные; объяснить полученные результаты.

4. Примеры выполнения задания

Пример 2.1. Последовательность чисел Фибоначчи определяется рекуррентным соотношением F(i + 1)=F(i)+F(i – 1) с начальными условиями F(0)=0 и F(1)=1. Требуется вычислить число Фибоначчи F(n) c заданным номером n ³ 1.

Поскольку при вычислении элемента последовательности Фибоначчи F(i + 1) используется пара предыдущих элементов F(i) и F(i – 1), то в программе будем использовать пару переменных a и b, таких, что после i-й итерации a_i = F(i) и b_i = F(i – 1). Тогда переход от пары <a_i – 1, b_i – 1> к паре <a_i, b_i> осуществляется с помощью рекуррентных соотношений (для i > 1)

a

(2. 3)

_i = a_i – 1 + b_i – 1,

b_i = a_i – 1,

при начальной установке a₁ = 1; b₁ = 0.

Действительно, если a_i – 1 = F(i – 1) и b_i – 1 = F(i – 2), то по (2.3) будут вычислены a_i = F(i – 1) + F(i – 2) = F(i) и b_i = F(i – 1). Начальная установка обеспечивает a₁ = F(1) и b₁ = F(0).

Эти рекуррентные вычисления с переменными var a, b, c, i, n: Integer реализуются следующим фрагментом программы (при n ³ 1)

a:=1; b:=0; i:=1;

{У1: (a=F(1)) & (b=F(0)) }

while (i<n) do

begin {У2: (a=F(i)) & (b=F(i-1)) & (1£i<n)}

i:=i+1;

c:=a;

a:=a+b;

b:=c

{У3: (a=F(i)) & (b=F(i-1)) & (1<i£n)}

end;

{У4: (i=n) & (a=F(n)) & (b=F(n-1))}

В приведенном фрагменте программы даны комментарии в виде утверждений, связывающих переменные программы либо между собой (например, 1< i £n), либо с математическими переменными из рекуррентного соотношения (например, (a = F(i)) & (b = F(i – 1)) ). Утверждение У1 является предутверждением для цикла while-do и характеризует инициализацию цикла. Утверждения У2 и У3 являются инвариантами точки входа тела цикла и точки выхода соответственно. Утверждение У4 является постутверждением для цикла и описывает результат работы программы.

Пример 2. 2. Рассмотрим модификацию задачи примера 2.1. Известно, что значения стандартного целого типа Integer в языке Паскаль имеют верхнюю границу MaxInt (предопределенная константа). Требуется вычислить число Фибоначчи F(n), максимальное среди целых чисел типа Integer, и его номер n.

Учитывая, что последовательность Фибоначчи возрастает, требование задачи можно записать в одном из трех видов:

1. n = max{nÎN | F(n) ≤ MaxInt};

2. n = min{nÎN | F(n + 1) > MaxInt};

3. найти такое n, что (F(n) ≤ MaxInt) & (F(n + 1) > MaxInt).

Третья формулировка наиболее конструктивна при реализации рекуррентных вычислений.

Для решения задачи достаточно изменить условие продолжения цикла в программе из примера 2. 1. Действительно, на i-м шаге должно быть вычислено следующее число Фибоначчи: F(i) = a + b = F(i – 1) + F(i – 2). Очередную итерацию следует проводить, если новое значение F(i) £ MaxInt, т.е. если a + b £ MaxInt. Однако непосредственно проверить неравенство a + b £ MaxInt нельзя, так как сумма a + b может превысить MaxInt (это вызовет ошибку выхода за границы диапазона). Поэтому заменим неравенство a + b £ MaxInt на равносильное ему a £ MaxInt – b. В итоге получим

a:=1; b:=0; i:=1;

{a=F(1) & b=F(0)}

while ( ) do

begin {(a=F(i)) & (b=F(i-1)) & (a+b£MaxInt)}

i:=i+1;

c:=a;

a:=a+b;

b:=c

{(a=F(i)) & (b=F(i-1)) & (a£MaxInt)}

end;

{(a=F(i)) & (b=F(i-1)) & (a£MaxInt) & (a+b>MaxInt) & (n=i)}

Пример 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). Далее приведем полную программу на языке Паскаль и пример ее выполнения. Отметим, что в тело цикла добавлены операторы, обеспечивающие поочередный вывод (в 3 колонки) вычисляемых чисел Фибоначчи и их номеров.

{ Вычисление чисел Фибоначчи с контролем диапазона типа 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.

После ввода n = 9 на экране появятся результаты, приведенные в табл. 2. 3.

Таблица 2.3

F ( 1 ) = 1 F ( 2 ) = 2 F ( 3 ) = 2

F ( 4 ) = 3 F ( 5 ) = 5 F ( 6 ) = 8

F ( 7 ) = 13 F ( 8 ) = 21 F ( 9 ) = 34

9-е число Фибоначчи =34

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

Пример 2. 4. Для заданного целого n ≥ 0 вычислить S(n) =S_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).

Заметим, что сумму 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.

Таблица 2.4

i= 0 a(0)= 1 S= 1

i= 1 a(1)= 10 S= 11

i= 2 a(2)= 90 S= 101

i= 3 a(3)= 720 S= 821

При i=4 последнее слагаемое равно 5040 Сумма равна 5861

При i=5 сумма вне диапазона типа Integer

При вводе n = 5 и m = 10 на экране появятся результаты, приведенные в табл. 2. 4.