/* 
 * Modulo: sucessao.c
 * 
 * Descricao:
 *    Este modulo contem funcoes para calculo de sucessoes famosas. 
 * 
 * Notas: 
 * 
 * Autores: 
 *    Manuel Menezes de Sequeira, ISCTE. 
 *
 * Historia:
 *    Autor:              Data:                  Notas:
 *    MMS                 1996/5/9               primeira versao
 *
 * Copyright (c) ISCTE, 1996.
 */

#include "sucessao.h"

/* 
 * Funcao: SUCfibonacciRec()
 * 
 * Accao:
 *    Calcula o valor do elemento n da sucessao de Fibonacci duma forma
 * recursiva (F(0)=F(1)=1, F(n)=F(n-1)+F(n-2) para n > 1).
 * 
 * Parametros: 
 *    n (E) - numero do elemento da sucessao a calcular.
 * 
 * Notas:
 *    Se a macro CONTABILIZA estiver definida, a funcao tem um contador
 * interno de chamadas que pode ser anulado chamando a funcao com argumento
 * -1, e cujo valor e' devolvido quando a funcao e' chamada com argumento
 * -2.
 *
 * Devolve:
 *    O valor do elemento n da sucessao.
 */
unsigned long SUCfibonacciRec(int n)

{
#ifdef CONTABILIZA
    static unsigned long chamadas = 0;
    
    if(n == -1)
	return chamadas = 0;
    if(n == -2)
	return chamadas;
    chamadas++;
#endif
    if(n < 2)
	return 1UL;
    return SUCfibonacciRec(n-1) + SUCfibonacciRec(n-2);
}


/* 
 * Funcao: SUCfibonacci()
 * 
 * Accao:
 *    Versao iterativa da funcao anterior.
 * 
 * Parametros: 
 *    n (E) - numero do elemento da sucessao a calcular.
 * 
 * Notas:
 *    Esta versao nao contabiliza chamadas.
 *
 * Devolve:
 *    O valor do elemento n da sucessao.
 */
unsigned long SUCfibonacci(int n)

{
    int i;
    unsigned long fn1, fn2, fn;
    
    fn = fn1 = fn2 = 1UL;
    for(i = 2; i <= n; i++)
    {	
	fn  = fn1 + fn2;
	fn2 = fn1;
	fn1 = fn;
    }
    return fn;
}


/* 
 * Funcao: SUCnfibonacci()
 * 
 * Accao:
 *    Funcao que calcula o numero de chamadas N(n) da funcao F(n) 
 * (SUCfibonnaciRec()), versao recursiva. N(n) = N(n-1) + N(n-2) + 1, para
 * n > 1, e N(0) = N(1) = 1.
 * 
 * Parametros: 
 *    n (E) - numero do elemento da sucessao para o qual calcular o numero
 *            de chamadas.
 * 
 * Notas:
 *    Mas, como o numero de chamadas a F() (versao recursiva) para calculo
 * de F(n) e' N(n)=2F(n)-1, esta funcao podia ser mais simples! Ver em 
 * comentario abaixo. A deducao faz-se com facilidade:
 * 1. F(n) = F(n-1) + F(n-2)                    n > 1
 * 2. 2F(n) = 2F(n-1) + 2F(n-2)                 n > 1
 * 3. 2F(n) - 1 = 2F(n-1) -1 + 2F(n-2) -1 + 1   n > 1
 * 4. X(n) = 2F(n) - 1
 * de 3. e 4.:
 * 5  X(n) = X(n-1) + X(n-2) + 1                n > 1
 * 6. X(0) = X(1) = 2x1 - 1 = 1
 * 7. mas 5. e 6. sao a definicao de N(n)! Logo N(n) = X(n) = 2F(n) - 1!
 *
 * Devolve:
 *    O numero de chamadas necessaris para obter valor do elemento n 
 * da sucessao.
 */
unsigned long SUCnfibonacci(int n)

{
    int i;
    unsigned long fn1, fn2, fn;
    
    fn = fn1 = fn2 = 1UL;
    for(i = 2; i <= n; i++)
    {	
	fn  = 1 + fn1 + fn2;
	fn2 = fn1;
	fn1 = fn;
    }
    return fn;
}
/* Ou...
{
    int i;
    unsigned long fn1, fn2, fn;
    
    fn = fn1 = fn2 = 1UL;
    for(i = 2; i <= n; i++)
    {	
	fn  = fn1 + fn2;
	fn2 = fn1;
	fn1 = fn;
    }
    return 2*fn-1;
}
*/