Diferencias

Muestra las diferencias entre dos versiones de la página.

--- informatica:programacion:python:cursos:introduccion_programacion_python:funciones [2023/04/18 23:35] – [Funciones que no retornan valor (procedimientos)] tempwin
+++ informatica:programacion:python:cursos:introduccion_programacion_python:funciones [2023/04/19 10:15] (actual) – [Problema de las ocho reinas] tempwin
@@ Línea 476: / Línea 476: @@
 factorial(0) # 1
+</code>
+===== Ejemplos prácticos =====
+==== Torres de Hanoi ====
+Ejemplo clásico de recursividad.
+El juego consiste en pasar todos los discos desde el poste ocupado (es decir, el que posee la torre) a uno de los otros postes vacíos. Para realizar este objetivo, es necesario seguir tres simples reglas:
+  * Solo se puede mover un disco cada vez y para mover otro los demás tienen que estar en postes.
+  * Un disco de mayor tamaño no puede estar sobre uno más pequeño que él mismo.
+  * Solo se puede desplazar el disco que se encuentre arriba en cada poste.
+<WRAP center round info 60%>
+La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es ''2^n - 1''
+</WRAP>
+<code python>
+def hanoi(n, origen='A', destino='C', auxiliar='B'):
+    if n > 1:
+        hanoi(n - 1, origen, auxiliar, destino)
+    print(f"Mover disco de {origen} a {destino}")
+    if n > 1:
+        hanoi(n - 1, auxiliar, destino, origen)
+</code>
+==== Problema de las ocho reinas ====
+El problema de las ocho reinas es un pasatiempo que consiste en poner ocho reinas en el tablero de ajedrez sin que se amenacen.
+<WRAP center round info 60%>
+El problema de las 8 reinas tiene 92 soluciones.
+</WRAP>
+https://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas
+<code python>
+def mostrar_tablero(reinas):
+    # Dibujamos un tablero de ajedrez
+    for columna in reinas:
+        print("+----+----+----+----+----+----+----+----+")
+        print("|    "*columna + "| @ " + "|    "*(7 - columna) + "|")
+        print("|    |    |    |    |    |    |    |    |")
+    print("+----+----+----+----+----+----+----+----+")
+</code>
+<code>
+mostrar_tablero([1, 3, 5, 7, 2, 0, 6, 4])
+</code>
+Vamos ahora con la resolución del problema:
+<code python>
+contador_soluciones = 0
+def reinas(posiciones=[]):
+    global contador_soluciones # Indicamos que queremos acceder a una variable externa a la función
+    # Determinamos el número de fila donde colocar la reina
+    # simplemente contando los elementos ya posicionados
+    fila = len(posiciones)
+    # En esa fila, probamos a colocar una reina en cada una
+    # de las columnas
+    for columna in range(8):
+        # Comprobar si la columna está libre; si no lo está,
+        # saltamos a la siguiente columna
+        if columna in posiciones:
+            continue
+        # Comprobación de diagonales: para todas las filas anteriores,
+        # ver si no hay reina en diagonal
+        choque_diagonal = False
+        for f in range(fila):
+            if posiciones[f] + fila - f == columna or posiciones[f] - fila + f == columna:
+                choque_diagonal = True
+                break
+        # Si hemos encontrado una reina en alguna diagonal,
+        # saltamos ya a la siguiente columna
+        if choque_diagonal:
+            continue
+        # Si hemos llegado hasta aquí es porque no hay reinas en
+        # la vertical ni en las diagonales, así que colocamos una
+        # nueva reina en el tablero
+        posiciones.append(columna)
+        # Y procedemos a rellenar el resto del tablero recursivamente,
+        # salvo que estemos ya en la última fila. En este último caso,
+        # visualizamos el tablero con la solución
+        if len(posiciones) < 8:
+            reinas(posiciones)
+        else:
+            contador_soluciones += 1
+            print(f"Solución {contador_soluciones}:")
+            mostrar_tablero(posiciones))
+        # Después de todo esto, quitamos la reina que acabamos de colocar
+        # para seguir explorando soluciones
+        posiciones.pop()
 </code>