Fonaments de Programació: Seqüències i Taules

Apuntes sobre seqüències i taules en programació, incloent definicions, tractament, exemples i algorismes d'ordenació.

Fonaments de Programació · Universitat Rovira i Virgili · Grado en Ingeniería Biomédica · 1r curs

78 pàgines · 11 temes · 55 flashcards · 55 preguntes tipus test

Índex

  1. 1. Seqüències · p. 3-12
  2. 2. Exemples de Seqüències · p. 13-23
  3. 3. Taules · p. 25-35
  4. 4. Recorregut de Taules · p. 36-37
  5. 5. Inicialització de Taules · p. 39-40
  6. 6. Operacions amb Taules · p. 41-42
  7. 7. Exemples de Taules · p. 43-57
  8. 8. Càrrega de dades d'un fitxer a una taula · p. 59-61
  9. 9. Cadenes de caràcters · p. 63-67
  10. 10. Exemples de Cadenes de caràcters · p. 68-71
  11. 11. Ordenació per selecció · p. 73-78

1. Seqüències

Flashcards

Què és una seqüència en programació?
Una successió d'elements.
Quins dos tipus de solucions hi ha en el tractament de seqüències?
Recorregut de tota la seqüència i cerca d'un element que compleixi una condició.
Què és un sentinella en el context de les seqüències?
Una dada concreta que indica el final de la seqüència.
Què hem de fer sempre quan treballem amb arxius seqüencials?
Comprovar si s'ha pogut obrir l'arxiu.

Preguntes tipus test

  1. Quin tipus de solució implica recórrer tota la seqüència d'elements, tractant-los tots?
    • a) Cerca d'un element.
    • b) Recorregut de la seqüència.
    • c) Ús d'un sentinella.
    • d) Divisió i conquesta.

    Resposta: b) Recorregut de la seqüència.. El recorregut de la seqüència implica visitar cada element, un per un, i aplicar-hi un tractament o operació.

  2. En el tractament de seqüències, quan utilitzem la cerca d'un element que compleix una condició, què passa si cap element compleix aquesta condició?
    • a) El bucle s'atura immediatament.
    • b) Es retorna un error.
    • c) Es recorre tota la seqüència.
    • d) El programa entra en un bucle infinit.

    Resposta: c) Es recorre tota la seqüència.. Si cap element compleix la condició de cerca, el bucle continuarà fins al final de la seqüència, recorrent tots els elements.

  3. Quina és la funció d'un 'sentinella' en el context de les seqüències?
    • a) Indicar l'inici de la seqüència.
    • b) Indicar el final de la seqüència.
    • c) Emmagatzemar el valor mitjà de la seqüència.
    • d) Realitzar operacions matemàtiques complexes.

    Resposta: b) Indicar el final de la seqüència.. El sentinella és un valor específic que marca el final d'una seqüència, permetent que el programa sàpiga quan ha d'aturar-se.

2. Exemples de Seqüències

Flashcards

Què és una seqüència en programació?
Una successió d'elements.
Quins són els dos tipus principals de tractament de seqüències?
Recorregut i cerca.
Què és un sentinella en el context de les seqüències?
Una dada que indica el final de la seqüència.
Quines són les tres maneres de saber quan una seqüència ha finalitzat?
Ús d'un sentinella, saber quants elements hi ha, o detecció del final d'un fitxer.

Preguntes tipus test

  1. Quin dels següents esquemes s'utilitza per recórrer una seqüència del primer a l'últim element?
    • a) Cerca d'un element que compleixi una condició.
    • b) Recorregut de tota la seqüència.
    • c) Ús d'un sentinella per finalitzar la seqüència.
    • d) Comptar el nombre d'elements a la seqüència.

    Resposta: b) Recorregut de tota la seqüència.. L'esquema de recorregut de tota la seqüència implica passar per cada element, des del primer fins a l'últim, i tractar-los tots.

  2. En un recorregut de seqüència amb sentinella, què representa el sentinella?
    • a) El primer element de la seqüència.
    • b) Un element que compleix una condició específica.
    • c) Un element que indica el final de la seqüència i no s'ha de tractar.
    • d) Un element que s'ha de tractar de manera especial.

    Resposta: c) Un element que indica el final de la seqüència i no s'ha de tractar.. El sentinella és una dada concreta que indica el final de la seqüència i no s'inclou en el tractament dels elements.

  3. Quin tipus de bucle és més adequat quan coneixem el nombre exacte d'elements en una seqüència en un recorregut?
    • a) Mentre (while).
    • b) Per (for).
    • c) Repetir fins (repeat until).
    • d) Si (if).

    Resposta: b) Per (for).. El bucle 'per' és ideal quan es coneix el nombre d'iteracions necessàries, ja que permet definir un comptador que s'incrementa automàticament.

3. Taules

Flashcards

Què és una taula (vector)?
Una estructura de dades que emmagatzema una col·lecció d'elements del mateix tipus, accessibles mitjançant un índex.
Com s'accedeix a l'element a la posició 5 d'una taula anomenada 'dades' en pseudocodi?
dades[5]
Quina és la diferència entre la mida màxima i el nombre efectiu d'elements en una taula?
La mida màxima és l'espai total reservat, mentre que el nombre efectiu és la quantitat d'elements amb dades vàlides.
Com s'inicialitza una taula de booleans en C amb els valors 'true, false, true'?
bool taula[3] = {true, false, true};

Preguntes tipus test

  1. Quina és la manera correcta de definir un vector de 10 enters en pseudocodi?
    • a) var vector: taula[10] d'enters fvar
    • b) vector[10]: taula d'enters
    • c) taula vector[10] enters
    • d) var vector: enters[10] fvar

    Resposta: a) var vector: taula[10] d'enters fvar. La sintaxi correcta per definir un vector en pseudocodi és 'var nom_vector: taula[mida] d'enters fvar'.

  2. En llenguatge C, com declares una matriu de 5x5 floats?
    • a) float matriu[5, 5];
    • b) float matriu[5][5];
    • c) matriu float[5][5];
    • d) matriu[5][5] float;

    Resposta: b) float matriu[5][5];. En C, les matrius es declaren especificant la mida de cada dimensió entre claudàtors: 'float matriu[5][5];'.

  3. Si tens una taula 'dades' de 10 enters, quin és l'índex de l'últim element?
    • a) 10
    • b) 1
    • c) 9
    • d) 0

    Resposta: c) 9. En la majoria de llenguatges de programació, els índexs de les taules comencen a 0. Per tant, l'últim element d'una taula de 10 posicions té l'índex 9.

4. Recorregut de Taules

Flashcards

Què és una taula d'una dimensió?
Una estructura de dades que emmagatzema una col·lecció d'elements del mateix tipus en posicions contigües de memòria, accessibles mitjançant un únic índex.
Com s'accedeix a un element específic d'una taula?
Mitjançant el nom de la taula seguit de l'índex de l'element entre claudàtors, per exemple: taula[índex].
Què és una taula de dues dimensions?
Una estructura de dades que emmagatzema elements en files i columnes, accessible mitjançant dos índexs: un per la fila i un altre per la columna.
Com s'inicialitza una taula en C durant la declaració?
Utilitzant claus {} per delimitar la llista de valors inicials dels elements, per exemple: int taula[3] = {1, 2, 3};.

Preguntes tipus test

  1. Quin tipus de bucle és més adequat per recórrer una taula quan coneixem el nombre exacte d'elements?
    • a) Bucle 'mentre'
    • b) Bucle 'per'
    • c) Bucle 'fes...mentre'
    • d) Cap dels anteriors

    Resposta: b) Bucle 'per'. El bucle 'per' és ideal quan es coneix el nombre d'iteracions necessàries, com en el cas de recórrer una taula amb un nombre conegut d'elements.

  2. Què passa si intentem accedir a una posició d'una taula fora dels seus límits definits?
    • a) Es crea una nova posició a la taula.
    • b) El programa es tanca de forma inesperada.
    • c) Es produeix un error en temps d'execució.
    • d) Es retorna un valor per defecte.

    Resposta: c) Es produeix un error en temps d'execució.. Accedir a una posició fora dels límits d'una taula genera un error en temps d'execució, ja que es tenta accedir a una zona de memòria no assignada a la taula.

  3. Quin és l'índex del primer element d'una taula en llenguatge C?
    • a) 1
    • b) 0
    • c) -1
    • d) Depèn de la definició de la taula

    Resposta: b) 0. En llenguatge C, els índexs de les taules comencen a 0. Per tant, el primer element es troba a la posició 0.

5. Inicialització de Taules

Flashcards

Què és un 'sentinella' en el context de les seqüències?
Una dada que indica el final de la seqüència i no s'ha de tractar.
Com s'anomena l'estratègia que consisteix a visitar cada element d'una seqüència per realitzar una operació?
Recorregut de la seqüència.
Quina és la funció de la variable 'n_elems' quan es treballa amb seqüències?
Indica quants elements hi ha a la seqüència.
Com s'inicialitza correctament una taula de 3x3 de booleans en C amb tots els valors a 'false'?
bool tauler[3][3] = {{false, false, false}, {false, false, false}, {false, false, false}};

Preguntes tipus test

  1. Quina és la manera correcta d'inicialitzar una taula de booleans anomenada 'tauler' de 3x3 en C?
    • a) bool tauler[3][3] = {{true, false, false}, {false, true, true}, {false, false, false}};
    • b) tauler = taula[3][3] de booleans {{cert, fals, fals}, {fals, cert, cert}, {fals, fals, fals}};
    • c) int tauler[3][3] = {{1, 0, 0}, {0, 1, 1}, {0, 0, 0}};
    • d) boolean tauler[3][3] = {{true, false, false}, {false, true, true}, {false, false, false}};

    Resposta: a) bool tauler[3][3] = {{true, false, false}, {false, true, true}, {false, false, false}};. La inicialització correcta en C utilitza la paraula clau 'bool' per a booleans i la sintaxi de doble clau per a taules bidimensionals, amb 'true' i 'false' com a valors.

  2. Quin és el resultat d'intentar accedir a taula_edats[10] si taula_edats es defineix com 'var taula_edats: taula[10] d'enters'?
    • a) Es mostrarà el valor emmagatzemat a la posició 10 de la taula.
    • b) Es produirà un error en l'execució, ja que l'índex està fora dels límits de la taula.
    • c) Retornarà el valor per defecte de l'element a la posició 10.
    • d) Es crearà una nova posició a la taula.

    Resposta: b) Es produirà un error en l'execució, ja que l'índex està fora dels límits de la taula.. L'índex d'una taula de 10 elements va de 0 a 9. Accedir a la posició 10 resulta en un error perquè està fora dels límits definits.

  3. Quina és la principal diferència entre 'Recorregut' i 'Cerca' en el tractament de seqüències?
    • a) 'Recorregut' s'utilitza per a fitxers i 'Cerca' per a taules.
    • b) 'Recorregut' processa tots els elements, mentre que 'Cerca' s'atura quan troba un element que compleix una condició.
    • c) 'Recorregut' només funciona amb nombres, i 'Cerca' només amb caràcters.
    • d) 'Recorregut' modifica la seqüència, mentre que 'Cerca' només la llegeix.

    Resposta: b) 'Recorregut' processa tots els elements, mentre que 'Cerca' s'atura quan troba un element que compleix una condició.. 'Recorregut' implica visitar cada element de la seqüència, mentre que 'Cerca' s'atura quan troba l'element desitjat o arriba al final de la seqüència.

6. Operacions amb Taules

Flashcards

Què és una seqüència en programació?
Una successió d'elements.
Quins són els dos tipus principals de tractament de seqüències?
Recorregut i cerca.
Què és un sentinella en el context de les seqüències?
Una dada que indica el final de la seqüència i que no s'ha de tractar.
Com s'anomena una taula d'una dimensió?
Vector.

Preguntes tipus test

  1. Quina és la manera correcta de definir un vector de 30 enters en pseudocodi?
    • a) var taula_edats: taula[30] d'enters
    • b) const taula_edats = taula[30] d'enters
    • c) taula_edats[30]: var d'enters
    • d) taula_edats = taula[30] d'enters

    Resposta: a) var taula_edats: taula[30] d'enters. La sintaxi correcta en pseudocodi per definir un vector és 'var nom_taula: taula[mida] de tipus'.

  2. Quin és l'índex del primer element d'una taula en la majoria de llenguatges de programació, incloent C?
    • a) 1
    • b) 0
    • c) -1
    • d) Depèn del llenguatge

    Resposta: b) 0. En la majoria de llenguatges, com C, el primer element d'una taula té l'índex 0.

  3. Què passa si intentes accedir a taula_edats[10] quan taula_edats es defineix com taula[10] d'enters?
    • a) Es retorna el valor per defecte del tipus enter.
    • b) Es produeix un error en l'execució.
    • c) Es crea una nova posició a la taula.
    • d) Es retorna el valor de la primera posició.

    Resposta: b) Es produeix un error en l'execució.. Accedir a una posició fora dels límits definits per a la taula (en aquest cas, més enllà de l'índex 9) provocarà un error en temps d'execució.

7. Exemples de Taules

Flashcards

Què és una seqüència en programació?
Una successió d'elements.
Com sabem que és el final d'una seqüència?
Mitjançant un sentinella, sabent quants elements hi ha, o amb una funció que indica el final del fitxer.
Què és un sentinella en el context de les seqüències?
Una dada concreta que indica el final de la seqüència.
Quins són els dos tipus principals de tractament de seqüències?
Recorregut i cerca.

Preguntes tipus test

  1. Quina és la principal diferència entre un recorregut i una cerca en una seqüència?
    • a) El recorregut sempre processa tots els elements, mentre que la cerca s'atura quan troba un element que compleix una condició.
    • b) La cerca sempre processa tots els elements, mentre que el recorregut s'atura quan troba un element que compleix una condició.
    • c) El recorregut només funciona amb nombres, mentre que la cerca només funciona amb caràcters.
    • d) La cerca és més eficient que el recorregut.

    Resposta: a) El recorregut sempre processa tots els elements, mentre que la cerca s'atura quan troba un element que compleix una condició.. El recorregut implica examinar cada element de la seqüència, mentre que la cerca s'atura quan troba un element que compleix una condició específica, optimitzant el procés si no cal examinar tota la seqüència.

  2. Quin tipus de bucle és més adequat quan coneixes el nombre exacte d'elements en una seqüència?
    • a) Mentre
    • b) Per
    • c) Repetir
    • d) Si

    Resposta: b) Per. El bucle 'per' és ideal quan es coneix el nombre d'iteracions necessàries, ja que simplifica la gestió del comptador i la condició de finalització.

  3. En el context de les taules, què representa l'índex?
    • a) El valor emmagatzemat a la taula.
    • b) El nombre total d'elements a la taula.
    • c) La posició d'un element dins la taula.
    • d) El tipus de dades que es poden emmagatzemar a la taula.

    Resposta: c) La posició d'un element dins la taula.. L'índex és un indicador de la posició d'un element específic dins de la taula, permetent accedir i manipular aquest element.

8. Càrrega de dades d'un fitxer a una taula

Flashcards

Què és una seqüència en programació?
Una successió ordenada d'elements.
Quin és un exemple d'ús de seqüències en el món real?
Un número de telèfon, el nom d'una ciutat, o les temperatures registrades per un sensor.
Quines són les dues estratègies principals per al tractament de seqüències?
Recorregut complet de la seqüència i cerca d'un element que compleixi una condició.
Com sabem que hem arribat al final d'una seqüència?
Mitjançant un sentinella, sabent el nombre d'elements, o detectant el final d'un fitxer.

Preguntes tipus test

  1. Quina és la principal estratègia per processar seqüències quan necessitem tractar cada element?
    • a) Cerca d'un element específic
    • b) Recorregut de tota la seqüència
    • c) Ús de sentinelles per marcar el final
    • d) Divisió de la seqüència en subseqüències

    Resposta: b) Recorregut de tota la seqüència. El recorregut de tota la seqüència és l'estratègia principal per assegurar que cada element sigui processat, a diferència de la cerca, que s'atura en trobar un element específic.

  2. En el context de les seqüències, què és un 'sentinella'?
    • a) Un element que indica el principi de la seqüència
    • b) Un element que indica el final de la seqüència i no s'ha de tractar
    • c) Un element que conté informació addicional sobre la seqüència
    • d) Un element que es troba al centre de la seqüència

    Resposta: b) Un element que indica el final de la seqüència i no s'ha de tractar. Un sentinella és una dada específica que marca el final d'una seqüència. Aquesta dada és diferent de les altres i no s'ha de processar.

  3. Quina és la principal diferència entre un vector i una matriu?
    • a) Un vector només pot contenir nombres enters, mentre que una matriu pot contenir qualsevol tipus de dada.
    • b) Un vector és unidimensional, mentre que una matriu és bidimensional.
    • c) Un vector és immutable, mentre que una matriu és mutable.
    • d) No hi ha diferència, són sinònims.

    Resposta: b) Un vector és unidimensional, mentre que una matriu és bidimensional.. Un vector és una taula d'una dimensió, mentre que una matriu és una taula de dues dimensions, organitzada en files i columnes.

9. Cadenes de caràcters

Flashcards

Què és una cadena de caràcters en C?
Una seqüència de caràcters acabada amb un caràcter nul ('\0').
Com es declara una cadena de caràcters en C?
Com una taula de tipus char. Exemple: char cadena[50];
Quina funció s'utilitza per llegir una línia sencera d'entrada, incloent espais, en C?
fgets()
Quina funció s'utilitza per llegir una paraula d'entrada en C?
scanf() amb l'especificador %s

Preguntes tipus test

  1. Quin procediment s'utilitza en llenguatge C per llegir una sola paraula del teclat?
    • a) fgets()
    • b) scanf()
    • c) printf()
    • d) gets()

    Resposta: b) scanf(). El procediment scanf() llegeix caràcters fins que troba un espai en blanc, un salt de línia o el final de l'entrada, fent-lo adequat per llegir una sola paraula.

  2. Quin procediment s'utilitza en llenguatge C per llegir una frase sencera del teclat, incloent espais en blanc?
    • a) scanf()
    • b) gets()
    • c) fgets()
    • d) printf()

    Resposta: c) fgets(). El procediment fgets() llegeix una línia sencera d'entrada, incloent els espais en blanc, fins que troba un salt de línia o arriba al nombre màxim de caràcters especificat.

  3. Quin caràcter s'utilitza com a sentinella per marcar el final d'una cadena de caràcters en C?
    • a) '\n'
    • b) '\t'
    • c) '\0'
    • d) '\e'

    Resposta: c) '\0'. El caràcter '\0' (caràcter nul) s'utilitza per indicar el final d'una cadena de caràcters en C. Les funcions que treballen amb cadenes utilitzen aquest caràcter per saber on acaba la cadena.

10. Exemples de Cadenes de caràcters

Flashcards

Què és una seqüència en programació?
Una successió d'elements.
Com sabem que és el final d'una seqüència?
Amb un sentinella, sabent el nombre d'elements, o amb una funció que indica el final d'un fitxer.
Quins són els dos tipus de tractament de seqüències?
Recorregut i cerca.
Com es defineix una taula d'una dimensió en pseudocodi?
var taula_edats: taula[30] d'enters

Preguntes tipus test

  1. Quin tipus de bucle és més adequat quan coneixem el nombre exacte d'iteracions necessàries en una taula?
    • a) Bucle 'mentre'
    • b) Bucle 'per'
    • c) Bucle 'fes...mentre'
    • d) Cap dels anteriors

    Resposta: b) Bucle 'per'. El bucle 'per' és ideal quan coneixem el nombre d'iteracions, ja que facilita la gestió de l'índex i la condició de finalització.

  2. En el context de seqüències, què és un 'sentinella'?
    • a) Un valor que indica el començament de la seqüència
    • b) Un valor que indica el final de la seqüència
    • c) Un valor que s'utilitza per calcular la mitjana de la seqüència
    • d) Un valor que sempre és parell

    Resposta: b) Un valor que indica el final de la seqüència. Un sentinella és un valor específic que marca el final d'una seqüència de dades, permetent que el programa sàpiga quan aturar el processament.

  3. Quina és la principal diferència entre un recorregut i una cerca en una seqüència?
    • a) El recorregut s'utilitza per trobar el valor màxim, mentre que la cerca s'utilitza per trobar el valor mínim
    • b) El recorregut processa tots els elements, mentre que la cerca s'atura quan troba un element que compleix una condició
    • c) El recorregut només funciona amb nombres, mentre que la cerca només funciona amb caràcters
    • d) El recorregut modifica la seqüència, mentre que la cerca no la modifica

    Resposta: b) El recorregut processa tots els elements, mentre que la cerca s'atura quan troba un element que compleix una condició. El recorregut implica visitar cada element de la seqüència, mentre que la cerca s'atura quan es troba un element que satisfà una condició específica.

11. Ordenació per selecció

Flashcards

Què és l'ordenació per selecció?
Un algorisme per ordenar una seqüència trobant repetidament l'element mínim i col·locant-lo al principi.
Quin és el primer pas en l'ordenació per selecció?
Trobar l'element mínim en la seqüència.
Com es compara l'eficiència de l'ordenació per selecció amb altres algorismes d'ordenació?
L'ordenació per selecció no és l'algorisme més eficient, especialment per a conjunts de dades grans.
Quina és la complexitat temporal de l'ordenació per selecció en el pitjor dels casos?
O(n^2), on n és el nombre d'elements.

Preguntes tipus test

  1. Quin és l'objectiu principal de l'ordenació per selecció?
    • a) Eliminar elements duplicats d'una taula.
    • b) Buscar un element específic dins d'una taula.
    • c) Ordenar una seqüència de dades en una taula de manera creixent o decreixent.
    • d) Calcular la mitjana dels valors en una taula.

    Resposta: c) Ordenar una seqüència de dades en una taula de manera creixent o decreixent.. L'ordenació per selecció té com a objectiu principal col·locar els elements d'una seqüència en un ordre específic, ja sigui de manera creixent o decreixent.

  2. Què cal per poder aplicar l'ordenació per selecció a una taula?
    • a) Que els elements de la taula siguin de diferents tipus.
    • b) Que es pugui establir una relació d'ordre entre els elements de la taula.
    • c) Que la taula estigui buida inicialment.
    • d) Que la taula tingui un nombre parell d'elements.

    Resposta: b) Que es pugui establir una relació d'ordre entre els elements de la taula.. Per aplicar l'ordenació per selecció, és essencial que es pugui definir una relació d'ordre (com ara comparacions numèriques o alfabètiques) entre els elements de la taula.

  3. Com funciona l'algorisme d'ordenació per selecció?
    • a) Intercanvia elements aleatoris fins que la taula estigui ordenada.
    • b) Divideix la taula en subtaules més petites i les ordena per separat.
    • c) Troba l'element mínim i l'ubica a la primera posició, repetint el procés per la resta de la taula.
    • d) Compara elements adjacents i els intercanvia si estan en l'ordre incorrecte.

    Resposta: c) Troba l'element mínim i l'ubica a la primera posició, repetint el procés per la resta de la taula.. L'algorisme d'ordenació per selecció busca l'element mínim a cada iteració i el col·loca a la posició correcta, movent-se progressivament per la taula.

I 11 flashcards i 22 preguntes més al document.

Text del document

Fonaments de Programació I T3. Seqüències i taules Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Contingut Seqüències Taules Cadenes de caràcters Ordenació per selecció 2 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Una seqüència és una successió d'elements. Exemples de seqüències: – Un número de telèfon és una seqüència de nombres enters – El nom d'una ciutat és una seqüència de caràcters – Les temperatures que cada minut va obtenint un sensor de temperatura és una seqüència de reals 3 1r 2n 3r 4t 5è 6è 7è …

següent element Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències S'hi poden resoldre multitud de problemes: – Sobre una seqüència de temperatures: -2,5 -1,3 -2,0 -0,5 Calcular la temperatura mitjana, buscar si hi ha temperatures negatives, buscar la temperatura mínima, etc. – Sobre la seqüència que formen els caràcters d'una piulada: Avui estudiem les #seqüències a classe de #programació. Comptar els '#', saber si conté hashtags, passar-la a majúscules, etc. – Sobre les edats dels inscrits a una cursa de muntanya: 30 17 21 31 32 19 21 20 34 27 ... 23 24 21 Comprovar si hi ha algun menor d'edat, comptar quants menors, etc.

4 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Tractament de seqüències, hi ha dos tipus de solucions: 1) Recorregut de tota la seqüència, del primer fins a l'últim. La solució es basarà en un bucle que passarà per tots els elements de la seqüència, tractant-los tots.

Esquema general: 5 Obtenir/accedir primer element de la seqüència mentre (no final_de_seqüència) fer $ fins que no estem a últim element Tractar element $ fem alguna operació amb l'element Obtenir/accedir element següent fmentre si cal Tractar últim element Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Tractament de seqüències 2) Cerca d'un element que compleixi una condició. El bucle aturarà el recorregut quan es trobi aquest element. Esquema general: 6 trobat fals $ el seu valor inicial ha de permetre 1a iteració.

Obtenir/accedir primer element de la seqüència mentre (no final de seqüència i no trobat) fer si (condició_cerca) llavors $ tractem l'element trobat cert sino Obtenir/accedir element següent fsi fmentre si cal Tractar últim element Noteu que si cap dels elements de la seqüència compleix la condició, s'acaba recorrent tota. Aquest booleà no té perquè anomenar-se sempre trobat. Usar un identificador adequat ajudarà a comprendre el programa. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Recorregut o cerca?

– Sobre una seqüència de temperatures: -2,5 -1,3 -2,0 -0,5 Calcular la temperatura mitjana, buscar si hi ha temperatures negatives, buscar la temperatura mínima, etc. – Sobre la seqüència que formen els caràcters d'una piulada: Avui estudiem les #seqüències a classe de #programació. Comptar els '#', saber si conté hashtags, passar-la a majúscules, etc. – Sobre les edats dels inscrits a una cursa de muntanya: 45 17 21 43 43 19 21 21 32 43 ... 23 24 21 Comprovar si hi ha algun menor d'edat, comptar quants menors d'edat hi ha, comptar els majors de 65 anys, etc.

7 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Com sabem que és el final d'una seqüència? Tenim 3 possibilitats: 1) La seqüència finalitza amb una dada concreta anomenada sentinella. És un element que ha de ser diferent de totes les dades de la seqüència, i no s'ha de tractar!! Si apliquéssim un Recorregut: 8 sentinella Obtenir/accedir primer element de la seqüència mentre (element sentinella) fer Tractar element Obtenir/accedir element següent fmentre El sentinella és l'última dada i no es tracta.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Com sabem que és el final d'una seqüència? 2) Sabem quants elements hi ha a la seqüència, per exemple perquè hi ha una variable que ho indica. Si apliquéssim l'esquema d'un Recorregut: 9 n_elems 8 Obtenir/accedir 1er element i 1 $ per comptar quants elements hem accedit mentre (i < n_elems) fer Tractar element Obtenir/accedir element següent i i + 1 fmentre Tractar element $ ens queda tractar l'últim Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Com sabem que és el final d'una seqüència?

– Sabent quants elements hi ha, quan es tracta d'un Recorregut podem usar el bucle 'per'. 10 $ n_elems conté quants elements hi ha $ i compta el nombre d'elements per i 1 fins n_elems fer Obtenir element Tractar element fper Fixa't que ha calgut intercanviar les instruccions del cos del bucle!! Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Com sabem que és el final d'una seqüència? 3) En el cas dels fitxers seqüencials, un procediment ens indica si hem arribat al final del fitxer.

11 fit obrir_fitxer("nom_fitxer","L") si s'obre fitxer correctament llavors $ obtenir/accedir primer element llegir_fitxer(fit, dada) mentre (no final_fitxer(fit)) fer tractar element $ obtenir/accedir al següent element llegir_fitxer(fit, dada) fmentre tancar_fitxer(fit) sino informar de l'error d'obertura fsi … (final de fitxer) (2) (2) (2) (1) (3) (3) (1) (2) Quan treballem amb arxius sempre comprovarem si s'ha pogut obrir l'arxiu!! Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències Podem obtenir seqüències...

– Des d'un fitxer de text, per exemple llegint caràcter a caràcter – Des del teclat, per anar llegint números de la seqüència – Des d'un sensor, per anar obtenint valors de temperatura – etc. Podem tractar els elements a mesura que els obtenim. Ara bé, si volem tractar-los vàries vegades o més endavant, caldrà desar la seqüència en una taula. 12 Més endavant estudiareu el concepte de taules i el seu ús, molt freqüent en programació.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències: exemple 1 Escriure un programa que, donada una seqüència de nombres enters introduïda pel teclat i acabada en -1, indiqui per pantalla quants nombres parells s'han introduït. 13 Estratègia - Recorregut de seqüència amb sentinella final. - Cal un comptador del nombre de parells - Tractament de l'element: si el nombre és parell, incrementar comptador.

Obtenir primer element de la seqüència mentre (element sentinella) fer Tractar element Obtenir següent element fmentre $ Tractar element si (element mod 2 = 0) llavors n_parells n_parells + 1 fsi Esquema de Recorregut amb sentinella: Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 14 Algorisme parells var n, n_parells: enter fvar inici n_parells 0 escriure("Introdueix valors enters i acaba la seq.

amb -1") $ Obtenir primer element escriure("Introdueix valor:") llegir(n) mentre (n - 1) $ Mentre no sigui l'últim $ Tractar element si (n mod 2 = 0) llavors $ nombre parell n_parells n_parells + 1 fsi $ Obtenir element següent escriure("Introdueix valor") llegir(n) fmentre escriure("Has introduit", n_parells,"valors parells") falgorisme Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 15 int main() { int n, n_parells; n_parells = 0; /* Obtenir primer element */ printf("Introdueix valors enters i acaba la seq.

amb -1\n"); scanf("%d", &n); while (n != -1) /* Mentre no sigui sentinella */ { /* Tractar element */ if (n%2 == 0) /* Si es parell */ { n_parells++; } /* Obtenir element següent */ scanf("%d", &n); } /* Fi del while */ printf("Has introduit %d valors parells\n", n_parells); return 0; } Introdueix valors enters i acaba la seq.

amb -1 4 4 3 5 2 3 3 -1 Has introduit 3 valors parells Versió en C a on no es demanen els valors un a un Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències: exemple 2 Escriure un programa que, donada una seqüència de n nombres introduïda pel teclat, on n és un valor que l'usuari també entra pel teclat, indiqui per pantalla quants nombres parells s'han introduït. 16 Estratègia - Recorregut de seqüència coneixent el nombre d'elements. - Cal un comptador del nombre de parells. - Tractament de l'element: si el nombre és parell, incrementar comptador. - Quan acabem, mostrar el resultat per pantalla. ...

n_parells 0 escriure("Quants elements introduiràs?") llegir(n_elems) per i 1 fins n_elems fer escriure("Introdueix valor:") llegir (n) si (n mod 2 = 0) llavors n_parells n_parells + 1 fsi fper ... Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 17 int main() { int n, n_parells, i, n_elems; n_parells = 0; printf("Quants elements introduiras?

"); scanf("%d", &n_elems); printf("\n Introdueix els %d valors \n",n_elems); for (i = 1; i <= n_elems; i++) { /* Obtenir element */ scanf("%d", &n); /* Tractar element */ if (n%2 == 0) /* Si es parell */ { n_parells++; } } printf("Has introduit %d valors parells\n", n_parells); return 0; } Quants elements introduiras? 5 Introdueix els 5 valors 12 21 30 10 2 Has introduit 4 valors parells Compte amb la traducció a C del bucle 'per'!

Una alternativa per aquest cas, i força habitual en llenguatge C seria la següent: for (i=0; i<n_elems; i++) Versió en C a on no es demanen els valors un a un Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències: exemple 3 Escriure un programa que, donada una seqüència de nombres enters introduïda pel teclat acabada amb -1, que representen les notes d'un alumne, indiqui per pantalla si hi ha alguna amb un 10. 18 Estratègia - Cerca en la seqüència amb sentinella. - Tractament de l'element: si trobem el 10 no continuem llegint la resta de notes. - Quan acabem, mostrar el resultat de la cerca per pantalla. ...

$ Obtenir 1er element escriure("Introdueix nota:") llegir(nota) hi_ha10 fals mentre (nota -1 i no hi_ha10) fer si (nota = 10) llavors $ tractem element hi_ha10 cert sino $ Obtenir element següent escriure("Introdueix nota:") llegir(nota) fsi fmentre si (hi_ha10) llavors ... Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 19 int main() { int nota; bool hi_ha10; printf("Introdueix notes i acaba la seq.

amb -1\n"); /* Obtenir primer element */ scanf("%d", &nota); hi_ha10= false; while ((nota != -1) && (!hi_ha10)) /* no final seqüència i no s'hagi trobat*/ { /* Tractar element */ if (nota == 10) /* condició de cerca*/ { hi_ha10= true; } else { /* Obtenir element següent */ scanf("%d", &nota); { } /* Fi del while */ if (hi_ha10) { printf("Hi ha almenys un 10"); } else { printf("No hi ha cap 10"); } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències: exemple 4 Escriure un programa que calculi la mitjana de valors que conté un fitxer de temperatures. 20 Estratègia - Recorregut de seqüència amb final de fitxer.

Cal tractar un possible error d'obertura. - Tenim un sumatori i un comptador, que serviran per calcular la mitjana. - Tractament de l'element: sumem el valor al sumatori. var fit: arxiu; ...

fit obrir_fitxer("nom_fitxer.txt", "L") si no s'obre l'arxiu correctament llavors informar de l'error d'obertura sino $ obtenir/accedir primer element llegir_fitxer(fit,temp) suma 0; cmpt 0 mentre (no final_fitxer(fit)) fer suma suma + temp; cmpt cmpt + 1 $ obtenir/accedir al següent element llegir_fitxer(fit, temp) fmentre tancar_fitxer(fit) mitjana suma / cmpt mostrar_mitjana fsi Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 21 int main() { FILE *fit; /* declarem variable tipus fitxer lògic */ int cmpt; float temp, mitjana, suma; fit = fopen("fitxer.txt", "r"); /* Obrim el fitxer per llegir */ if (fit == NULL) /* comprovem si no s'ha obert correctament */ { printf("Error en obrir el fitxer\n"); } else { cmpt = 0; suma = 0.0; fscanf(fit, "%f", &temp); /* Llegim primera dada */ while (!feof(fit)) /* Mentre no sigui final de fitxer */ { suma = suma + temp; cmpt++; fscanf(fit, "%f", &temp); /*següent dada */ } fclose(fit); /* Tancar fitxer */ mitjana = suma / cmpt; printf("La mitjana es:%f", mitjana); } return 0; } Per tractar fitxers en C FILE tipus de dades per definir el fitxer lògic fopen( ) per obrir el fitxer fclose( ) per tancar el fitxer feof( ) indica si hem arribat al final del fitxer fscanf( ) per llegir una dada d'un fitxer lògic.

Noteu que té una sintaxi similar a scanf( ). A les pràctiques veureu més exemples de tractament de fitxers. El fitxer contindrà un seguit de nombres reals Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Seqüències: exemple 5 Escriure un programa que processa un fitxer d'un control de qualitat. Aquest fitxer conté dades sobre el pes de les peces d'un mateix lot de fabricació (un valor real). Es considera que un lot té qualitat quan totes les peces tenen un pes de 200 gr. amb una tolerància de ±5. El resultat s'ha d'indicar a l'usuari amb un missatge en pantalla. 22 Estratègia - Cerca de seqüència sobre un fitxer.

- Cerquem un pes fora del rang, que farà que el lot ja no tingui qualitat. ... $ obrir fitxer, comprovar error, etc qualitat cert llegir_fitxer(fit, pes) $ obtenir 1er element mentre (no final_fitxer(fit) i qualitat) fer si (pes<195 o pes>205) llavors $ tractem element qualitat fals sino llegir_fitxer(fit, pes) $ obtenir element fsi fmentre ... $ tancar fitxer si (qualitat) llavors escriure ("El lot té qualitat") sino escriure ("El lot no té qualitat") fsi Per simplicitat i perquè ho hem vist en l'exemple anterior, ometem aquí el tractament de l'obertura del fitxer.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 23 int main() { FILE *fit; /* Fitxer logic */ bool qualitat; int pes; fit = fopen("lot.txt", "r"); /* Obrim el fitxer per llegir */ if (fit == NULL) /* comprovem si no s'ha obert correctament */ { printf("Error en obrir el fitxer\n"); } else { qualitat = true; fscanf(fit, "%d", &pes); /* Llegim primera dada */ while (!feof(fit) && qualitat)) /* Mentre no sigui final de fitxer i no trobat */ { if (pes < 195 "" pes > 205) /* tractem dada */ { qualitat = false; } else { fscanf(fit, "%f", &dada); /* Llegim següent dada */ } } fclose(fit); /* Tancar fitxer */ if (qualitat) { printf("El lot te qualitat"); } else { printf("El lot no te qualitat"); } } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Contingut Seqüències Taules Cadenes de caràcters Ordenació per selecció 24 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Les farem servir quan hem de guardar un conjunt de dades del mateix tipus (p.

ex. taula d'enters). Cada dada es desa en una posició o cel·la. – Pel fet que cada dada estigui en una posició, podem veure les dades d'una taula com una seqüència i, per tant, hi podrem aplicar també les estratègies de recorregut i cerca. 25 Taula d'una dimensió (també anomenat vector) Taula de dues dimensions (també anomenada matriu) Podem tenir taules de més dimensions. El nombre de cel·les d'una taula ve donat pel producte de la cardinalitat de cadascuna de les seves dimensions. 21 4 99 99 -7 … 37 9 21 4 99 -10 34 17 Una variable simple es pot interpretar com una taula d'una cel·la!!

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules d'una dimensió – Definició de taules en pseudocodi 26 $ Definició d'un vector de 30 elements com a màxim var taula_edats: taula[30] d'enters fvar $ Si declarem una constant, podrem redefinir la mida de $ vàries taules només canviant el valor de la constant const NUM_PERSONES 30 fconst var taula_edats: taula[NUM_PERSONES] d'enters taula_pesos: taula[NUM_PERSONES] de reals fvar Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules d'una dimensió – Definició de taules en llenguatge C 27 /* Definició d'un vector de 30 elements com a màxim */ int taula_edats[30]; /* Si declarem una constant, podrem redefinir la mida de vàries taules només canviant el valor de la constant */ #define NUM_PERSONES 30 int main() {...

int taula_edats[NUM_PERSONES]; float taula_pesos[NUM_PERSONES]; ... Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules d'una dimensió – La constant (literal o simbòlica) que usem quan definim la taula estableix el nombre màxim d'elements que pot desar la taula. A més, sovint caldrà controlar el nombre efectiu d'elements que conté si la taula no està plena. Per exemple, la següent taula s'ha definit amb una mida de 7 elements, però ara mateix hi ha 4 elements efectius. En la resta de posicions, no sabem quines dades hi ha.

28 En general, definirem el nombre màxim d'elements amb una constant, i el nombre efectiu amb una variable de tipus enter. En determinats llenguatges de programació aquestes estructures es gestionen de forma diferent. En el context d'aquesta assignatura i el llenguatge C ho farem d'aquesta manera. 21 4 99 99 ? ? ? Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules d'una dimensió Per accedir a un element/cel·la cal indicar el nom de la taula i l'índex o posició de l'element: nom_taula[index] L'índex pot ser una constant, o bé una variable o expressió entera. L'índex pot anar de 0 fins a "nombre d'elements menys 1".

Això en determinats llenguatges de programació trobareu que l'índex va d'1 a nombre d'elements. 29 dades[0] dades[29] var dades: taula[30] d'enters El contingut de la taula en la posició 1 és 4, el de la posició 29 és 9... La taula està plena. 21 4 99 99 -7 … 37 9 dades[1] Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules d'una dimensió – Exemples per desar valors en una taula i per accedir als valors que guarden. L'índex pot ser una variable o una constant. 30 var taula_edats: taula[10] d'enters edat, índex, dif: enter fvar ...

índex 5 taula_edats[índex] 40 $ Desem 40 a la 6ena posició índex índex + 1 taula_edats[índex] 12 $ Desem 12 a la 7ena posició dif taula_edats[1]-taula_edats[0] $ faig un càlcul edat taula_edats[10] $ Això donarà un error en l'execució! Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques const N_FRANGES 3; N_DIES 7 fconst var ocup_mitj: taula[N_FRANGES][N_DIES] d'enters fil, col: enters $ índexs per accedir a la taula fvar Taules Taules de dues dimensions – Quan la definim, primer especifiquem el nombre total de files i després el de columnes.

Exemple: taula per desar l'ocupació mitjana d'un restaurant per esmorzar, dinar i sopar, cada dia de la setmana. 31 Nombre total de files Nombre total de columnes Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques #define N_FRANGES 3 #define N_DIES 7 ... main() { int ocup_mitj[N_FRANGES][N_DIES]; ...

Taules Taules de dues dimensions – En llenguatge C 32 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Taules de dues dimensions 33 2 7 5 6 3 12 18 5 12 14 20 18 30 52 2 4 0 7 12 20 6 ocup_mitj[0][0] ocup_mitj[2][6] ocup_mitj[0][6] ocup_mitj[1][6] ocup_mitj[2][0] ocup_mitj[2][3] ocup_mitj[fila][columna] Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques const MAX_FIL 5 $ Nombre total de files MAX_COL 10 $ Nombre total de columnes fconst var dades: taula [MAX_FIL][MAX_COL] d'enters $ Definim la taula n_fil, n_col: enter $ Nombre efectiu de files i columnes Taules Taules de dues dimensions – Com en el cas dels vectors, sovint necessitarem controlar el nombre efectiu de files i columnes, amb variables enteres.

34 2 7 5 6 3 12 ? ? ? ? 5 12 14 20 18 30 ? ? ? ? 2 4 0 7 12 20 ? ? ? ? 6 7 8 9 11 15 ? ? ? ? ? ? ? ? ? ? ? ? ? ? n_fil = 4 n_col = 6 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques #define MAX_FIL 5 /* Nombre total de files */ #define MAX_COL 10 /* Nombre total de columnes */ ...

int dades[MAX_FIL][MAX_COL]; /* Definim la taula */ int n_fil, n_col; /* Nombre efectiu de files i columnes */ Taules Taules de dues dimensions - En llenguatge C 35 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules 36 Recorregut de taules d'una dimensió – Utilitzarem un bucle per recórrer tots els elements de la taula. Com que coneixem quants elements (cel·les amb dades) hi ha a la taula, podem utilitzar un bucle per. – La variable de control ens indexa quin element de la taula tractem, l'índex (normalment l'anomenarem i) i: enter $ index de la cel·la a tractar ...

per i 0 fins número_elements-1 fer $ Tractar cel·la i de la taula fper for (i = 0; i < n_elements; i++) { /* Tractar cel·la i de la taula */ } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules 12 4 19 21 7 43 14 ? ? 5 7 -1 -2 31 0 -5 ? ? 40 12 2 34 -15 8 60 ? ? 32 1 18 -12 43 27 -10 ? ? ? ? ? ? ? ? ? ? ?

bucle "intern" recórrer cada element de la fila bucle "extern" per tractar cada fila Recorregut de taules de dues dimensions – Necessitem dos bucles, un per tractar una fila concreta (tants elements/cel·les com columnes té la taula) i un altre per tractar totes les files Mida màxima de la taula (espai reservat a memòria en la declaració de la taula). El nombre efectiu d'elements pot ser menor com es aquest exemple. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 12 4 19 21 7 43 14 ? ? 5 7 -1 -2 31 0 -5 ? ? 40 12 2 34 -15 8 60 ? ? 32 1 18 -12 43 27 -10 ? ? ? ? ? ? ? ? ? ? ?

Taules 38 fil: enter $ fila a tractar col: enter $ columna a tractar n_fil, n_col: enter $ nombre de files i columnes efectives ... per fil 0 fins n_fil -1 fer per col 0 fins n_col -1 fer $ Tractar cel·la (fil,col) de la taula fper fper 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Ordre en què es recorren les cel·les segons aquests bucles: Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Inicialització de taules – En alguns casos concrets, podríem trobar algorismes que assignen valors als elements de les taules just quan les defineixen.

– En les taules de dues dimensions se sol usar una línia per fila, o bé usar una notació de caire matricial. 39 dies_mes: taula[12] d'enters {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} tauler: taula[3][3] de booleans {{cert, fals, fals}, {fals, cert, cert}, {fals, fals, fals}} cert fals fals tauler: taula de booleans fals cert cert fals fals fals Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Inicialització de taules – Això també ho podem fer en llenguatge C.

40 int dies_mes[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool tauler[3][3] = {{true, false, false}, {false, true, true}, {false, false, false}}; Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Operacions amb taules – Les taules d'elements no es poden comparar, ni assignar amb els operadors que hem vist ( , =, >, ...). És a dir, el següent exemple és incorrecte: 41 var dades, càlculs: taula[MAX_EL] d'enters fvar inici ... si (dades càlculs) llavors dades càlculs fsi Per fer aquestes operacions caldrà fer un algorisme/procediment que ho dugui a terme! NO!

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules Per als exemples i exercicis... En els exemples i exercicis sobre taules de nombres, sovint indicarem que les taules ja tenen les dades carregades.

Suposarem que tenim procediments ad hoc que fan aquesta tasca, per exemple: Procediment que emplena un vector i dona el nombre d'elements efectius: Procediment que emplena un vector i marca el final utilitzant el sentinella -1: Procediment que emplena una matriu i dona el nombre de files i columnes efectives: 42 obtenir_dades_vector(dades, MAX, n_elements) obtenir_dades_senti(dades, MAX,-1) obtenir_dades_matriu(dades, MAXF, MAXC, n_files, n_colum) nom_vector nombre d'elements efectius capacitat vector sentinella nombre files i columnes efectives nom_matriu Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 1 Escriure un programa que calculi la mitjana d'un vector d'enters, dades, carregat amb n_elements i la mostri per pantalla.

43 Estratègia - Aplicar un esquema de recorregut, limitat pel valor de la variable n_elements. - Anar sumant els valors. - En acabar el recorregut dividir la suma pel nombre d'elements (indicat a n_elements). ... $ guardar dades al vector Obtenir_dades_vector(dades, MAX, n_elements) suma 0 $ index a la primera posició de la taula i 0 mentre (i<n_elements) fer suma suma + dades[i] $ index a següent posició de la taula i i + 1 fmentre mitjana suma / n_elements ...

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 44 #define MAX 100 int main() { int suma, n_elements, i, dades[MAX]; float mitjana; obtenir_dades_vector(dades, MAX, &n_elements); /* Obtenir les dades */ suma = 0; i = 0; while (i < n_elements) { suma = suma + dades[i]; i++; } mitjana = suma / n_elements; printf("La mitjana dels valors es %f\n", mitjana); return 0; } Noteu que, en conèixer el nombre d'elements que conté el vector, podem fer servir 'for'.

for (i = 0; i < n_elements; i++) { suma = suma + dades[i]; } Noteu que hem usat un ampersand (&) en la crida al procediment obtenir_dades_vector(dades, MAX, &n_elements); Aquest detall l'aprendreu al proper tema. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 2 Escriure un programa que calculi la mitjana d'un vector, dades, carregat amb enters positius amb el sentinella -1 i la mostri per pantalla. 45 Estratègia - Aplicar un esquema de recorregut, mentre el valor de l'element no sigui el sentinella. - Anar sumant els valors. - En acabar el recorregut dividir la suma pel nombre d'elements, que haurem de comptar. ...

Obtenir_dades_senti(dades, MAX, -1) $ n_elements per saber quants elements s'han sumat n_elements 0; suma 0 $ index a la primera posició de la taula i 0 mentre (dades[i] -1) fer suma suma + dades[i] i i + 1 n_elements n_elements + 1 fmentre mitjana suma / n_elements ... 1ª versió: Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 2 Escriure un programa que calculi la mitjana d'un vector, dades, carregat amb enters positius amb el sentinella -1 i la mostri per pantalla. 46 Estratègia - Noteu que en aquest cas no podem fer servir un bucle 'per'.

- Fixeu-vos, també, que no és necessari anar comptant el número d'elements perquè la variable del bucle (i) ja té aquesta funcionalitat! ... obtenir_dades_senti(dades, MAX, -1) suma 0 $ index a la primera posició de la taula i 0 mentre (dades[i] -1) fer suma suma + dades[i] i i + 1 fmentre mitjana suma / i ...

2ª versió: eliminant la variable n_elements Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 47 #define MAX 100 int main() { int suma, i, dades[MAX]; float mitjana; obtenir_dades_senti(dades, MAX, -1); /* guarda dades al vector*/ suma = 0; i = 0; while (dades[i] != -1) { suma = suma + dades[i]; i++; } mitjana = suma / i; printf("La mitjana dels valors es %f\n", mitjana); return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 3 Escriure un programa que indiqui per pantalla si un vector, dades, carregat amb n_elements enters inclou algun nombre negatiu.

48 Estratègia - Aplicar un esquema de cerca, mentre no trobem el que cerquem ni arribem al final de la seqüència d'elements. - Tanmateix, podem millorar el disseny. ...

Obtenir_dades_vector(dades, MAX, n_elements) trobat fals $ Ubicar-se a la primera posició de la taula i 0 mentre (no trobat i i<n_elements) fer si (dades[i]<0) llavors trobat cert sino i i + 1 fsi fmentre si (trobat) llavors escriure ("El vector conté algun negatiu") sino escriure ("Tots els nombres són positius") fsi Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 3 Escriure un programa que indiqui per pantalla si un vector, dades, carregat amb n_elements enters inclou algun nombre negatiu. 49 Millora - Podem anomenar a la variable booleana hi_ha_negatiu perquè semànticament tingui més sentit.

Així millora la comprensió del programa. ...

Obtenir_dades_vector(dades, MAX, n_elements) hi_ha_negatiu fals $ Ubicar-se a la primera posició de la taula i 0 mentre (no hi_ha_negatiu i i<n_elements) fer si (dades[i]<0) llavors hi_ha_negatiu cert sino i i + 1 fsi fmentre si (hi_ha_negatiu) llavors escriure ("El vector conté algun negatiu") sino escriure ("Tots els nombres són positius") fsi Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 50 #define MAX 100 int main() { int n_elements, i, dades[MAX]; bool hi_ha_negatiu; obtenir_dades_vector (dades, MAX, &n_elements); /* Carreguem les dades */ hi_ha_negatiu = false; i = 0; while (!hi_ha_negatiu && i < n_elements) { if (dades[i]<0) { hi_ha_negatiu = true; } else { i++; } } if (hi_ha_negatiu) /* Mostrem el resultat per pantalla */ { printf("El vector conte algun negatiu\n"); } else { printf("Tots els nombres son positius\n"); } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 4 Escriure un programa que indiqui per pantalla si un vector, dades, carregat amb n_elements està ordenat de forma creixent.

51 Estratègia - Fem una cerca sobre la seqüència però en aquest cas en lloc de tractar un element necessitem dos: un element i el següent. - Cal anar en compte amb els límits del bucle! - Si dades[i]>dades[i+1] la seqüència no està ordenada de forma creixent. ...

Obtenir_dades_vector(dades, MAX, n_elements) ordenat cert $ Ubicar-se a la primera posició de la taula i 0 mentre (ordenat i i < n_elements-1) fer si (dades[i] > dades[i+1]) llavors ordenat fals sino i i + 1 fsi fmentre si (ordenat) llavors escriure ("El vector està ordenat") sino escriure ("El vector no està ordenat") fsi Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 52 #define MAX 100 int main() { int n_elements, i, dades[MAX]; bool ordenat; obtenir_dades_vector(dades, MAX, &n_elements); /* Carreguem les dades */ ordenat = cert; i = 0; while (ordenat && i < n_elements-1) { if (dades[i] > dades[i+1]) { ordenat = false; } else { i++; } } if (ordenat) /* Mostrem el resultat per pantalla */ { printf("El vector esta ordenat\n"); } else { printf("El vector no esta ordenat\n"); } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 5 Escriure un programa que trobi el valor mínim dels elements d'una matriu, dades, que conté n_fil files i n_col columnes d'enters, i el mostri per pantalla.

53 Estratègia - Per trobar el mínim cal fer un recorregut de la taula. Necessitarem dos bucles 'per' imbricats. - Tractar l'element es correspon amb comparar l'element amb el valor mínim que hàgim trobat fins aleshores. Si l'element és menor que el mínim, l'actualitzem. ...

Obtenir_dades_matriu(dades,MAXF,MAXC,n_fil,n_col) $ El valor inicial del mínim és el valor de la primera cel·la de la taula min dades[0][0] per i 0 fins n_fil-1 fer per j 0 fins n_col-1 fer si (dades[i][j]< min) llavors min dades[i][j] fsi fper fper escriure ("El valor mínim de la taula és ", min) Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 54 #define NFIL 50 #define NCOL 50 int main() { int min, i, j, n_fil, n_col, dades[NFIL][NCOL]; obtenir_dades_matriu(dades,NFIL,NCOL,&n_fil,&n_col); /* Carreguem les */ /* dades */ min = dades[0][0]; /* Assignem el valor inicial al minim */ for (i = 0; i < n_fil; i++) { for (j = 0; j < n_col; j++) { /* Si escau, actualitzem */ if (dades[i][j] < min) { min = dades[i][j]; } } } printf("El valor minim de la taula es %d\n", min); return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 6 Escriure un programa que indiqui per pantalla si en una taula, dades, que conté n_fil x n_col enters, hi ha algun valor negatiu.

55 Estratègia - Haurem d'usar el bucle 'mentre' perquè estem fent una cerca. - Adaptem l'esquema de cerca amb un bucle als dos bucles imbricats. ...

Obtenir_dades_matriu(dades,MAXF,MAXC,n_fil,n_col) hi_ha_negatiu fals $ Ubicar-se a la primera posició de la taula i 0 mentre (no hi_ha_negatiu i i<n_fil) fer j 0 mentre (no hi_ha_negatiu i j<n_col) fer si (dades[i][j] < 0) llavors hi_ha_negatiu cert sino j j + 1 fsi fmentre si (no hi_ha_negatiu) llavors i i + 1 fsi fmentre si (hi_ha_negatiu) llavors escriure ("El vector conté algun negatiu") sino escriure ("Tots els nombres són positius") fsi Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 56 #define MAXF 50 #define MAXC 50 int main() { int n_elements, i, dades[MAXF][MAXC]; bool hi_ha_negatiu; obtenir_dades_matriu(dades, MAXF, MAXC, &n_fil, &n_col); /* Carreguem les dades */ hi_ha_negatiu = false; i = 0; while (!hi_ha_negatiu && i < n_fil) { j = 0; while (!hi_ha_negatiu && j < n_col) { if (dades[i] < 0) { hi_ha_negatiu = true; } else { j++; } } if (!hi_ha_negatiu) { i++; } } if (hi_ha_negatiu) /* Mostrem el resultat per pantalla */ { printf("El vector conte algun negatiu\n"); } else { printf("Tots els nombres son positius\n"); } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 7 Escriure un programa que indiqui per pantalla si dues matrius amb el mateix nombre d'elements enters (taula1, taula2) són iguals o no.

57 Estratègia - Fem una cerca, on el que busquem és la situació on taula1[i][j] taula2[i][j]. - Necessitem dos bucles 'mentre' imbricats. ...

Obtenir_dades_matriu(taula1,MAXF,MAXC,n_fil,n_col) Obtenir_dades_matriu(taula2,MAXF,MAXC,n_fil,n_col) iguals cert i 0 mentre (iguals i i<n_fil) fer j 0 mentre (iguals i j<n_col) fer si (taula1[i][j] taula2[i][j]) llavors iguals fals sino j j + 1 fsi fmentre si (iguals) llavors i i + 1 fsi fmentre $ mostrar resultat Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 58 #define MAXF 50 #define MAXC 50 int main() { int n_elements, i, taula1[MAXF][MAXC], taula2[MAXF][MAXC]; bool iguals; obtenir_dades_matriu (taula1, MAXF, MAXC, &n_fil, &n_col); /* Carreguem les dades */ obtenir_dades_matriu (taula2, MAXF, MAXC, &n_fil, &n_col); /* Carreguem les dades */ iguals = true; i = 0; while (iguals && i < n_fil) { j = 0; while (iguals && j < n_col) { if (taula1[i][j] != taula2[i][j]) { iguals = false; } else { i++; } } if (iguals) { j++; } } if (iguals) /* Mostrem el resultat per pantalla */ { printf("Les taules són iguals\n"); } else { printf("Les taules no són iguals\n"); } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Taules: exemple 8 Escriure un codi que carregui les dades d'un fitxer a una taula d'enters, de mida màxima MAX_F, MAX_C.

El fitxer comença amb dos enters: un indica el número de files i el segon el número de columnes de la taula. 59 Estratègia - Primer cal llegir el número de files i de columnes, i comprovar que les dades del fitxer càpiguen a la taula. - Després anem llegint seqüencialment el fitxer i recorrent la taula amb dos bucles. 6 4 18 -45 38 21 0 -7 12 13 0 0 5 78 -3 56 34 -22 18 0 1 12 14 41 23 -8 18 -45 38 21 … ? 0 -7 12 13 … ? 0 0 5 78 … ? -3 56 34 -22 … ? 18 0 1 12 … ? 14 41 23 -8 … ? … … … … … … ? ? ? ? ? ?

Exemple MAX_F = 100, MAX_C = 10 Nombre de files Nombre de columnes 0 9 0 99 Per aquest exemple senzill, suposem que el nombre de files i columnes mai superaran el màxim i que, a més, sempre hi haurà dades al fitxer. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 60 var fit: arxiu; .... $ obrim fitxer i comprovar error fit obrir_fitxer("nom_fitxer.txt", "L") si fit = NULL llavors $ no s'obre l'arxiu correctament $ informar de l'error d'obertura ...

sino llegir_fitxer(fit, n_files) $ Llegim el nombre de files llegir_fitxer(fit, n_cols) $ Llegim el nombre de columnes $ no cal tenir en compte el final de fitxer, ja sabem el nombre de dades per i 0 fins n_files-1 fer per j 0 fins n_cols-1 fer llegir_fitxer(fit, dades[i][j]) $ Llegim dada i la desem a la taula fper fper tancar_fitxer(fit) fsi ...

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 61 #define MAX_F 100 #define MAX_C 10 int main() { FILE *fit; /* Fitxer logic */ int n_files, n_cols, i, j, dades[MAX_F][MAX_C]; fit = fopen("dades.txt", "r"); /* Obrim el fitxer "dades.txt" per llegir-lo */ if (fit == NULL) { printf("Error en obrir el fitxer\n"); } else { fscanf(fit, "%d %d", &n_files, &n_cols); /* Llegir el nombre de files i columnes */ /* Aquí no cal tenir en compte el final de fitxer, ja sabem el nombre de dades */ for (i=0; i < n_files; i++) { for (j=0; j < n_cols; j++) { fscanf(fit, "%d", &dades[i][j]); /* Llegim la dada i la desem a la taula */ } } fclose(fit); /* Tancar fitxer */ } return 0; } Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Contingut Seqüències Taules Cadenes de caràcters Ordenació per selecció 62 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters També anomenades taules de caràcters.

Es una estructura de dades per guardar seqüències de caràcters, com ara paraules i frases. – Els llenguatges de programació fan diferents aproximacions a la cadena de caràcters. – En el marc d'aquesta assignatura (i també en llenguatge C) les veurem com una taula de caràcters on el final de la cadena es marca amb el sentinella '\0', que es correspon al caràcter amb codi (ASCII) 0. 63 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters Exemple: – Definim una taula de caràcters de mida 50 per desar un nom. – Llegim la cadena de caràcters amb el procediment llegir i el mostrem per pantalla amb escriure.

64 'A' 'd' 'a' ' ' 'L' 'o' 'v' 'e' 'l' 'a' 'c' 'e' '\0' … ? nom: taula[50] de caràcters ... escriure ("Com et dius?") llegir(nom) escriure ("Hola, ", nom) La 4a posició de la cadena, nom[3], conté un espai en blanc. La cel·la 12 conté el sentinella '\0'. De la posició 13 a la 49 no sabem quin és el contingut de la taula. Com et dius? Ada Lovelace Hola, Ada Lovelace No es pot fer servir llegir per llegir un conjunt de nombres!! nom Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters Entrada pel teclat en llenguatge C Hi ha dues maneres de fer-ho: - Si hem d'introduir una paraula, usem el procediment scanf( ).

Vegeu l'exemple, on només es llegeix la paraula "Ada". 65 char nom [50]; ... printf("Com et dius?\n"); scanf("%s", nom); printf("Hola, %s\n", nom); scanf llegeix com a cadena tots els caràcters fins trobar un espai en blanc (o un salt de línia). Noteu que en aquesta crida a scanf no hi posem l'ampersand! Com et dius? Ada Lovelace Hola, Ada Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters Entrada pel teclat en llenguatge C – Si hem d'introduir una frase, usem el procediment fgets ( ) La frase sempre acaba amb un salt de línia(tecla Intro) ! 66 char nom [50]; ...

printf("Com et dius?\n"); fgets(nom, 50, stdin); printf("Hola, %s\n", nom); Com et dius? Ada Lovelace Hola, Ada Lovelace fgets(taula de caràcters, MIDA_MAX, stdin); Què succeeix si l'usuari introdueix més caràcters que els que hi caben a la cadena? Sobre l'algorisme, que és a nivell descriptiu, no passa res. Sobre un programa, en segons quin entorn, es podrien sobreescriure altres zones de memòria i arribar a plantejar problemes d'inestabilitat o seguretat. L'avantatge d'usar fgets ( ) és que si l'usuari introdueix més caràcters que els que caben a la cadena, el text es trunca.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters Al voltant del sentinella... – En l'exemple de "Ada Lovelace" scanf( ) agafa la primera paraula i acaba la cadena amb el sentinella \0. – Ara bé, tot i que fgets( ) agafarà tota la frase, abans del sentinella afegirà el caràcter del salt \n 67 'A' 'd' 'a' \0 ? ? ? ? ? ? ? ? ? ? … ? 'A' 'd' 'a' ' ' 'L' 'o' 'v' 'e' 'l' 'a' 'c' 'e' '\n' '\0' … ? Aquest és un aspecte que caldrà tenir en compte a l'hora de tractar la cadena de caràcters. Tanmateix, en molts escenaris se'ns especificarà que el text acaba en un caràcter com ara el punt, que al capdavall, farà de sentinella.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters: exemple 1 Escriure un programa que compti el nombre de vocals d'una frase acabada en punt. La frase és en minúscules i no conté ni accents ni dièresis. 68 Estratègia - Desem la frase en una cadena de caràcters - Cal fer un recorregut sobre la cadena de caràcters amb sentinella '.' - Al tractar cada element, si es tracta d'una vocal incrementarem un comptador. ... i 0 mentre (frase[i] '.') fer Tractar element i i + 1 fmentre $ mostrar resultat ...

$ Tractar element, si (frase[i]='a' o frase[i]='e' o frase[i]='i' o frase[i]='o' o frase[i]='u') llavors n_vocals n_vocals + 1 fsi cal inicialitzar comptador abans del bucle!

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 69 #define MAX 100 int main() { char frase[MAX]; int i, n_vocals; printf("Introdueix una frase acabada en punt\n"); fgets (frase, MAX, stdin); n_vocals = 0; i = 0; while (frase[i] != '.') /* El punt es el sentinella*/ { if (frase[i] == 'a'"" /* Si es vocal */ frase[i] == 'e' "" frase[i] == 'i' "" frase[i] == 'o' "" frase[i] == 'u') { n_vocals++; } i++; } /* Fi de while */ printf("La frase te %d vocals.\n", n_vocals); return 0; } Introdueix una frase que acabi en punt el nen menja una poma. La frase te 8 vocals Noteu que si la frase no acaba en punt el programa no funcionarà correctament.

És una precondició de funcionament del programa. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Cadenes de caràcters: exemple 2 Escriure un programa que indiqui si una paraula conté el diftong "ai". La paraula és en minúscules i no conté ni accents ni dièresis. 70 Estratègia - Cal fer una cerca sobre una cadena de caràcters que contindrà la paraula. - Hem d'analitzar la subseqüència formada per una lletra i l'anterior. Per tant, haurem d'anar en compte en posicionar-nos pels elements de la cadena. ...

i 1; diftong fals mentre (paraula[i] '\0' i no diftong) fer si (paraula[i-1] = 'a' i paraula[i] = 'i') llavors diftong cert sino i i + 1 fsi fmentre 'a' 'i' 'r' 'e' '\0' ? ? … ?

Comparem un caràcter amb l'anterior Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques 71 #define MAX 100 int main() { char paraula[MAX]; int i; bool diftong; printf("Introdueix una paraula\n"); scanf("%s", paraula); i = 1; diftong = false; while (paraula[i] != '\0' && !diftong) { if (paraula[i-1] == 'a' && paraula[i] == 'i') { diftong = true; } else { i++; } } /* Fi de while */ if (diftong) { printf("La paraula te diftong ai.\n"); } else { printf("La paraula no te diftong ai.\n"); } return 0; } Introdueix una paraula aigua La paraula te diftong ai Fixeu-vos que si la paraula només té una lletra, també funciona.

Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Contingut Seqüències Taules Cadenes de caràcters Ordenació per selecció 72 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció Una de les operacions més habituals que cal fer amb les taules és l'ordenació del seu contingut. – Cal que es pugui establir una relació d'ordre entre els elements de la seqüència emmagatzemada a la taula. Per exemple, si són números tenim els operadors de comparació. Si tenim lletres, gràcies a llur codificació a números preservant l'ordre alfabètic també les podem ordenar.

– Cal decidir si s'ordena de forma creixent: 71 192 324 512 1009 1011 1755 1981... – o decreixent. 73 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció Algorismes d'ordenació – Ordenen dades, per exemple, ubicades en un vector. – Com més dades hi hagi i més desordenades estiguin, més es trigarà a ordenar. – En aquesta assignatura, introductòria, estudiarem l'algorisme d'ordenació per selecció, un algorisme que és força evident i senzill d'entendre. 74 Els algorismes d'ordenació són "un clàssic" de l'algorísmica: l'art de resoldre problemes per mitjà d'algorismes.

Hi ha diferents maneres d'ordenar seqüències, algunes de més eficients que d'altres. Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció Objectiu: Ordenar la seqüència, emmagatzemada en un vector, de manera creixent. 75 Estratègia: - Cerquem l'element mínim de la seqüència i l'ubiquem en la primera posició, intercanviant les dades. - Cerquem l'element més petit de la part no ordenada de la seqüència i l'ubiquem en la segona posició... - ...I així successivament, fins tenir tota la seqüència ordenada.

5 8 2 7 10 9 11 n_elems - 1 0 Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció Objectiu: Ordenar la seqüència, emmagatzemada en un vector, de manera creixent. 76 5 8 2 7 10 9 11 n_elems - 1 0 Comencem en la primera posició (i=0). La variable j s'usa per buscar el mínim, del qual en guardarem tant el valor (min) com la posició dins la seqüència (pos_min). Cerquem el mínim: Assignació inicial, min 5, pos_min 0 Cerquem en la resta del vector (j.. n_elems-1): 8 < min? no, llavors avancem j; 2 < min? sí, llavors min 2, avancem j; ...

seguim fins que fins que j = n_elems – 1 Haurem trobat el mínim (2) i el tindrem localitzat (pos_min = 2) j i Calen dos índexs: i, per la cel·la que volem ordenar j, per recórrer la taula no ordenada Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció Objectiu: Ordenar la seqüència, emmagatzemada en un vector, de manera creixent. 77 Intercanviem les dades: posarem el mínim a la primera posició i l'element que hi havia a la primera posició (el 5) el posarem a la posició pos_min, on teníem el mínim. La primera posició ja està ordenada!! Repetim el procés actualitzant els índexs.

2 8 5 7 10 9 11 pos_min 5 8 2 7 10 9 11 n_elems - 1 0 i i j Un cop trobat el mínim: Fonaments de Programació I – Seqüències i taules Departament d'Enginyeria Informàtica i Matemàtiques Ordenació per selecció (vector d'enters) 78 algorisme ordena_seqüència const MAX_ELEMS 20 fconst var seq: taula [MAX_ELEMS] d'enters i, j, min, n_elems, pos_min: enters fvar inici obtenir_dades_vector(seq,MAX_ELEMS,n_elems)$ guardem les dades al vector i 0 mentre (i < n_elems - 1) fer $ càlcul del mínim min seq[i]; pos_min i j i + 1 mentre (j < n_elems) fer si (seq[j] < min) llavors min seq[j]; pos_min j fsi j j + 1 fmentre seq[pos_min] seq[i] seq[i] min $ Ubiquem el mínim i i + 1 fmentre falgorisme 5 8 2 7 10 9 La implementació en llenguatge C d'aquest algorisme es veurà, si escau, en el context dels laboratoris.

Exàmens, temes i apunts de Fonaments de Programació