Esquemes de tractament seqüencial

Introducció

Un esquema de programació no és altra cosa que un model de solució per a a una família de problemes de programació homòlegs. L'ús d'esquemes de programació és una eina imprescindible per al programador atès que el seu ús facilita molt la solució de problemes i rebaixa considerablement la taxa d'errors de programació.

Aquesta estratègia de treball no és única de l'àmbit de la programació sinó que també l'apliquem en altres disciplines. Per exemple, a física quan aprenem a resoldre problemes de tir parabòlic o a matemàtiques quan aprenem  a calcular primitives fent integració per parts.

La metodologia general segueix aquests passos:

  1. Indentificació del tipus de problema.
  2. Caracterització dels elements característics.
  3. Aplicació de l'esquema.

En aquest material introduïrem els esquemes seqüencials, és a dir els que s'apliquen a dades que tenen estructura de seqüència.

Seqüències

Una seqüència és un conjunt de dades de qualsevol tipus que es caracteritzen per estar disposades «en forma de fila», ja sigui des d'un punt de vista físic o conceptual. Moltes de les dades que manipula un programa tenen estructura de seqüència. Per exemple, un string com ara "Hola nois", pot ser considerat com una seqüència de caracters ('H', 'o', 'l',...) o una matriu de reals com una seqüència de files. Més formalment, una seqüència és una conjunt de dades tal que:

  • És finit.
  • Conté un element que és el primer de la seqüència
  • Es pot definir la relació de "següent", que donat un element de la seqüència, diu quin ve a darrera.

Per exemple, el enters de 1 a 10 tenen estructura de seqüència atès que són un conjunt finit, tenen un primer ben definit (l'1) i la relació de següent consisteix a sumar una unitat a l'anterior.

Iteracions i seqüències

Les iteracions s'usen habitualment com a eina per manipular dades amb estructura seqüencial. Fixeu-vos en aquest programa que compta quantes paraules més llargues de tres caràcters té la llista l:

l = ['hola', 'ale', 'ea', 'citron']
i = 0
n = 0
while i < len(l):
if len(l[i]) > 3:
n += 1
i += 1

La iteració while s'està usant per manipular la llista l i l és una estructura seqüencial (com totes les llistes!).

Els esquemes seqüencials serveixen per a dissenyar les iteracions dels programes de manera eficaç. La idea és molt senzilla: quan tenim un problema a resoldre sobre unes dades seqüencials de manera iterativa, s'aplica l'esquema addient i llestos!

Esquema de recorregut

L'esquema de recorregut s'aplica a un problema si:

  • Tracta dades amb estructura seqüencial
  • Per resoldre el problema cal «visitar» totes les dades

L'esquema té aquest aspecte:

e = <primer>
while not <sentinella>:
<tractament>
e = <seguent>

Com veieu, un esquema és una plantilla de programes que té forats per omplir. En el cas que ens ocupa els forats són els següents:

  • <primer>
    Fa referència a un càlcul (trivial o complicat) que ens dóna el primer element de les dades a tractar.
  • <sentinella>
    És una expressió booleana que s'avalúa a fals per a tots els elements del conjunt a tractar i a cert per aquells que no són del conjunt.
  • <següent>
    És un càlcul (trivial o complicat) que calcula l'element de la seqüència que vé després d'e.
  • <tractament>
    És un bloc de codi que s''aplica a cada element visitat. És la única part que depèn del problema a resoldre atès que les parts anteriors depenien de les dades i no pas del problema.

Exemple 1

Tenim una llista d'enters l i volem calcular-ne la suma. Evidentment es tracta d'un recorregut atès que per calcular-ne la suma cal visitar tots els elements de la llista. Aleshores es pot resoldre aplicant l'esquema:

s = 0
i = 0
while i < len(l):
s += l[i]
i += 1

En aquest darrer exemple els elements de la seqüència són enters, el primer element és 0, el següent element es calcula sumant 1 a l'anterior i el sentinella és l'enter len(l). Noteu com el sentinella és un element que no forma part de la seqüència tractada. Finalment, el tractament consisteix a incrementar la variable s amb l[i].

Exemple 2

Escriviu un programa que compti en nombre de a's de l'string s. En aquest cas, també es tracta clarament d'un recorregut atès que cal analitzar totes les lletres de l'string per poder comptar el nombre de a's. Aplicant l'esquema resulta:

na = 0
i = 0
while i < len(s):
if s[i] == 'a':
na += 1

Fixeu-vos que en aquest cas. el tractament consisteix en una sentència condicional.

Exemple 3

Escriviu els 10 primers múltiples de 7. En aquest cas, la seqüència es tracta dels enters entre 0 i 9. La solució és immediata:

i = 0
while i < 10:
print i*7
i += 1

Exemple 4

Calculeu la llista formada pels elements que ocupen posicions parells en la llista l. En aquest cas una solució podria ser:

i = 0
lp = []
while i < len(l):
lp += [l[i]]
i += 2

Exemple 5

Donada una llista l, escriviu els elements que ocupen posicions múltiples de 3 o de 5. La solució a aquest recorregut podria ser:

i = 0
while i < len(l):
if i % 3 == 0 or i % 5 == 0:
print l[i]
i += 1

 

Recorreguts amb l'iterador for

Els recorreguts són tant freqüents en els programes que el llenguatge de programació Python ofereix una sentència específica per a fer recorreguts. Es tracta de la sentència for. Molts dels casos de recorregut (si bé no tots) poden expressar-se amb aquesta sentència. L'exemple 1 es pot expressar amb aquesta sentència fent:

s = 0
for e in l:
s += e

De la mateixa manera, l'exemple 2 es pot expressar fent:

na = 0
for c in s:
if c == 'a':
na += 1

L'exemple 3 és també expressable amb l'iterador for. Aquesta vegada, però, cal fer ús de la funció range:

for i in range(10):
print i*7

L'exemple 4 també es pot reescriure amb l'ajuda de range:

lp = []
for i in range(0,len(l),2):
lp += [l[i]]

Una forma alternativa de escriure aquest recorregut, una mica més sintètica i preferible a l'anterior, és la següent:

lp = []
for e in l[::2]:
lp.append(e)

Finalment l'exemple 5 també es pot reescriure amb un iterador for si ens ajudem de la funció enumerate de la següent manera:

for i,e in enumerate(l):
if i % 3 == 0 or i % 5 == 0:
print e

Esquema de cerca

L'esquema de cerca és semblant al de recorregut. En aquest cas, però, l'objectiu no és tractar tots els elements d'una seqüència sinó determinar si la seqüència conté un element que cumpleixi una condició específica.  Un problema típic d'aquesta tipologia és el de determinar si una llista d'enters conté el número 9. Fixeu-vos que, a diferència de l'esquema de recorregut, generalment a una cerca no li cal visitar tots els elements de la seqüència ja que una vegada trobat l'element cercat es pot acabar el procés. Resumint direm que un esquema de cerca s'aplica si:

  • Tracta dades amb una estructura seqüencial.
  • Per resoldre el problema cal cercar un element de la seqüència amb una determinada característica.

L'esquema de cerca té aquest aspecte:

trobat = False
e = <primer>
while not trobat and not <sentinella>:
if <propietat>:
trobat = True
else:
e = <següent>

L'esquema que s'ha mostrat, que es coneix com cerca amb booleà per motius obvis, considera els següents elements a més dels que ja eren propis de l'esquema de recorregut:

  • <propietat> és una funció booleana sobre el element e que torna cert ssi e és l'element que buscàvem.

Exemple 6

Donada una llista de reals l, determineu si conté un negatiu.

En aquest problema, l'element buscat té la propietat de ser negatiu, aleshores, aplicant l'esquema tenim la següent solució:

trobat = False
i = 0
while not trobat and i < len(l):
if l[i] < 0.0:
trobat = True
else
i += 1

Fixeu-vos que, en acabar aqest troç de codi, la variable trobat val True o False segons si la llista conté un negatiu o no.

Exemple 7

El problema de la inserció única consisteix a inserir en una llista un element únicament si aquest no hi era prèviament. Dissenyeu una funció que donada una llista l i un enter k, afegeixi k a la llista solament si l no contenia k.  La solució passa per cercar k a la llista i actuar segons si l'hem trobat o no. Aplicant l'esquema tenim:

def inserir(l,k):
trobat = false
i = 0
while not trobat and i < len(l):
if l[i] == k:
trobat = True
else:
i += 1
# insereix si no existia
if not trobat:
l.append(k)

Com veieu,  sovint després d'una cerca hi ha un petit càlcul que depèn de si s'ha trobat l'element buscat o no.

Exemple 8

Escriviu una funció que donada una llista de paraules l i una paraula p, retorni la (primera) posició dins la llista l en que apareix la paraula p o bé -1 en cas que la paraula no es trobi en la llista. De nou, apliquem l'esquema per trobar la paraula en la llista:

def on_es(l,p):
trobat = False
i = 0
while not trobat and i < len(l):
if l[i] == p:
trobat = True
else:
i += 1
# segons si trobada
if trobat:
return i
else
return -1

Cerques amb l'iterador for

Tal i com i succeia amb els recorreguts, Python ofereix eines específiques per dur a terme la majoria de cerques de manera més amable. En aquest cas es tracta de complementar l'iterador for amb algunes funcionalitats més que permeten descriure cerques amb més comoditat. En essència es tracta de les sentències:

break
Aquesta sentència, quan s'executa dins d'una iteració, provoca la sortida immediata de la iteració.
else
La sentència else aplicada a les iteracions (no a els if!!!) s'executa únicament si la iteració corresponent acaba normalment, és a dir no acaba bruscament per culpa d'un break.

Amb aquestes dues sentències, l'iterador for és fàcilment aplicable a les cerques.  L'exemple 6 vist abans pot reescriure's fent

for e in l:
if e < 0.0:
trobat = True
break
else:
trobat = False

Noteu que hem mantingut la variable trobat per coherència amb el problema original tot i que no és del tot necessària. Pel que fa a l'exemple 7, la versió corresponent podria ser:

def inserir(l,k):
for e in l:
if e == k:
break
else:
l.append(k)

Fixeu-vos com la forma respecte l'original és molt més senzilla. Finalment, l'exemple 8 podria reescriure's de la següent forma:

def on_es(l,p):
for i,w in enumerate(l):
if w == p:
return i
return -1

Noteu que en aquest cas particular hem acabat l'iteració inserint un return directament en el cos del for. Aquest return trenca l'execució del for. Noteu també com el darrer return només s'executa en cas que el primer no ho faci.