Introdução à Programação - Poli - 11 - recorrência e séries (C)

Prévia do material em texto

Introdução à Computação 
para Engenharia 
MAC2166
Prof. Dr. Paulo Miranda
IME-USP
Fórmula de Recorrência e 
Séries (Somas Infinitas)
   
Fórmula de Recorrência
● Uma fórmula de recorrência é uma relação entre os 
termos sucessivos de uma sequência numérica.
● Dessa forma, usando uma fórmula de recorrência, é 
possível obter o próximo termo da sequência usando o 
valor de termos anteriores.
fat(n) = 
1 se n=0
n x fat(n-1) se n>0
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2) se n>1
   
Exemplo
● Cálculo da série de Fibonacci.
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2) se n>1
● A sequência de Fibonacci consiste em uma série de 
números, tais que, definindo seus dois primeiros 
números como sendo 0 e 1, os números seguintes são 
obtidos através da soma dos seus dois antecessores.
● Exemplos da sequência são:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
   
Exemplo
● A ocorrência da sucessão de Fibonacci na natureza é 
tão frequente que é difícil acreditar que seja acidental 
(ex: flores, conchas, mão humana).
   
Exemplo
● Cálculo da série de Fibonacci.
int main(){
 int f0,f1,f2,k,n;
 scanf(“%d”,&n);
 f0 = 0;
 f1 = 1;
 for(k = 1; k <= n; k++){
 f2 = f0+f1;
 f0 = f1;
 f1 = f2;
 }
 printf(“fibo(%d) = %d\n”,n,f0);
 return 0;
}
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2) se n>1
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5