Программирование 1

k  = n;
while (k > 0) {
p  = p *k ;
k  = k  1 ;
}

Что здесь вычисляется?
Как

условия продолжения цикла на k>1
Анализ таблицы :  на последнем

{
// Утв2: ?
p = p*k;
k = k  1;
// Утв3: ?  
}
//p=n !
Предположим, что

//Утв1: (p *k ! = n !) & (0  k  n)

//Утв2: (p *k ! = n!) & (0 < k  n)

//Утв3: (p*k ! = n !) & (0  k < n)

n! = p*k ! = p*k*(k-1)! = p*k*(k-1)!  p*k ! = n!

n > 0
Вычислить:

Пусть

Тогда Si = S i 1 + i

xi, Si = Si-1 + yi

= S(n))
// n  0
x = 0; y = 1; s = 0;
// (x = 0) &

while (x < n) 
{

x = x + 1 ;
y = y *x;
s = s + y;

// (0  x < n) & (y = fact (x)) & (s = S(x))

// (0 < x  n) & (y = fact (x)) & (s = S(x))

i =0...3 а (i ) =
= i=0...3 A(i | 5) = а(0)+

22.09.2011

Схема итерации

Пример 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).

S (0) = A(0| m) = 1; 
a (i ) = A(i | m) =

В программе:
слагаемое a (i )  переменная a,
номер слагаемого i  переменная i,
формируемая сумма S (i )  переменная s.

* (m – i + 1)
i = 0; a

i =0,…,n  1; S(0) =1; 
a (i ) =

= a(i) * (m – i)
i = 0; a

(демонстрировать на лекции)

войдет в след. лекцию)

+ 1) = F(i) + F(i – 1) с начальными

Вставка про числа Фибоначчи

Рекурре́нтная после́довательность
(от лат. recurrens,  — возвращающийся),
то же, что возвратная последовательность

Fn + 2 = Fn + 1 + Fn  при n = 0, 1, 2, …
и начальными элементами F0 = 0 и F1 = 1.
Вот

Фибоначчи – Леонардо Пизанский (Leonardo Pisano) или
Леонардо Фибоначчи (Filius Bonaccii – сын Боначчо), 1202 г.

и
Число   1.61803… называют «золотым сечением»
Конец вставки

числами.

Замечание о форме рекуррентного соотношения:
F(i + 1) = F(i) +

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

то в программе будем использовать
пару переменных a и b,

Вычисление числа Фибоначчи F(n) c заданным номером n  1

b i – 1 = F(i – 2),
то по (**) будут

(a=F(1)) & (b=F(0)) }
while (i < n) do
begin {У2:

целого типа Integer в языке Паскаль имеют верхнюю границу MaxInt

n = max {nN | F(n) ≤ MaxInt};
n = min {nN | F(n + 1) > MaxInt};
такое n, что (F(n) ≤ MaxInt) & (F(n + 1) > MaxInt).

F(i) = a + b = F(i – 1) + F(i – 2).
Непосредственно проверить неравенство a + b  MaxInt нельзя !

(a + b  MaxInt)  (a  MaxInt – b)

Условие продолжения

0; i := 1;
{a=F(1) & b=F(0)}
while (a  MaxInt – b ) do
begin {(a=F(i))

F(n). Если число F(n) выходит за диапазон стандартных целых чисел

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

Условие завершения цикла
Not B  (i  n) or (a > (MaxInt – b))

 (a & b) = ( a)  ( b)

:= 1; b := 0; i :=1;
{a=F(1) & b=F(0)}
while

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ