Tutora 3

Computacin

Miguel Enrique Campusano Araya

mcampusa@dcc.uchile.cl

1 Listas y Tuplas

1.1 Concepto

No podemos manejar un nmero indeterminado de constantes ni variables Permite manejos iterativos sobre conjuntos de elementos Los elementos pueden ser cualquier valor vlido en Python, lo que permite crear listas de listas(llamadas listas de dos dimensiones o matrices).

Una de las grandes diferencias (sino la ms importante) es que las tuplas no se pueden modi-car.

Listas tienen orden (funcin sort). Tuplas tienen estructuras (pueden ser llaves en un diccionario).

1.2 Ejemplo

Veamos:

|[1, 3, 5] lista con varios elementos |[hola, 4, 4.5] lista con distintos elementos |[ ] lista vacaTodo esto se pueden escribir como tuplas. Notamos que estos ejemplos son muy grcos de ver, en

cambio las listas de listas pueden confundir un poco el como verlas.

|[[1,2], [3,4], [5,6]]Como vemos, tiene una notacin un tanto no intuitiva, pero podemos verlo de esta manera:

0: [1,2] 1: [3,4] 2: [5,6]

1

1.3 Problemas

1.3.1

Escriba un programa que lea una lista de nmeros (que termina con un cero) y escriba cual fue el

mayor y el menor nmero y adems el promedio de todos.

1.3.2

Escriba un programa tal que lea un archivo notas.txt donde en cada linea se encuentran notas de

3 controles distintos separadas por espacios. Este archivo tiene que ser procesado de tal forma que

entregue la nota mxima, mnima y el promedio para cada uno de los controles y adems entregue

la nota mxima, mnima y el promedio para el promedio de los 3 controles.

1.3.3

Sea A := (aij)mn y B := (bij)np dos matrices, se dene la multplicacin de matrices como:

AB := (cij)mp

donde

cij =n

r=1

airbrj

Se pide programar la funcin timesM(A,B) que recibe dos matrices y retorne una tercera, la cual

es su multiplicacin. Suponga que las matrices estan representadas como listas de listas de tamao

consistente para el funcionamiento de esto.p

2 Diccionario

2.1 Concepto

Nos basamos en la misma idea que listas y tuplas, pero usamos un llave en lugar de un ndice Esta llave debe ser un valor no mutable de python (un nmero, string, tupla) La idea general es que las llaves tienen un valor agregado y no solo son un ndice.2.2 Ejemplo

nombre: cosme apellido: fulanito direccion: calle falsa #123Veamos que todos los elementos a la izquierda son las llaves y a la derecha sus valores, luego si

queremos obtener el nombre y el apellido del diccionario de arriba (llamemoslo d), sera:

d['nombre'],' `,d['apellido']2.3 Problemas

2.3.1

Escriba un programa tal que reciba un archivo notas.txt que tiene como formato nombre y luego

su nota separada por un espacio. El archivo representa una persona y su nota, la persona puede

aparecer varias veces en el archivo. Su programa debe ser capaz de entregar quien tiene la nota

mayor y quien tiene el mejor promedio.

2

2.3.2

En este problema se le pide implementar una forma autmatica de obtener los ganadores de los

grupos de la copa amrica. Para ello se disponen de tres archivos para los grupos A.txt, B.txt

y C.txt, donde el formato es pais puntos goles, estas tablas no estan necesariamente ordenadas.

Su programa debe poder imprimir quienes son los paises que pasarn a la siguiente ronda (puede

suponer que los puntos siempre son distintos entre los grupos), los equipos que pasan son los 2

primeros de cada grupo y 2 mejores terceros que, para simplicar, se determinarn por puntos y

si empatan por puntos, deberemos ver que equipo tiene ms goles (supongo que de aqu nunca

empatan en goles).

2.3.3 Extra

Tome el ejercicio anterior, y cree los braquets de los cuartos de nales, esto es, el orden de los

partidos de la siguiente fase, donde se enfrentan de esta manera:

Primero grupo A - Primer mejor tercero Segundo grupo A - Segundo grupo C Primero grupo B - Segundo mejor tercero Primero grupo C - segundo grupo B3 Ordenamiento y Bsqueda

3.1 Concepto

Problemas muy interesantes dentro de la computacin. La forma ms intuitiva de hacerlo muchas veces es la ms lenta.

3.2 Problemas

3.2.1 Bubble Sort

El algoritmo de ordenamiento de Bubble Sort lo que hace es recorrer la lista y toma dos elementos,

donde se posiciona y el vecino derecho, luego los compara y si el derecho es mayor al elemento

actual, los intercambia. Y asi, repite el proceso hasta que no se realicen intercambios.

Usted deber programar este algoritmo en python y muestre que es de orden O(n2) en el peor caso.

3.2.2 Busqueda Binaria

La bsqueda binaria es uno de los algoritmos de bsqueda ms conocidos por su simplicidad y buen

comportamiento. Programe este algoritmo en python y muestre que es de orden O(log2n). Recuerdeque este algoritmo recibe una lista ya ordenada.

3

Listas y TuplasConceptoEjemploProblemas

DiccionarioConceptoEjemploProblemasExtra

Ordenamiento y BsquedaConceptoProblemasBubble SortBusqueda Binaria