ESQUEMA DE RECORRIDO INFORMÁTICO (CATALÁN)

ESQUEMA DE RECORREGUT

L’esquema de recorregut s’aplica en els problemes on s’han de tractar tots els elements d’una seqüència.

Exemples:

- Mostrar per pantalla tots els múltiples de 5 menors de 1000.

- Sumar tots els elements d’una seqüència d’enters.

- Mostrar per pantalla les vocals d’una cadena de caràcters.

- ...

L’esquema genèric de recorregut és el següent:

[pic 1]

La darrera línia, tractament_final, és opcional.

ESQUEMA DE CERCA

L’esquema de cerca s’aplica en els problemes on s’ha de determinar si existeix un element en una seqüència que compleixi una propietat donada.

Exemples:

- Comprovar si un nombre és primer.

- Determinar si una seqüència d’enters donada està ordenada de forma   creixent.

- Determinar si en una cadena de caràcters hi ha alguna paraula que comenci per la lletra ’p’.

- ...

L’esquema genèric de cerca és el següent:

[pic 2]

Una altra versió de l’esquema que fa servir una variable booleana per recordar si l’element s’ha trobat, és la següent:

[pic 3]

ORDRE DE PRECEDÈNCIA DELS OPERADORS

[pic 4]

PROBLEMA 1:

[pic 5]

Problema: calcular el factorial d’un enter positiu n. Es tracta d’una cerca o d’un recorregut?

Els elements a tractar (multiplicar) són tots els que hi ha entre 1 i n.

Per tant, estem fent un recorregut.

[pic 6][pic 7]

[pic 8][pic 9]

PROBLEMA 2:

Com que els fluxos de dades tenen una longitud finita però indeterminada, per reconèixer la finalització de la transmissió de les dades és necessari fer servir un element especial anomenat sentinella.

Un sentinella és el darrer element d’un flux de dades i la seva única finalitat és assenyalar el final de la transmissió (de les dades).

Exercici: donada una seqüència (flux) de naturals més grans que zero i acabada en zero, calcular i mostrar per pantalla la seva suma.

[pic 10]

[pic 11]

[pic 12]

[pic 13]

PROBLEMES:

4.10 Donat un enter n i una seqüència de caràcters acabada en un punt, feu un programa que indiqui si hi ha almenys n vocals consecutives. NOTA: Per tal de simplificar la solució d’aquest problema considerarem com a vocals només les vocals de l’alfabet anglès (les vocals sense accents ni dièresis).

Pas 1. Identificació de la seqüència

Atès que és un flux de dades, la identificació de la seqüència és una tasca senzi- lla.

•                 _  primer: e = input()  
•                 _  següent: e = input()  
•                 _  sentinella: e == ’.’, per tant la condició de continuació del bucle és e != ’.’
• Cal tenir present que com la seqüència està formada per caràcters no cal fer conversion
• ja que sempre quan fem input estem llegint caràcters.  
• Pas 2. Esquema de recorregut o cerca?  És un esquema de cerca ja que en el moment
• que trobem n vocals consecutives llavors no cal mirar res més.  

Pas 3. Condició de cerca

Cal anar comptant el nombre de vocals que apareixen a la seqüència. Per això trindrem un variable vocals que incrementarem cada cop que trobem una vo- cal. Però a més si el caràcter actual de la seqüència no és una vocal llavors cal posar a 0 la variable vocals

[pic 14]

Aquesta variable vocals inicialment tindrà el valor de 0 ja que al principi no hem processat cap vocal.

La condició de la cerca és comprovar que la variable locals sigui igual n:

Vocals == n

Pas 4. Tractament trobat i no trobat

Atès que estem fent un programa, com a tractament de trobat i no trobat només cal mostrar per pantalla un missatge indicant si s’ha trobat o no el nombre de vocals consecutives indicat.

Pas 5. Aplicació de l’esquema

[pic 15]

4.13 Dissenyeu un programa que, a partir de les temperatures mínimes enre- gistrades durant un període donat de n dies (que se suposa ≥ 2), numerats de 1 a n, mostri quins han estat els primers dies en què s’enregistraren temperatures mínimes negatives durant dos dies consecutius. En cas que no existeixin, cal indicar-ho.

Exemple:

Dades: n = 7, temperatures = 4.2 1.5 -0.5 -1.8 2.1 -0.8 -1.3 Resultat: 3 i 4 són els primers dos dies consecutius amb temperatures negatives.

Pas 1. Identificació de la seqüència

Atès que és un flux de dades, la identificació de la seqüència hauria de ser sen- zilla, però en aquest cas no hi ha element sentinella sinó que hem de llegir un nombre de temperatures indicat inicialment per l’usuari. Això implica que cal- drà mantenir en una variable i el nombre de temperatures que hem llegit fins a aquest moment.

...