Osnovy_informatiki_-_5_Primery_programm-1

Задачи на обработку рекуррентных последовательностей

u1	A1 , u2 A2 ,...,uk	Ak	где A1 , A2 ,..., A3 задано
un	F (un 1 , un 2 ,...,un k )	для	n k

K=1

var i,N,F:integer;

begin

read(N);

f:=1;

for i:=1 to N do

f:=f*i;

writeln(f);

end.

f0 1

f n	f n 1 n, n 0

Для больших N

var i,N,F:real;	var i,N,F:real;
begin	begin
read(N);	read(N);
f:=1;	f:=1;
i:=N;	i:=1;
while (i>1e-10) do	repeat
begin	i:=i+1;
f:=f*i;	f:=f*i;
i:=i-1;	until (i<1e-10);
end;	writeln(f);
writeln(f);	end.
end.

Пример 2.

Найти элемент с минимальным номером N, делающий истинным логическое условие P(un, un-1)

	x0	A,		где		A 0
	xn	1	(	A		xn 1 ), n 0
		2		xn 1

Логическое условие

xn

xn 1

, 0

1

{вычисление квадратного корня из положительного A}

const eps=1e-8;

var a,xn,xn_1;

begin

read(a);

xn:=a;

repeat

xn_1:=xn;

xn:=0.5*(a/xn_1+xn_1);

until abs(xn-xn_1)<eps;

writeln(xn);

end.

Пример 3. Эффективный алгоритм возведения в целую положительную степень

p mn p0 1

pn	pn 1 m, n 0

var p,m: real;

I,n:integer;

begin

read(m,n);

p:=1; m1:=m; I:=N;

while I<>0 do begin

I:=I-1;

p:=p*m1;

end;

writeln(p);

end.

p * m1i = mn

Инвариант цикла

p	mn
p0	1
pn	pn 1 m,	n	0	(n	нечетное)
pn	( pn / 2 )2 ,	n	0	(n	четное)

var p,m: real; I,n:integer;

begin read(m,n);

p:=1; m1:=m; I:=N; while I<>0 do begin

while not odd(i) do begin I:=I div 2; m1:=m1*m1;

end; I:=I-1;

p:=p*m1;	p * m1i = mn
end;
writeln(p);	Инвариант цикла
end.

Пример 4. k>1

f1	1, f 2	1
f k	f k 1	f k 2 , k 2

a:=1;

b:=1;

write(1,' ',1,' '); for i:=3 to n do begin

c:=a+b; write(c,' ');

a:=b; //сдвиг элементов, подготовка к // вычислению следующего

b:=c; // элемента последовательности end;