Eliminación de duplicados

En esta página, aprenderás una técnica recursiva para eliminar duplicados de una lista.
elementos distintos de (lista (manzanas) (zanahorias) (plátanos) (naranjas) (plátanos) (pan) (zanahorias)) reporta {manzanas, naranjas, plátanos, pan, zanahorias}

Imagina que tienes una lista de elementos y quieres saber si los elementos de la lista son distintos. Por ejemplo, puede que quieras asegurarte de que no tienes nada en tu lista de la compra dos veces.

Como primer paso, responderemos a la pregunta de sí/no: ¿hay duplicados en tu lista?
¿Los elementos de (lista (manzanas) (zanahorias) (plátanos) (naranjas) (plátanos) (pan) (zanahorias)) son distintos? reporta falso

  1. Experimenta con el 'lista ranura de entrada' sin el primer elemento bloque utilizando unas cuantas listas de entradas diferentes. Habla con tu compañero ¿Qué reporta este bloque?
  2. Termina de construir el predicado ¿son los artículos distintos?, que se inicia a continuación. Ya que estás escribiendo un predicado, tu procedimiento siempre debe reportar verdadero o falso.
    Intenta hacerlo sin esta pista.
    Si el programa llega al tercer bloque reporte en el fondo, ¿qué te dice eso sobre los elementos de la lista?
    ¿Los elementos de (datos) son distintos? { si ((datos) vacía?) { reportar () } si ((¿(datos) sin el primer elemento) contiene ()) { reportar () } reportar (¿Los elementos de () son distintos?) }
    Observa que este procedimiento se llama a sí mismo al final. (Es recursivo.) Esto no funcionará si la entrada de esa llamada es la misma que la entrada original. Así que no lo puedes decir reportar (¿Los elementos de (datos) son distintos?). En su lugar, tienes que utilizar un valor de entrada más pequeño.
  3. Habla con tu compañero Si duplicas la longitud de la lista, ¿este algoritmo tomaría la misma cantidad de tiempo? ¿El doble de tiempo? ¿Más del doble de tiempo?

Para tu lista de compras, no solo te gustaría saber si hay o no duplicados. Sería bueno tener una nueva lista con los duplicados eliminados.

  1. Experimenta con el () in front of 'list input slot' bloque utilizando unas pocas entradas diferentes. Habla con tu compañero ¿Qué reporta el bloque?
  2. Construye un reportero elementos distintos de utilizando una estructura similar a la del predicado ¿son distintos los elementos?.
    elementos distintos de (datos) { si ((datos) vacía?) { reportar () } si ((¿(datos) sin el primer elemento) contiene ()) { reportar () } reportar () }

    El algoritmo para este bloque tomará las mismas decisiones que en ¿son los elementos distintos?. Pero eso era un predicado. Este tiene que reportar una lista. Así que mira los tres bloques reportar en tu código para el predicado ¿son los elementos distintos?, y decide que deben reportar estos para el reportero elementos distintos de.

    ¿Necesitas otra pista?

    • Si la lista está vacía, ¿qué reportará elementos distintos de?
    • Si el primer elemento de la lista aparece en el resto de la lista, no importa qué copia dejes fuera. ¿Existe una forma fácil de obtener una versión de la lista sin una de esas copias?
      • ¿Y si hay otros duplicados en esa lista?
    • Si la computadora llega al tercer bloque reportero, ¿qué te dice eso sobre el primer elemento de la lista? ¿Quieres que el primer elemento sea parte de la lista que reportas?

  3. Pruébalo. Asegúrate de escoger buenos casos de prueba: más de un par de duplicados, más de dos elementos del mismo valor, duplicados uno al lado del otro en la lista, etc.
  4. "U5L1-EliminarDuplicados"Guarda tu trabajo como U5L1-EliminarDuplicados