Tema 6: Esquemes de tractament seqüencial

Objectius i argument

Contrariament als temes vists fins ara, aquest tema és de caire metodològic. Després d'haver introduït els principals elements del llenguatge Python, en aquest tema s'aborda la problemàtica del disseny d'iteracions. L'enfoc adoptat és el dels esquemes de programació: un mecanisme senzill i potent en mans de programadors entrenats.

Resultats d'aprenentatge

Un estudiant que hagi assolit aquest tema ha de ser capaç de:

Identificar i caracteritzar correctament els problemes de recorregut i cerca seqüencial.
Aplicar els esquemes de cerca i recorregut de manera sistemàtica cada vegada que cal dissenyar una iteració.
Implementar esquemes de cerca i recorregut emprant l'iterador for.

Conceptes clau

Esquema de programació. Seqüència. Esquema de recorregut. Esquema de cerca. Cerca amb booleà. Iterador for. Sentència break. Sentència else (aplicada a iteracions).

Referència principal

La referència principal en aquest cas són aquests apunts sobre Esquemes de Programació.

Referències complementàries

Els esquemes de tractament seqüencial són una eina fonamental tant des d'un punt de vista didàctic com pràctic. La primera referència d'aquesta metodologia és la del llibre:

Pierre-Claude Scholl and Jean-Pierre Peyrin, Schémas algorithmiques fondamentaux, Masson, Paris 1988. (amb traducció al castellà a l'editorial Mason).

Posterioment, aquesta metodologia ha estat emprada en nombroses obres d'iniciació a la programació. Alguns exemples ón:

Jordi Àlvarez Canal, Xavier Burgués Illa Raymond Lanonigro Bertran, et al., Fonaments de programació, Ed. UOC. ISBN:978-84-9788-735-9. (en podeu veure els capítols sobre tractament seqüèncial a Google Books)

Exercicis obligatoris de teoria

Recordeu que per resoldre els següents exercicis, totes les funcions han d'estar correctament documentades amb els doctests.

EOT 6.1

Dissenyeu una funció tal que, donada una llista de enters qualsevol, retorni la llista en ordre invers. Implementeu-la amb una iteració.

EOT 6.2

Dissenyeu una funció tal que, donada una llista qualsevol la modifiqui esborrant-ne els elements que ocupen posicions múltiples de 3 o de 5 i que no siguin parells.

EOT 6.3

Dissenyeu una funció tal que, donada una llista de números enters compresos entre 0 i 10, imprimeixi la llista de freqüències dels diferents números remarcant el de més freqüència. Serviu-vos de les funcions auxiliars que cregueu oportunes.

EOT 6.4

Dissenyeu una funció tal que, donada una llista de reals l, retorni una llista amb els mateixos elements ordenats en sentit ascendent. A tal efecte, useu el mètode d'inserció directa. Aquest mètode consisteix a repetir des del segon component fins al darrer component el següent procés: situar aquest component en el lloc on li correspongui per ordre entre les components situades a l'esquerra d'aquest (aquestes ja estaran ordenades). Mentre que a la dreta quedaran les components que s'hauran d'ordenar en passes posteriors.

Per exemple, donada la llista [2.0,1.5,4.0,2.1], els passos intermitjos serien:

1era. iteració, seleccionaríem 1.5 i el situariem davant de 2.0, la llista quedaria així [1.5,2.0,4.0,2.1]
2ona. iteració, seleccionaríem el 4.0 però la llista no canviaria
n-1 iteració, seleccionaríem el darrer element i el situaríem en l'ordre que li correspont dins dels n-1 elements a la seva esquerra, en aquest cas la llista ja estaria ordenada

EOT 6.5

Dissenyeu una funció tal que donada una llista de 10 alumnes (identificats amb un codi enter entre 1 i 10), i les seves notes en 5 assignatures (expressades amb un real), imprimeixi quin és l’alumne amb mitjana més gran i quina és aquesta.

Per exemple, una llista amb un sol alumne, el 3, podria tenir la següent estructura

 [[3,[2.5,3.9,6.35,5.6,8.25]]]

EOT 6.6

Suposeu que teniu una llista que representa els resultats d'un campionat de futbol. Cada element de la llista representa l'equip d'una població segons la següent estructura:

[nom_ciutat, partits_guanyats, partits_empatats, partits_perduts, gols_a_favor, gols_en_contra]

Es demana que dissenyeu una funció tal que donada una llista de resultats retorni el nom de la ciutat que correspon a l'equip guanyador del campionat. L'equip guanyador és el que acumula més punts. Per tal de determinar la puntuació de cada equip considereu que:

Cada partit guanyat compta 2 punts i cada partit empatat 1 punt.

En cas que dos equips tinguin els mateixos punts, caldrà considerar que guanyarà l'equip amb la menor diferència entre gols a favor i gols en contra. En cas que aplicant aquest criteri encara hi hagi empat, es considerarà qualsevol dels equips empatats com el guanyador.

Exercicis obligatoris de laboratori

Recordeu que per resoldre els següents exercicis, totes les funcions han d'estar correctament documentades amb els doctests.

EOL 6.1

Dissenyeu un programa tal que donat una seqüència d'enters acabada en 0 (que actua de sentinella), escrigui els que són superiors a la mitjana.

A tal efecte, us caldrà dissenyar les funcions per fer les tasques que s'especifiquen a continuació:

Emmagatzemar els elements en una llista. Feu-ho utilitzant una funció que demani a l'usuari la seqüència d'enters i retorni una llista d'enters.
Calcular la mitjana d'elements d'una llista. Feu-ho utilitzant una funció que donada una llista, retorni la mitjana dels elements de la llista.
Obtenir els elements superiors a la mitjana. Feu-ho utilitzant una funció que, donada una llista i un valor, retorni en una altra llista els elements superiors a aquest valor.

EOL 6.2

La cadena de producció d'una fàbrica de components electrònics vol dissenyar un algorisme per al control de qualitat de les peces que fabriquen. Per poder sortir al mercat, les peces han de tenir un pes d'entre 100 i 150 grams.

Dissenyeu un programa tal que, donada la seqüència de pesos (en grams) d'una partida de peces, detecti si totes passen el control de qualitat. La seqüència acaba amb un pes fictici -1 (sentinella).
A tal efecte heu de considerar el següent:

Cal dissenyar una funció tal que donat un valor, retorni cert si es tracta d'una peça no defectuosa i fals en cas contrari
Cal dissenyar una funció tal que demani a l'usuari valors de la seqüència fins que es trobi alguna peça defectuosa o s'arribi al final de la seqüència. Utilitzeu doncs un esquema de cerca.

Dissenyeu un programa tal que, donada la seqüència de pesos (en grams) determini quantes no passen el control de qualitat. La seqüència acaba amb un pes fictici -1 (sentinella).
A tal efecte heu de considerar el següent:

Cal dissenyar una funció que demani a l'usuari valors fins al final de la seqüència i calculi quants dels valors introduïts corresponen a peces defectuoses.

EOL 6.3

Dissenyeu un programa tal que donades una seqüència de paraules acabada amb la paraula 'X', escrigui aquelles que tenen la mateixa mida que la paraula més llarga.

A tal efecte heu de considerar el següent:

Cal dissenyar una funció tal que donada una paraula comprovi si es tracta de la paraula 'X'. Si és el cas retornarà cert, altrament retornarà fals.
Cal dissenyar una funció que demani a l'usuari paraules fins arribar a la paraula 'X' i les retorni en una llista.
Cal dissenyar una funció que donada una llista de paraules, calculi la mida de la paraula més gran.
Cal dissenyar una funció que donada una llista de paraules l i un valor v, retorni la llista de paraules de l que tenen mida v.

EOL 6.4

Afegiu el que calgui a l'exercici anterior perquè escrigui més a més, si l'usuari ha introduït la paraula 'informàtica'.

Pista:

Cal dissenyar una nova funció tal que, donada una llista de paraules, retorni cert si conté la paraula informàtica i fals en cas contrari. Aquesta funció ha d'utilitzar l'esquema de cerca.

Exercicis optatius

EOP 6.1

Dissenyeu una funció que, donada una llista d'enters, retorni Cert ssi la llista és creixent. Un cop la tingueu, dissenyeu un programa que llegeixi una llista de 10 enters i comprovi si aquesta és creixent.

EOP 6.2

Dissenyeu una funció que, donada una llista de cadenes, determini si totes les comencen per la lletra 'a'. Un cop la tingueu, dissenyeu un programa que vagi llegint cadenes fins a trobar la cadena sentinella 'final', i a continuació comprovi si totes les cadenes de la llistan comencen per la lletra 'a'.

EOP 6.3

Dissenyeu una funció que, donada una llista de cadenes, determini quantes comencen per la lletra 'a'. Un cop la tingueu, dissenyeu un programa que vagi llegint cadenes fins a trobar la cadena sentinella 'prou', i a continuació imprimeixi el nombre de cadenes de la llista que comencen per la lletra 'a'.

EOP 6.4

Dissenyeu una funció que, donada una cadena, retorni Cert ssi la cadena és cap-i-cua.

EOP 6.5

Dissenyeu una funció que llegeixi una cadena i retorni Cert ssi conté dues vegades la lletra 'm'.

EOP 6.6

Dissenyeu un programa que llegeixi 10 cadenes i emmagatzemi en una llista totes aquelles cadenes llegides que continguin algun digit. A continuació, el programa ha d'afegir la subacadena "bogeria" al principi de cada cadena de la llista i, finalment, ha d'imprimir per pantalla aquelles cadenes que tinguin més de 15 lletres.

EOP 6.7

Dissenyeu una funció anomenada en_general_positiva que, donada una llista de reals, retorni Cert ssi hi ha més d'un 50% de valors positius.

EOP 6.8

Dissenyeu una funció que, donada una llista de reals, retorni una llista amb tres elements enters: el primer ha de correspondre al nombre d'elements negatius de la llista, el segon al nombre d'elements iguals a zero i el tercer, ha de ser el nombre d'elements positius.