In [6]:
"""
IPython Notebook v4.0 para python 2.7
Librerías adicionales: Ninguna.
Contenido bajo licencia CC-BY 4.0. Código bajo licencia MIT. (c) Sebastian Flores.
"""

# Configuracion para recargar módulos y librerías 
%reload_ext autoreload
%autoreload 2

from IPython.core.display import HTML

HTML(open("style/iwi131.css", "r").read())


Out[6]:






IWI131

Programación de Computadores

Sebastián Flores

http://progra.usm.cl/

https://www.github.com/sebastiandres/iwi131

Clase anterior

  • ¿Instalaron python?
  • Algoritmo vs Programa Computacional

¿Qué contenido aprenderemos?

  • Modelamiento de problemas
  • Diagrama de flujo

¿Porqué aprenderemos ese contenido?

  • Modelamiento de problemas
    • Paso esencial para entender y luego solucionar un problema.
  • Diagrama de flujo
    • Permite modelar las distintas etapas de una solución.
    • Facilita la programación.

Definición

Un diagrama de flujo es una representación gráfica de un algoritmo.

  • Los pasos son representados por varios tipos de bloques
  • El flujo de ejecución es indicado por flechas que conectan los bloques.

Simbología

Estructuras de un diagrama de flujo

  • Estructuras secuenciales
  • Estructuras condicionales
  • Estructuras repetitivas

Estructuras secuenciales

Estructuras secuenciales

Ejemplo: Calcular el perímetro y el área de un círculo.

Estructuras secuenciales

Ejemplos de la clase:

  • 1- Cortar un apel
  • 2- Comprar pan
  • 3- Llegar a clases

Estructuras condicionales

Estructuras condicionales

Ejemplo: Determinar si un número es par o impar.

Estructuras condicionales

Ejemplos de la clase:

  • 1- Mayor entre 2 numeros
  • 2- Decidir si vale la pena ir a clases
  • 3- Cualquier eleccion.

Estructuras de repeticion

Estructuras de repeticion

Ejemplos: Calcular el promedio de 5 notas.

Estructuras de repetición

Ejemplos de la clase:

  • 1- Determinar si un nro es primo
  • 2- Elegir ropa
  • 3- Jugar tenis

¿Cómo aprenderemos?

  • Aplicación a problemas

Problema 1 : Números mágicos

Usando la notación de diagrama de flujo diseñe un algoritmo para determinar si un número natural n es mágico o no.

Definición de Número Mágico

  • Un número se dice mágico cuando la suma de sus divisores es igual al número.
  • En la suma no se debe considerar al mismo número como un divisor.

Ejemplo:

  • 28 = 1+2+4+7+14 es un número mágico
  • 32 != 1+2+4+8+16 no es un número mágico

Problema 1: Números mágicos

  • Modelamiento
  • Diagrama de flujo

Problema 1: Números mágicos

  • ¿Cuál era el output requerido? ¿Cuál era el input posible?
  • ¿Qué pasos son necesarios?
  • ¿Qué estructuras necesitamos: secuencias, condiciones, repetición?

Modelamiento

  1. Leer N
  2. Para cada numero m entre 1 y N-1, ambos incluídos:
    • Si m es divisor de N, agregarlo a la suma de divisores
    • Si m no es divisor de N, no hacer nada
  3. Ver si la suma de divisores es igual al N

Problema 1: Números mágicos

Diagrama de flujo

Problema 1: Números mágicos

Implementación


In [14]:
def es_magico(N):
    suma_divisores = 1
    for  m in range(2,N):
        if N%m==0:
            suma_divisores = suma_divisores + m
    if suma_divisores==N:
        print N, "es mágico"
    else:
        print N, "no es mágico"
mi_numero = int(raw_input("Ingrese un número: "))
es_magico(mi_numero)


---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-14-6cd64beff7ac> in <module>()
      8     else:
      9         print N, "no es mágico"
---> 10 mi_numero = int(raw_input("Ingrese un número: "))
     11 es_magico(mi_numero)

/usr/local/lib/python2.7/dist-packages/IPython/kernel/zmq/kernelbase.pyc in raw_input(self, prompt)
    649             self._parent_ident,
    650             self._parent_header,
--> 651             password=False,
    652         )
    653 

/usr/local/lib/python2.7/dist-packages/IPython/kernel/zmq/kernelbase.pyc in _input_request(self, prompt, ident, parent, password)
    679             except KeyboardInterrupt:
    680                 # re-raise KeyboardInterrupt, to truncate traceback
--> 681                 raise KeyboardInterrupt
    682             else:
    683                 break

KeyboardInterrupt: 

Follow-up

  • ¿Qué pasos fueron necesarios?
  • ¿Qué fue lo difícil del ejercicio?
  • ¿Qué fue lo fácil del ejercicio?
  • ¿Qué aprendimos del ejercicio?

Problema 2: Secuencia de Collatz

Realice un diagrama de flujo para el siguiente proceso:

  • Solicite el ingreso de un número hasta que se ingrese el valor cero.
  • Luego al número ingresado se le deben realizar las siguientes operaciones hasta convertirse en el valor 1. Si el número es par se debe dividir por 2, sino se debe multiplicar por 3 y sumarle 1.
  • Una vez ingresado el valor cero, se debe mostrar la cantidad de números ingresados y la cantidad de pasos realizados para convertirlos en 1.

Ejemplo:

  • Si se ingresa 1, la secuencia es 1 FIN. Requiere 0 pasos.
  • Si se ingresa 2, la secuencia es 2/2=1 FIN. Requiere 1 paso.
  • Si se ingresa 3, la secuencia es (3x3+1)=10, (10/2)=5, (3x5+1)=16, 16/2=8, 8/2=4, 4/2=2, 2/2=1 FIN. Requiere 7 pasos.

Problema 2: Secuencia de Collatz

  • Modelamiento
  • Diagrama de flujo

Problema 2: Secuencia de Collatz

  • ¿Qué pasos son necesarios?
  • ¿Que estructuras necesitamos: secuencias, condiciones, repetición?
  • ¿Cómo podemos dividir el problema en subproblemas más simples? ### Modelamiento

Bucle general:

  1. Leer número.
  2. Si número es cero detener.
  3. Calcular secuencia de Collatz para el número, contando los pasos requeridos.
  4. Volver a 1.

Bucle de secuencia de Collatz para n:

  1. Si n=1, detener.
  2. Si n es par, asignar n=(n/2).
  3. Si n es impar, asignar n=3n+1

Problema 2: Secuencia de Collatz

Diagrama de flujo

Problema 2: Secuencia de Collatz

Implementación


In [ ]:
def leer_numeros_e_imprimir_solucion():
    N = int(raw_input("Ingrese un número: "))
    total_pasos = 0
    total_numeros = 0
    while N!=0:
        total_pasos += collatz(N)
        total_numeros += 1
        N = int(raw_input("Ingrese un número: "))
    print total_numeros, "números ingresados"
    print total_pasos, "pasos en la secuencia"
    
        
def collatz(N):
    n_pasos = 0
    while N!=1:
        if N%2==0:
            N = N/2
        else:
            N = 3*N+1
        n_pasos += 1
    return n_pasos

leer_numeros_e_imprimir_solucion()

Follow-up

  • ¿Qué pasos fueron necesarios?
  • ¿Qué fue lo difícil del ejercicio?
  • ¿Qué fue lo fácil del ejercicio?
  • ¿Qué aprendimos del ejercicio?

¿Preguntas?