Funcion recursiva de fibonacci

¿Has encontrado un error? ¿Tienes la solución? Deja tu correción ;-)

Antes de comentar: Gran parte de los ejercicios propuestos no tienen librerías debido a que Wordpress las eliminó al verlas como etiquetas HTML. Si sabes/tienes/conoces las librerías que hacen falta, déjalo en los comentarios. Y lo mas importante: Todos los ejemplos fueron realizados por estudiante con únicamente conocimiento básico del lenguaje, no de programación.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
 
long fibonacci( long n ); /* prototipo de la función */
 
/* la función main comienza la ejecución del programa */int main()
{
   long resultado; /* valor fibonacci */
   long numero;    /* numero a introducir por el usuario */
    /* obtiene un entero del usuario */
   printf( "Introduzca un entero: " );
   scanf( "%ld", &numero);
 
   /* calcula el valor fibonacci del número introducido por el usuario */   resultado = fibonacci( numero );
 
   /* despliega el resultado */
   printf( "Fibonacci( %ld ) = %ldn", numero, resultado );
      return 0; /* indica terminación exitosa */
 
} /* fin de main */
 
/* definición de la función recursiva fibonacci */long fibonacci( long n )
{
   /* caso base */
   if ( n == 0 || n == 1 ) {
      return n;   } /* fin de if */
   else { /* paso recursivo */ 
      return fibonacci( n - 1 ) + fibonacci( n - 2 );
   } /* fin de else */
   } /* fin de la función fibonacci */

11 comentarios en "Funcion recursiva de fibonacci"

el

[c]/*suma de dos matrices*/
#include
#include
#define R 100
#define C 100

int a,b,i,j,r,c;
float A[R][C],B[R][C],J[R][C];

main()
{
printf("Renglones: ");scanf("%d",&r);
printf("Columnas: ");scanf("%d",&c);
printf("nMATRIZ An");
for(a=0;a<r;a++)
for(b=0;b<c;b++)
{
printf("nA[%d][%d]= ",a,b);
scanf("%f",&A[a][b]);
}
printf("nMATRIZ Bn");
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
printf("nA[%d][%d]= ",i,j);
scanf("%f",&B[i][j]);
J[i][j]=A[i][j]+B[i][j];
}
printf("nMATRIZ Jn");
for(i=0;i<r;i++)
{
printf("n");
for(j=0;j<c;j++)
{
printf("t %.2f",J[i][j]);
}
}
getch();
}[/c]

jur

La función presentada es claramente ineficiente, ya que calcula 2 series de fibonacci de orden n-1 por cada llamada de orden n.

Combierte un problema lineal en uno exponencial!!

jur

Adjunto funcion fibrec en Python (lo siento, no sé C) que calcula fibonnacci recursivamente con coste lineal...

def fibrec2 (n): #auxiliar que calcula fib recursivamente pero desde 0 1
if n==1: # Solución trivial
return [0,1]
else: # Solución recursiva...
l= fibrec2 (n-1) # del problema de tamaño n-1
l.append(l[-2]+l[-1]) # y añadimos el elemento n
return l

def fibrec (n):
if n>1:
return fibrec2 (n)[1:] #Nos ayudamos de fibrec2 y eleminamos el 0 inicial
else:
print "ERROR: No se puede calcular fibonacci de", n


Se usa la auxiliar fibrec2 para simplificar la solución (que realmente está devolviendo fib0(n+1), es decir la solución de la serie de fibonacci comenzando con 0 1 para n+1). Con esta ayuda calcuar fibonacci de n comenzando por 1 1 es sólo cuestión de eliminar de la lista el primer 0...
Ejemplos:
>>>fibrec(5)
[1, 1, 2, 3, 5]
>>>fibrec(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Se puede observar que la solución tiene coste lineal ya que realiza una única llamada recursiva a un problema de tamaño n-1...

Lo siento si el código no es el más limpio o más estiloso en Python, pero es mi primer ejemplo de uso de python. Empecé con python esta mañana después de más de 10 años sin programar ;)

Un saludo,

Jur.

PACO

TUS PROGRAMAS SON MUY BUENOS, DE HECHO SOLO QUISIERA AYUDA, ME PIDEN QUE PERMUTE 3 LETRAS PERO NO SE COMO PROGRAMAR ESO. EL EJEMPLO ES ASI
ABC
ACB
BAC
BCA
CAB
CBA
SI ME PUDIERAS DECIR COMO REALIZARLO TE ESTARIA MUY AGRADECIDO
GRACIAS Y SALU2.
SIGUE ASI, ERES MUY BUENO.

Punto importante: Si vas a sugerir un segmento de código en algún lenguaje debes hacerlo así:

  • Si es lenguaje C <code lang="c">Código en C</code>
  • Si es lenguaje Pascal <code lang="pascal">Aquí dentro el código de Pascal</code>.

De esta manera el código coloreas el código.

Deja un comentario

Suscribirse a los comentarios.