Estás en:   ArielOrtiz.com > Estructura de datos > Búsquedas

Búsquedas

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Usando el lenguaje de programación Python versión 3.2, escribe las funciones que se describen a continuación. Coloca todas las funciones en un mismo archivo llamado tarea_busquedas.py. En la parte superior del archivo coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo: 

#--------------------------------------------------------------------
# Actividad de programación: Búsquedas 
# Fecha: 24-Ago-2012
# Autores:
#           1166611 Pepper Pots  
#           1160611 Anthony Stark
#--------------------------------------------------------------------

  1. cuenta_ocurrencias(x, lst): Devuelve el número de veces que aparece el elemento x en lst.

    Ejemplos: 

    >>> cuenta_ocurrencias(4, [6, 4, 2, 5, 4, 4, 7, 9]) 
3
>>> cuenta_ocurrencias(3, [6, 4, 2, 5, 4, 4, 7, 9]) 
0
>>> cuenta_ocurrencias(42, []) 
0

  2. mas_repetido(lst): Devuelve el elemento que aparece el mayor número de veces en lst. Si hay un empate entre varios elementos, entonces devuelve el elemento que aparece primero en lst. Devuelve None si lst está vacía.

    Ejemplos: 

    >>> mas_repetido([6, 4, 2, 5, 4, 4, 7, 9])
4
>>> mas_repetido([2, 1, 2, 3, 2, 1, 2, 1, 1])
2
>>> mas_repetido([5, 4, 3, 2, 1])
5
>>> print(mas_repetido([]))
None

  3. indices_mas_repetido(lst): Similar a la función del problema 2, pero devuelve una tupla de la forma: (x, índices), en donde x es el elemento que más veces se repite en lst e índices es una lista con los índices donde x aparece en lst. Devuelve None si lst está vacía.

    Ejemplos: 

    >>> indices_mas_repetido([6, 4, 2, 5, 4, 4, 7, 9])
(4, [1, 4, 5])
>>> indices_mas_repetido([2, 1, 2, 3, 2, 1, 2, 1, 1])
(2, [0, 2, 4, 6])
>>> indices_mas_repetido([5, 4, 3, 2, 1])
(5, [0])
>>> print(indices_mas_repetido([]))
None

  4. mas_repetido_con_empates(lst): Similar a la función del problema 2, pero devuelve una tupla de la forma: (n, empates), en donde n es el número de veces que aparece el elemento que más veces se repite en lst y empates es una lista con todos los elementos que aparecen n número de veces en lst. Devuelve la tupla (0, []) si lst es una lista vacía.

    Ejemplos: 

    >>> mas_repetido_con_empates([6, 4, 2, 5, 4, 4, 7, 9])
(3, [4])
>>> mas_repetido_con_empates([2, 1, 2, 3, 2, 1, 2, 1, 1])
(4, [2, 1])
>>> mas_repetido_con_empates([5, 4, 3, 2, 1])
(1, [5, 4, 3, 2, 1])
>>> mas_repetido_con_empates([])
(0, [])

  5. busqueda_binaria_iterativa(x, lst): Tiene la misma funcionalidad que busqueda_binaria_recursiva (vista en clase) pero sin usar recursión. Es decir, se debe usar el mecanismo de iteración convencional (por ejemplo un ciclo while) en lugar de llamadas a sí misma (recursivas). En este caso no se requiere definir una función auxiliar. Solo es necesario definir inicio y fin como variables locales inicializadas con sus valores correspondientes. El ciclo termina cuando se encuentra el elemento buscado o cuando inicio > fin. El cuerpo del ciclo consiste en actualizar las variables inicio o fin según lo determinen las comparaciones que se vayan realizando.

    Usa los mismos ejemplos vistos en clase para probar esta función.

¿Qué se debe entregar?

Sube el archivo tarea_busquedas.py usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.

Fecha límite: Viernes, 24 de agosto.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

100 La actividad cumple con todos los requerimientos.
-10 No se incluyó en comentario los datos de los autores.
10 El programa fuente contiene errores sintácticos.
50-90 El programa produce algunos errores al momento de correrlo.
DA La solución es un plagio.