Introducción

1

¿Qué es un grafo?

2

¿Qué es un árbol?

3

¿Qué es recursión?

4

Aplicaciones reales de grafos y árboles

5

Formas de representar un grafo

DFS

6

Análisis de DFS: algoritmo de búsqueda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un Árbol

10

Sum Root to Leaf Numbers: análisis del problema

11

Solución de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: análisis del problema

15

Solución de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

Análisis de BFS: algoritmo de búsqueda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

23

Solución de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: análisis del problema

27

Solución de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: análisis del problema

31

Solución de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: análisis del problema

38

Solución de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: análisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: análisis del problema

45

Solución de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Próximos pasos

51

¿Qué otros algoritmos y tipos de grafos puedes aprender?

52

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

¿Qué es recursión?

3/52
Recursos

Aportes 15

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Podemos usar memoizacion para optimizarlo, antes de hacer la llamada a la función podemos revisar en una especie de cache si el valor ya lo hemos consultado previamente, en caso que no llamamos a la función.

Para mejorarlo aplicaría Programación Dinámica con la técnica de Memorización, para evitar repetir cálculos ya realizados, transformar la complejidad de un algoritmo de exponencial a lineal o polinomial, dependiendo del problema e intercambiar tiempo por espacio.
Y así poder obtener el resultado de fibonacci de números grandes en menor tiempo:

import sys

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1

    try:
        return memo[n]
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado

        return resultado

print(fibonacci_dinamico(250))        

https://platzi.com/clases/1835-programacion-estocastica/26429-introduccion-a-la-programacion-dinamica/

Se me ocurre crear un “cache”, de numeros ya calculados.

cache = {}
def fib(n):
    if n <= 1:
        return n
    if cache.get(n) != None:
        return cache[n]
    result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

Asi queda lo mas resumido posible, detectando también que el numero sea mayor a cero

def fibo(n):
    return (print('Error') if n<0 else( n if n<2 else fibo(n-1) + fibo (n-2)))

Tomando los datos solo para numeros positivos, e intentando reducir el código al máximo en python:

def fibo(n):
    return (n if n<2 else fibo(n-1) + fibo (n-2))

Para evitar cálculos pre-hechos, en ese código en particular se me ocurre mandar un arreglo con los valores fibonacci recién calculados y validar si ya está calculado algo como:

def fib(n, fib_values):
     if n == 0:
         return 0
     if n == 1:
         return 1
     if fib_values[n] >= 0:
         return fib_values[n]
     fib_values[n] = fib(n-1, fib_values) + fib(n-2, fib_values)
     return fib_values[n]

n = 100
fib_values = [-1] * (n+1)

print(fib(n, fib_values))

Esto mejora mucho el tiempo en valores mayores como 40 pasando de 51seg a 0.04seg:

oscar@pavilion:~/Dev/algo$ time python3 fibonacci.py
102334155

real	0m51.446s
user	0m51.286s
sys	0m0.032s
oscar@pavilion:~/Dev/algo$ time python3 fibonacci_optimizado.py 
102334155

real	0m0.040s
user	0m0.028s
sys	0m0.012s

O un poco más elegante para mi gusto, resolverlo con programación dinámica:

def fib(n):
    fib = [-1] * (n+1)
    fib[0] = 0
    fib[1] = 1

    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]

    return fib[n]

Recursividad: Proceso que se define en términos de sí mismo. Lo importante al definir una función de recursividad es saber cuando va a terminar de ejecutar la función (el caso base), caso contrario podríamos caer en un ciclo infinito.
En tiempo de ejecución en memoria funciona como un Pila (LIFO), en el cuál cada frame tiene sus variables independientes de cada llamada de la función. Ej.: con factorial.

Sucesión de Fibonacci: Sucesión infinita de números naturales, la cual empieza a partir del 0 y el 1, continuando con la suma de los 2 anteriores: 0, 1, 1 (1+0), 2(1+1), 3(2+1), 5(3+2)+, 8(5+3), 13(8+5) … Descubierta por el matemático italiano Leonardo de Pisa, más conocido como Fibonacci en el siglo trece.

Al código le añadiría un mensaje de retorno en caso que se pida el Fibonacci de un número negativo o retornaría el mismo número:

function fib(n) {
	if (n <= 1) 
		return n;
	return (fib(n-1) + fib(n-2));
}

def fibo(n):
if n == 1 or n==2:
return n
else:
num = fibo(n-1) + fibo(n-2)
return num
print(fibo(7))

La recursión es un concepto fundamental en informática y matemáticas que se refiere a la técnica de resolver problemas mediante la división en casos más pequeños y la auto-referencia.
Esta es mi solución en java, utilicé un HashMap para la caché y en lugar de crear los casos para cuando n = 1 || 0 inserto esas llaves para que las encuentre en la validación de la caché. ```java public class Fibonacci { static Map<Integer, Long> cache = new HashMap<>(); static { cache.put(0, 0L); cache.put(1, 1L); } public static void main(String[] args) { final Scanner sc = new Scanner(System.in); System.out.println("ingrese el valor a calcular"); final int fibonacciSeries = sc.nextInt(); System.out.println("resultado final: " + calcularFibonacci(fibonacciSeries)); } private static long calcularFibonacci(int n) { System.out.println(n); if(cache.get(n) != null){ System.out.println("valor en cache: [" + n + "] : [" + cache.get(n) + "]"); return cache.get(n); } long result = calcularFibonacci(n-1) + calcularFibonacci(n-2); System.out.println("añadiendo valor: [" + result + "] a la cache en la posicion: [" + n + "]"); cache.put(n, result); return result; } } ```public class Fibonacci { static Map\<Integer, Long> *cache* = new HashMap<>(); static { *cache*.put(0, 0L); *cache*.put(1, 1L); } public static void main(String\[] args) { final Scanner sc = new Scanner(System.*in*); System.*out*.println("ingrese el valor a calcular"); final int fibonacciSeries = sc.nextInt(); System.*out*.println("resultado final: " + *calcularFibonacci*(fibonacciSeries)); } private static long calcularFibonacci(int n) { System.*out*.println(n); if(*cache*.get(n) != null){ System.*out*.println("valor en cache: \[" + n + "] : \[" + *cache*.get(n) + "]"); return *cache*.get(n); } long result = *calcularFibonacci*(n-1) + *calcularFibonacci*(n-2); System.*out*.println("añadiendo valor: \[" + result + "] a la cache en la posicion: \[" + n + "]"); *cache*.put(n, result); return result; } }
<public class sucesionDeFibonacci{

    public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
        System.out.println("Numero de fibonacci a conocer: ");
        int numUsuario = leer.nextInt()-1;
        int [] fibonacci  = new int [numUsuario+1];
        int i = 0;
        sucesion(numUsuario, fibonacci, i);
    }
    
    public static void sucesion(int fibonacci, int [] num, int i){
        if (i <= 1) {
            num[i] = 1;
            System.out.println("Fibonacci " + (i + 1) + ": " + num[i]);
        } else {
            num[i] = num[i - 1] + num[i - 2];
            System.out.println("Fibonacci " + (i + 1) + ": " + num[i]);
        }
        if (i < fibonacci) {
            i++;
            sucesion(fibonacci, num, i);
        }
    }
     }> 
Buena analogía. De la caja dentro de la caja

Jejeje si recuerso la pelicula del Origen o Inceptión.
Y su parodia de Rick y Morty.

Me gusto la forma sencilla de explicar recursión
Es una forma sencilla de repetir una misma acción varias veces.

function fib(n<2){
    if (n<=1){
        return n
    } 
    return fib(n-1) + fib(n-2);
}
console.log(fib(6))
const fib = n =>	(n< 2) ? n :	fib(n-1) + fib(n-2);
console.log(fib(6));