IWI131 Programación


Descomposición en Funciones y Ciclos Anidados



Departamento de Informática
Universidad Técnica Federico Santa María

Descomposición en Funciones

Como dice el refrán: Divide y Vencerás... Es posible resolver un problema difícil, dividiéndolo en subproblemas más simples (en la medida de lo posible). La idea es resolver el problema principal, utilizando las soluciones de los subproblemas.

En el mundo de la informática, es muy frecuente que se resuelvan los problemas de esta forma, siendo uno de los paradigmas más importantes en el diseño de algoritmos. Un pequeño esquema podría ser:

Problema:
    Subproblema 1
    Subproblema 2
    ...
    Subproblema N

Subproblema a Función

Recordando los contenidos vistos en clases anteriores, podríamos relacionar cada subproblema a una función. De esta forma el esquema anterior quedaría más o menos así:

# Inicio de mi algoritmo (problema):
def funcion1(...):
    Instrucciones
def funcion2(...):
    Instrucciones
....
Instrucciones
funcion1(...)
Instrucciones
funcion2(...)
...
# Fin de mi algoritmo

En resumen, buscamos descomponer nuestro algoritmo en funciones, integrar estas funciones y finalmente obtener nuestra solución.

Ahora el problema está en la capacidad de encontrar los subproblemas... Pero generalmente son bastante simples de identificar :)

Variables Globales y Locales

Si bien hay una definición mucho más completa de los tipos de variables Globales y Locales, para nosotros bastará diferenciarlas de la siguiente manera:

  • Variable local: es una variable que sólo se usa dentro del código de una función.
  • Variable global: es una variable que se puede utilizar en cualquier parte del programa, inclusive al interior de una función.

A continuación un pequeño ejemplo...

Ejemplo

La fuerza de atracción gravitacional entre dos planetas de masas $m_1$ y $m_2$ separados por una distancia de $r$ kilómetros está dada por la fórmula:

$$ F = \frac{G\,m_1\,m_2}{r^2}, $$

donde $G = 6,67428\times 10^{−11}$ [m$^3$ kg$^{−1}$ s$^{−2}$] es la constante de gravitación universal.

Escriba un programa que pregunte las masas de los planetas y su distancia, y entregue la fuerza de atracción entre ellos.

Opción 1, utilizando $G$ como variable global.

In [1]:
G = 6.67428e-11 # Variable global. Puede ser utilizada en cualquier parte del código

def cgu(masa1, masa2, radio):
    # La variable fuerza se comporta como variable local, 
    # solo se conoce dentro de la función cgu
    fuerza = G * masa1 * masa2 / (radio ** 2)
    return fuerza

m1 = float(input('m1: '))
m2 = float(input('m2: '))
r = float(input('Distancia: '))
print('La fuerza de atraccion es', cgu(m1, m2, r))

m1: 5
m2: 1000
Distancia: 10
La fuerza de atraccion es 3.3371399999999995e-09

Opción 2, utilizando $G$ como variable local.

In [11]:
def cgu(masa1, masa2, radio):
    # Tanto fuerza como G son variables locales que solo se conocen en cgu.
    G = 6.67428e-11
    fuerza = G * masa1 * masa2 / (radio ** 2)
    return fuerza

m1 = float(input('m1: '))
m2 = float(input('m2: '))
r = float(input('Distancia: '))
print('La fuerza de atraccion es', cgu(m1, m2, r))

m1: 1
m2: 1
Distancia: 1
La fuerza de atraccion es 6.67428e-11

Ciclos Anidados

Como su nombre lo dice, hay problemas en los cuales es necesario utilizar una estructura repetitiva dentro de otra estructura repetiva. Sintaxis general:

ciclo:
    ciclo:
        ciclo:
            ...

Y en Python:

while condicion:
    while condicion:
        while condicion:
            instrucciones
            ...

Pequeño Ejemplo

Escriba un programa que muestre todas las combinaciones de dos dados que entreguen un puntaje mayor que siete.

In [2]:
dado_1 = 1
while dado_1 <= 6:
    dado_2 = 1
    while dado_2 <= 6:
        if dado_1 + dado_2 > 7:
            print(dado_1, dado_2)
        dado_2 += 1
    dado_1 += 1

2 6
3 5
3 6
4 4
4 5
4 6
5 3
5 4
5 5
5 6
6 2
6 3
6 4
6 5
6 6

Y para que el puntaje sea mayor a 12?

Otro ejemplo

Imprimir (mostrar) todos los números primos en un rango particular recibido como entrada.

In [3]:
# Suponiendo que el rango es siempre correcto (no hay que verificar)
a = int(input("Ingrese a: "))
b = int(input("Ingrese b: "))

# Variable que utilizaremos para probar si es primo
n = a

while n <= b:
    d = 2 # Variable para buscar divisores
    n_divisores = 0 # Contador para numero de divisores
    while d <= n/2:
        if n % d == 0:
            n_divisores += 1
        d += 1

    # Mostramos el numero si es primo
    if n_divisores == 0:
        print(n)

    # Seguimos con el proximo numero
    n += 1

Ingrese a: 0
Ingrese b: 10
0
1
2
3
5
7

Ejercicios

Apliquemos los conceptos revisados en esta clase.

  1. Aproxime la función $e^x$ utilizando Serie de Taylor:
\begin{equation} e^x \approx \sum_{n=0}^{N} \frac{x^n}{n!}, \quad \forall x \in \mathbb{R}, \, n\in\mathbb{N}_0 \end{equation}
In [17]:
N = int(input("Ingrese N: "))
x = float(input("Ingrese x: "))

n = 0
exp = 0
while n <= N:

    # Calculo de factorial
    prod = 1
    i = 1
    while i <= n:
        prod *= i
        i += 1

    # Actualizar acumulador
    exp = exp + (x ** n) / prod

    n += 1

print("Valor aproximacion: ", exp)

Ingrese N: 10
Ingrese x: 5
Valor aproximacion:  146.38060102513225

Resolvamos el mismo ejercicio pero descomponiendo el problema.

In [4]:
def factorial(n):
    prod = 1
    i = 1
    while i <= n:
        prod *= i
        i += 1
    return prod
In [5]:
def aproximacion(N, x):
    n = 0
    exp = 0
    while n <= N:
        exp += (x ** n) / factorial(n)
        n += 1
    return exp
In [6]:
N = int(input("Ingrese N: "))
x = float(input("Ingrese x: "))

exp_aprox = aproximacion(N, x)

print("Valor aproximacion: ", exp_aprox)

Ingrese N: 100
Ingrese x: 1
Valor aproximacion:  2.7182818284590455
  1. Basándose en el ejercicio anterior. Calcule la aproximación de $e^x$ hasta que la diferencia entre dos sumandos sucesivos sea menor a un $\varepsilon$.
In [29]:
x = float(input("Ingrese x: "))
eps = float(input("Ingrese epsilon: "))

flag = True

n = 1
while flag:
    aprox_1 = aproximacion(n, x)
    aprox_2 = aproximacion(n+1, x)

    if abs(aprox_1 - aprox_2) < eps:
        flag = False
    else:
        n += 1

print("Aproximacion: ", aprox_2)
print("Numero de terminos: ", n)

Ingrese x: 5
Ingrese epsilon: 1e-14
Aproximacion:  148.41315910257657
Numero de terminos:  32

Solo por curiosidad...

In [31]:
from math import exp
print(exp(x))

148.4131591025766
  1. En cada ronda del juego del cachipún, los dos competidores deben elegir entre jugar tijera, papel o piedra. Las reglas para decidir quién gana la ronda son: tijera le gana a papel, papel le gana a piedra, piedra le gana a tijera, y todas las demás combinaciones son empates.

El ganador del juego es el primero que gane tres rondas.

Escriba un programa que pregunte a cada jugador cuál es su jugada, muestre cuál es el marcador después de cada ronda, y termine cuando uno de ellos haya ganado tres rondas. Los jugadores deben indicar su jugada escribiendo tijera, papel o piedra.

In [11]:
def cachipun(j1, j2):
    gana = 0 # Para manejar el empate
    if j1 == 'piedra':
        if j2 == 'papel':
            gana = 0
        elif j2 == 'tijera':
            gana = 1
    elif j1 == 'papel':
        if j2 == 'piedra':
            gana = 1
        elif j2 == 'tijera':
            gana = 0
    else:
        if j2 == 'piedra':
            gana = 0
        elif j2 == 'papel':
            gana = 1
    return gana
In [12]:
p1 = 0
p2 = 0

while p1 < 3 and p2 < 3:
    jug_1 = input("Jugador 1: ")
    jug_2 = input("Jugador 2: ")

    if jug_1 != jug_2:
        res = cachipun(jug_1, jug_2)
        p1 += res
        p2 += (1 - res)

    print("Marcador: ", p1, " - ", p2)

if p1 > p2:
    print("Gana jugador 1")
else:
    print("Gana jugador 2")

Jugador 1: papel
Jugador 2: tijera
Marcador:  0  -  1
Jugador 1: tijera
Jugador 2: papel
Marcador:  1  -  1
Jugador 1: piedra
Jugador 2: piedra
Marcador:  1  -  1
Jugador 1: piedra
Jugador 2: tijera
Marcador:  2  -  1
Jugador 1: tijera
Jugador 2: papel
Marcador:  3  -  1
Gana jugador 1
  1. El método de Newton es un algoritmo para encontrar aproximaciones de los ceros o raíces de una función real.
\begin{equation} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \end{equation}

Calcule $\sqrt{2}$, sabiendo que $f(x)=x^2-2$, $f'(x)=2x$. El número máximo de iteraciones $N$ y $x_0$ son entradas del programa.

In [11]:
def f(x):
    return x**2 - 2

def df(x):
    return 2*x

def metodo_newton(x_0, N):
    n = 1
    x = x_0 # Valor inicial
    while n <= N:
        x = x - f(x) / df(x)
        n += 1
    return x

x_0 = float(input("Ingrese valor inicial: "))
N = int(input("Ingrese numero de iteraciones: "))

sol = metodo_newton(x_0, N)

print("La raiz de 2 es aproximadamente: ", sol)

Ingrese valor inicial: 1000
Ingrese numero de iteraciones: 10
La raiz de 2 es aproximadamente:  1.5795487524060154

Nuevamente por curiosidad...

In [12]:
from math import sqrt
print(sqrt(2))

1.4142135623730951
In [13]:
print(abs(sol-sqrt(2)))

0.1653351900329203