introducciÓ a la programaciÓ€¦ · web viewintroducciÓ a la programaciÓ material extret de...

INTRODUCCIÓ A LA PROGRAMACIÓMATERIAL EXTRET DE FONAMENTS DE PROGRAMACIÓ I DE LA UOC

ITEE25-04-11

Introducció a la programació

ÍNDEX

TEMA 1. INTRODUCCIÓ A LA PROGRAMACIÓ

1. CONCEPTES BÀSICS:................................................................................................................................ 41.1. DEFINICIONS........................................................................................................................................ 41.2 ALGORISMES:....................................................................................................................................... 5

2. LA PROGRAMACIÓ COM A UNA DISCIPLINA D’ENGINYERIA................................................................62.1 ETAPES EN EL DESENVOLUPAMENT D’UN PROGRAMA.................................................................7

2.1.1 DEFINICIÓ DEL PROBLEMA. ANÀLISI DE REQUERIMENTS......................................................72.1.2. DISSENY DE L’ALGORISME.........................................................................................................72.1.3 IMPLEMENTACIÓ DEL PROGRAMA.............................................................................................72.1.4 PROVES.......................................................................................................................................... 72.1.5 OPERACIÓ, MILLORES I MANTENIMENT.....................................................................................82.2. CONCLUSIONS I MOTIVACIONS.....................................................................................................8

3. INTRODUCCIÓ A L’ALGORÍSMICA............................................................................................................93.1 ETAPES DEL DISSENY D’UN ALGORISME.........................................................................................9

3.1.1 ENTENDRE EL PROBLEMA...........................................................................................................9

TEMA 2. LLENGUATGE ALGORÍSMIC O PSEUDO-CODI

1. OBJECTES ELEMENTALS DEL LLENGUATGE ALGORÍSMIC................................................................111.1 TIPUS ELEMENTALS..........................................................................................................................11

1.1.1 TIPUS BOOLEÀ............................................................................................................................. 121.1.2 TIPUS CARÀCTER........................................................................................................................ 131.1.3 TIPUS ENTER............................................................................................................................... 141.1.4 TIPUS REAL.................................................................................................................................. 15

1.2 DECLARACIÓ D’OBJECTES...............................................................................................................161.3 EXPRESSIONS.................................................................................................................................... 17

1.3.1 SINTAXI I SEMÀNTICA................................................................................................................. 171.3.2 AVALUACIÓ.................................................................................................................................. 18

1. 4 DEFINICIÓ DE TIPUS. TIPUS ENUMERATIUS..................................................................................191.5 FUNCIONS DE CONVERSIÓ DE TIPUS.............................................................................................20

2. ESPECIFICACIÓ D’ALGORISMES............................................................................................................212.1 ALGORISME I CANVI D’ESTAT...........................................................................................................212.2. QUE VOL DIR ESPECIFICAR?...........................................................................................................222.3 ELEMENTS DE L'ESPECIFICACIÓ.....................................................................................................232.4 ESPECIFICACIÓ I COMENTARIS.......................................................................................................242.5 EXEMPLES D’ESPECIFICACIÓ..........................................................................................................25

2.5.1 INTERCANVI DE DUES VARIABLES...........................................................................................252.5.2 ARREL QUADRADA......................................................................................................................25

2.5.3 ARREL QUADRADA ENTERA..........................................................................................................252.5.4 QUOCIENT I RESIDU...................................................................................................................262.5.5 NOMBRE DE DIVISORS...............................................................................................................26

3. ESTRUCTURES ALGORÍSMIQUES..........................................................................................................263.1 ESTRUCTURA GENERAL D’UN ALGORISME...................................................................................263.2 ACCIONS ELEMENTALS.....................................................................................................................27

3.2.1 L’ASSIGNACIÓ.............................................................................................................................. 28

Pag 2 de 45


3.3 COMPOSICIÓ D’ACCIONS.................................................................................................................. 293.2 COMPOSICIÓ ALTERNATIVA.............................................................................................................31

3.3.3 COMPOSICIÓ ITERATIVA............................................................................................................33

4. ACCIONS I FUNCIONS.............................................................................................................................. 364.1 ACCIONS............................................................................................................................................. 364.2 PARÀMETRES..................................................................................................................................... 384.3 FUNCIONS........................................................................................................................................... 414.4 ACCIONS I FUNCIONS PREDEFINIDES............................................................................................43

4.4.1 FUNCIONS DE CONVERSIÓ DE TIPUS......................................................................................434.4.2. ACCIONS I FUNCIONS D’ENTRADA I SORTIDA DE DADES....................................................43

RESUM................................................................................................................................................... 45

Pag 3 de 45


TEMA 1. INTRODUCCIÓ A LA PROGRAMACIÓ

La finalitat bàsica de la programació és solucionar problemes mitjançant l’ordinador. L’aprenentatge ha de ser progressiu: primer cal aprendre a resoldre problemes senzills a partir d’un conjunt d’eines bàsiques, per a més endavant resoldre problemes més complexos que requereixen més temps.

1. CONCEPTES BÀSICS:

1.1. DEFINICIONS

ALGORISME: es defineix com una descripció no ambigua i precisa de les accions que cal fer per a resoldre un problema ben definit en un temps finit.Un algorisme és un procediment de càlcul que consisteix a acomplir un seguit ordenat i finit d'instruccions que condueix, un cop especificades les dades, a la solució que el problema genèric en qüestió té per a les dades considerades.

Un algorisme és un mètode GENERAL per a resoldre TOTS ELS CASOS POSSIBLES del mateix problema, i per tant, ha de ser independent de les dades d’entrada de qualsevol cas concret.

L’ENTORN és el conjunt d’objectes necessaris per a portar a terme una tasca determinada.

L’ESTAT DE L’ENTORN en un moment determinat és la descripció de l’estat dels objectes de l’entorn en aquell moment concret. Un algorisme actua de manera que fa canviar progressivament l’estat del seu entorn.

(exemple d’entorn i estat: en el cas d’una recepta de cuina, l’entorn vindria donat pels estris de cuina -olles, paelles, etc- i els ingredients. L’estat de les paelles, per exemple, canviarà de netes a brutes)

Una ACCIÓ és un esdeveniment finit en el temps i que té un efecte definit i previst. Una acció pot actuar sobre un entorn i el pot modificar, es a dir, es parteix d'un estat inicial i s'arriba a un estat final diferent.

Una ACCIÓ ELEMENTAL és una acció que el destinatari d’un algorisme entén i sap processar.

Un PROCÉS és l’execució d’una o diverses accions. L’algorisme expressa unes pautes que cal seguir per a portar a terme una tasca concreta. L’encarregat de dur a terme aquesta tasca és el processador.

Un PROCESSADOR és una entitat capaç de comprendre i executar eficaçment un algorisme. El destinatari de l’algorisme és, doncs, el processador.

(Un processador pot ser una persona, una rentadora, un ordinador, etc)

LLENGUATGE ALGORÍSMIC O NOTACIÓ ALGORISMICA: un llenguatge que ens permeti fer una descripció no ambigua i precisa de les accions que componen els nostres algorismes.

Pag 4 de 45


ORDINADOR: es pot definir fonamentalment com una màquina formada per circuits electrònics que té la capacitat de resoldre problemes sota el control d’unes instruccions donades. Un ordinador està format bàsicament per un processador, la memòria i els dispositius d’entrada i sortida que permeten la seva comunicació amb l’exterior.

LLENGUATGE DE PROGRAMACIÓ: un llenguatge capaç de ser comprès per un ordinador.(exemples: Pascal, C, C++, Cobol, Fortran, VisualBasic, Java, etc)

PROGRAMA: codificació d’un algorisme en un llenguatge que l’ordinador entén.

LLENGUATGES IMPERATIUS O PROCEDIMENTALS I LLENGUATGES DECLARATIUS: Bàsicament hi ha dos tipus de llenguatges de programació, els imperatius i els declaratius, que a la vegada es divideixen en llenguatges funcionals i llenguatges lògics.

En la PROGRAMACIÓ IMPERATIVA, els programes són seqüències d’instruccions que s’han de dur a terme com una recepta o guió per a resoldre un problema determinat.

(exemples de lenguatges imperatius:Pascal, Cobol, C, Javascript, PHP...exemples de llenguatges declaratius: HTML, CSSfuncionals: Lisplògics: Prolog

tipus de llenguatges de programaci ó

** programació orientada a objectes POO, cada vegada pren més i més rellevància.esquema llenguatges programació

1.2 ALGORISMES:

exemple: algorisme d’una rentadora que renta roba blanca:

● agafar aigua i sabó del calaix● escalfar l’aigua a 40 graus.● donar voltes durant 20 minuts (rentar)● expulsar l’aigua● agafar més aigua● donar voltes durant 10 minuts (primera esbandida)● expulsar l’aigua

…● donar voltes durant 10 minuts (quarta esbandida)● expulsar l’aigua● donar voltes molt ràpidament durant 1 minut (centrifugat)

Si es demanés que es rentés la roba delicada, l’algorisme seria diferent (temperatura inferior, temps rentat més curt, menys esbandides, etc), equivalent a un altra algorisme.

Es important veure que hi pot haver més d’un algorisme que resolgui el mateix problema, com també algun problema per al qual no hi hagi cap algorisme que el resolgui.

Pag 5 de 45

http://babel.ls.fi.upm.es/teaching/prog_decl/Material/Slides/sesion1.pdf



http://www.monografias.com/trabajos38/tipos-lenguajes-programacion/tipos-lenguajes-programacion.shtml






Fixar-se també que cal que es compleixin unes condicions inicials perquè el problema es resolgui correctament (que la roba blanca estigui dins la rentadora, que la rentadora estigui connectada al corrent elèctric i a l’entrada d’aigua, que hi hagi sabó al calaixet). Per tal d’arribar a l’ESTAT FINAL desitjat, l’entorn hauria d’estar en aquest ESTAT INICIAL.

Amb l’ordinador, exemple:que ens calculi la mitjana de quatre nombres enters determinats.

Un algorisme en llenguatge natural podria ser: “Sumeu els quatre números que ens han donat i dividiu el resultat d’aquesta suma per quatre per a obtenir-ne el resultat final”

en llenguatge algorísmic:

algorisme mitjanavar

n, suma, i: enter;resultat: real;

fvar

suma := 0;i := 1;mentre i <= 4 fer

llegirEnter(n);suma := suma + n;i := i + 1;

fmentreresultat := enterAReal(suma) / 4.0;escriureReal(resultat);

falgorisme

2. LA PROGRAMACIÓ COM A UNA DISCIPLINA D’ENGINYERIA

Actualment, la programació es considera una disciplina que, igual que altres disciplines d’enginyeria, es fonamenta en una teoria, una proposta metodològica i un conjunt de tècniques de disseny.

Cada una d’aquestes parts de la disciplina ha sorgit de la recerca i l’expèriencia adquirides en els darrers anys i contribueix a fer que la progamació sigui una tasca eficaç (doni els resultats esperats) i eficient (en un temps de desenvolupament raonable).

En un entorn industrial competitiu, l’eficàcia i l’eficiència son valors molt apreciats. Per aconseguir-ho s’ha de practicar molt!

2.1 ETAPES EN EL DESENVOLUPAMENT D’UN PROGRAMA

1. Definició del problema. Anàlisi de requeriments2. Disseny de l’algorisme

Pag 6 de 45


3. Implementació del programa4. Proves5. Operació, millores i manteniment

Després de l’etapa de proves, ja es té un programa disponible per a començar a operar-hi. Pero com a resultat de la seva explotació i maneniment, és possible que calgui fer-hi millores o canvis, modificacions que generalment provoquen haver de retrocedir a algunes etapes prèvies del desenvolupament.

Per motius d’eficiència, és desitjable que el desenvolupament de cadascuna de les etapes s’efectuï de manera seqüencial en el temps i que cap etapa obligui a retrocedir a l’anterior (excepte com s’ha dit, la darrera).

2.1.1 DEFINICIÓ DEL PROBLEMA. ANÀLISI DE REQUERIMENTS.

Un o diversos clients plantegen un problema que necessita una solució mitjançant la construcció d’un programa. D’entrada, cal fer una anàlisi del problema, que pot ser laboriosa, ja que a vegades el problema és difícil de comprendre. Un cop s’ha aclarit el problema, es fa una anàlisi minuciosa dels requeriments que ajudaran a definir el problema que volem resoldre.

El resultat de l’etapa de definició del problema i anàlisi de requeriments serà un enunciat precís i clar del problema que cal resoldre.

2.1.2. DISSENY DE L’ALGORISME.

A partir de l’enunciat hem de fer un disseny que ens porti a la solució desitjada.

La representació del disseny es farà mitjançant el llenguatge algorísmic explicat properament (pseudo-codi).

Aquesta es una de les etapes més importants i costoses dins el desenvolupament d’un programa.

2.1.3 IMPLEMENTACIÓ DEL PROGRAMA

Implementar vol dir portar a terme. El resultat del disseny és un algorisme, però per a executar-lo, caldrà traduir el disseny a un llenguatge de programació.

Podrem traduir sense cap dificultat els llenguatges de programació imperatius qualsevol disseny que hàgim fet en llenguatge algorísmic.

2.1.4 PROVES

En l’etapa de proves es tracta de provar el programa resultant amb diferents dades d’entrada que reben el nom de jocs de proves. L’èxit d’aquestes proves dependrà en gran mesura de la qualitat del disseny fet abans.

Pag 7 de 45


Tenir en compte que els jocs de proves només serveixen per a comprovar que el programa no és correcte (si algun joc de proves no dóna el resultat esperat), però no per a assegurar que sí ho és (llevat que es comprovin totes les entrades possibles, pràcticament impossible)

Existeixen mètodes formals de verificació que permeten demostrar la correctesa d’un algorisme -i per tant del programa corresponent- a partir de l’especificació formal dels seus requeriments. D’aquesta manera es podria afirmar amb tota seguretat que el programa compleix els seus objectius.

La seguretat en la correctesa ens vindrà donada per les dues etapes a) disseny -la més estratègica- i b) implementació i prova amb un joc de proves exhaustiu (per exemple, que es verifiqui els casos estranys o extrems) -la de confirmació.

La millor manera d’assegurar que el programa és correcte es estar-ne convençuts de la correctesa en l’etapa de disseny.

2.1.5 OPERACIÓ, MILLORES I MANTENIMENT

Els programes canvien per a millorar o adaptar-se a noves necessitats. Si la nova millora obliga a modificar parts del programa o si, per qüestions de manteniment, s’hi han de fer correccions, això només es pot dur a terme amb eficiència si el disseny del programa es fa de manera intel·ligible.

Un programa s’escriu una vegada, però es llegeix moltes més. Convé fer dissenys clars, comprensibles i senzills perquè ajudin a fer que aquesta etapa sigui eficient i eficaç.

El disseny també haurà d’estar ben documentat. Caldrà aprendre a documentar bé els programes i saber distingir entre una documentació bona i una que no aporta res.

2.2. CONCLUSIONS I MOTIVACIONS

Les etapes anteriors tenen costos molt diferents:

1. L’anàlisi de requeriments és una de les més costoses, ja que depèn de molts factors entre els quals, a més del purament tècnics, es troben els sociòlogics i econòmics.

2. L’etapa de disseny és costosa i cal dedicar-hi tots els esforços que calgui, atès que de la qualitat del disseny dependrà el cost i l’èxit de la resta d’etapes.

3. L’etapa d’implementació és actualment la menys costosa de tot el desenvolupament, atès que és una traducció força directa.

Si les anteriors etapes s'han fet correctament, per exemple si és el client que et proporciona l'etapa 1 i després el desenvolupador l'ha de modificar, corregir o completar, el disseny i la implementació es veuran endarrerits.

Conèixer perfectament un llenguatge de programació no vol dir saber programar, es conèixer l’eina a partir de la qual podrem implementar el disseny del programa.

Pag 8 de 45


4. El cost de l’etapa de proves depèn de la complexitat que tingui el programa i del fet que les anteriors etapes s’hagin fet bé.

Tenir present que en algunes aplicacions com l’hospitalària o la informàtica de control d’una central nuclear, els errors poden tenir efectes dramàtics.

3. INTRODUCCIÓ A L’ALGORÍSMICA

Un algorisme adient serà aquell que presenti les característiques següents:

a. Correctesa: l’algorisme fa allò que realment es demana.b. Intel·ligibilitat: l’algorisme ha de ser clar i fàcil d’entendre, cara al manteniment i modificacions.c. Eficiència: ha de portar a terme la tasca en un temps raonable.d. Generalitat: amb pocs canvis, s’ha de poder adaptar a altres enunciats semblants.

3.1 ETAPES DEL DISSENY D’UN ALGORISME

1. Entendre el problema. L’especificació formal dels algorismes és una bona eina per a assolir aquesta etapa rigorosament i evitar ambigüitats.

2. Plantejar/planificar la solució: la metodologia proposada (bàsicament els esquemes de recorregut i cerca i l’anàlisi descendent) permetrà efectuar de manera eficient i amb eficàcia aquesta etapa i alhora facilitarà la resta d’etapes.

3. Formular la solució: el pseudo-codi ens permetrà definir l’algorisme amb precisió i sense ambigüitats

4. Avaluar la correcció de la solució proposada: la intel·ligibilitat de l’algorisme junt amb l’aplicació dels esquemes permetrà estar gairebé segurs de la correcció de l’algorisme. L’especificació (precondicions, postcondicions) també ajudarà a raonar sobre la seva correctesa.

3.1.1 ENTENDRE EL PROBLEMA

Cal saber què es demana i de quin estat inicial es parteix. En aquesta etapa, es pretén ordenar les idees, identificar quines son les condicions inicials (precondició), i a partir d’aquí, establir l’objectiu que es vol assolir (postcondició)

No es pot permetre cap ambigüitat. L’especificació consistirà precisament en això.

L’algorisme ha de solucionar estrictament el que volem, ni més ni menys.

No cal preocupar-se ara de com es farà, sinó de què s’ha de fer, què hi ha inicialment, i què es vol obtenir.

Exemple d’especificació de problema:

Pag 9 de 45


L’objectiu d’una rentadora es rentar la roba que s’ha introduït. Per assolir aquest objectiu cal que estigui connectada al corrent i al subministrament d’aigua.

(...)

Glossari:

algorisme: conjunt explicit de regles per a resoldre un problema en un nombre finit de passos.

codificació: traducció d’un algorisme a un llenguatge de programació.

computador: autòmat de càlcul governat per un programa.

entorn: conjunt d’objectes necessaris per a dur a terme una tasca determinada.

especificació: formalització de l’enunciat d’un problema.

estat: descripció de l’entorn en un moment determinat.

implementació: realització d’un projecte.

llenguatge algorísmic: llenguatge artificial que es fa servir per a expressar algorismes.

llenguatge natural: qualsevol llenguatge que es fa servir com a forma natural de comunicació (català, castellà, anglès, etc)

llenguatge de programació: llenguatge creat per a expressar programes i que es capaç de ser interpretat per un ordinador.

notació algorísmica: veure llenguatge algorísmic.

ordinador: veure computador.

programa: codificació d’un algorisme en un llenguatge de programació que l’ordinador entengui.

sintaxi: regles d’estructura d’un llenguatge.

semàntica: significat dels símbols d’un llenguatge.

TEMA 2. LLENGUATGE ALGORÍSMIC O PSEUDO-CODI

Necessitem definir un llenguatge que disposi d’una sintaxi reduïda, simple i precisa que permeti d’expressar algorismes sense ambigüitats i amb la claredat i precisió necessàries per tal que puguin ser interpretats per qualsevol processador sense pressuposar cap coneixement previ per la seva part.

Aquest llenguatge teòric dóna prou genericitat perquè es pugui fer servir per a descriure qualsevol tipus d’algorisme sense haver de preocupar-se de la seva posterior codificació en un entorn concret.

Pag 10 de 45


La metodologia següent no està lligada a cap llenguatge concret i permet codificar fàcilment els dissenys en qualsevol dels llenguatges de programació estructurada que hi ha al mercat, només aprenent les particularitats del llenguatge en concret.

1. OBJECTES ELEMENTALS DEL LLENGUATGE ALGORÍSMIC.

Sense saber com dissenyar algorismes, es pot saber que es tractarà amb dades. Es necessitarà referenciar aquestes dades d’alguna manera i explicitar quins comportaments s’espera d’elles. L’objecte serà el suport per mantenir les dades de que tracti un algorisme.

Un objecte té tres atributs:

● nom o identificador. Permet identificar unívocament l’objecte.

● tipus. Indica el conjunt de valors que pot tenir i quines operacions s’hi poden aplicar.

● valor. Serà un element del conjunt al qual pertany i que ve indicat pel seu tipus. Hi haurà objectes en que el seu valor podrà ser canviat per un altre del mateix tipus, es a dir que es pot modificar al llarg del temps d’execució de l’algorisme.

(exemple: l’objecte semàfor amb un tipus que només accepta els valors verd, vermell, groc i apagat. El valor de l’objecte semàfor en algun moment donat serà vermell, en un altre instant verd, etc. En canvi, l’objecte senyal de trànsit, com el de direcció prohibida tindrà sempre un valor constant dins el tipus de valors indicadors de senyals de trànsit)

Per tant un objecte podrà ser constant: el seu valor no és modificablevariable: el seu valor es pot modificar.

1.1 TIPUS ELEMENTALS.

booleà, caràcter, enter i real. Són els tipus que té inicialment el llenguatge per declarar els nostres objectes. Més endavant es veurà que es poden definir tipus particulars.

Per descriure cada tipus, s’exposarà l’identificador o nom amb que el llenguatge el reconeix, quins son els valors que pot prendre, quines operacions admet, i quina es la sintaxi reconeguda pel llenguatge dels seus valors.

1.1.1 TIPUS BOOLEÀ.

És un dels més utilitzats i el seu origen està en l’àlgebra de Boole. En molts casos, els seus dos valors serveixen per a representar la certesa o falsedat d’un estat concret de l’entorn. També se l’anomena tipus lògic.

El llenguatge algorísmic el reconeix mitjançant l’identificador booleà. Nomes té dos valors possibles: cert i fals. El llenguatge algorísmic reconeixerà les paraules cert i fals com els valors booleans. Les operacions internes (aquelles que tornen un valor del mateix tipus) són no (negació), i (conjunció), o (disjunció).

Pag 11 de 45


Els operadors lògics no, i, o es defineixen mitjançant la taula següent:

a b no a a i b a o b

cert cert fals cert cert

cert fals fals fals cert

fals cert cert fals cert

fals fals cert fals fals

Característiques del tipus booleà:

identificador booleà

rang de valors cert, fals

operadors interns no, i, o, =, ≠, <, ≤, <, ≥

operadors externs

sintaxi de valors cert, fals

OPERADORS RELACIONALS =, ≠, <, ≤, <, ≥

(Poden operar també sobre altres tipus). S’apliquen a dos operands del mateix tipus. A més, els operadors <, ≤, <, ≥ només es poden aplicar si el tipus té una relació d’ordre. Per conveni, en el tipus booleà es té el següent:fals < certAixí, fals < cert és una operació que dóna com a valor cert. L’operació cert = fals dóna el valor de fals, etc.

Taula pels operadors =, <, >

a b a = b a < b a > b

cert cert cert fals fals

cert fals fals fals cert

fals cert fals cert fals

fals fals cert fals fals

I les expressions següents cobriran la resta de casos que es poden trobar amb els operadors relacionals:

a ≠ b és equivalent a no(a=b)Pag 12 de 45


a ≥ b és equivalent a (a>b) o (a=b)a ≥ b és equivalent a (a<b) o (a=b)

EXERCISI 4

1.1.2 TIPUS CARÀCTER

És el tipus més elemental perquè un algorisme pugui gestionar informació simbòlica.

L’identificador del tipus es caracter. La sintaxi que reconeix el llenguatge algorísmic dels seus valors és el mateix caràcter delimitat per cometes simples. Per exemple ‘e’ és el valor de caràcter corresponent a la lletra “e”, ‘=’ és el valor corresponent al símbol d’igual, i ‘ ‘ és el caràcter corresponent a l’espai.

El rang de valors que pot tenir aquest tipus depèn de la codificació utilitzada pel computador. En tot cas, serà un conjunt finit de valors.

Dins aquest conjunt de caràcters hi ha definida una relació d’ordre. Això permet aplicar els operadors relacionals que seran externs al conjunt. En el cas dels caràcters que representen les lletres que coneixem, l’ordre segueix un criteri alfabètic: el valor de l’operació ‘a’ < ‘b’ és cert, ‘z’ < ‘a’ fals. ‘A’ = ‘a’ fals. ‘0’ < ‘5’ cert.

També hi ha un ordre entre conjunts de caràcters que correspon a un conveni de la codificació utilitzada per a representar els caràcters (codificació ASCII -que satisfà el mon angles- té 128 valors i és una de les més utilitzades arreu del mon. A Europa té àmplia difusió el codi iso-latin de 256 caràcters. I altres, com Unicode, que recull la majoria d’alfabets existents.). En el cas de fer servir l’ASCII, les minúscules sempre són més grans que les majúscules, i les majúscules més grans que els caràcters dígits.

Característiques del tipus caràcter:

identificador caràcter

rang de valors conjunt finit de valors que depenen d’un codi usat pel computador

operadors interns

operadors externs =, ≠, <, ≤, <, ≥

sintaxi de valors exemples: ‘a’, ‘W’, ‘1’. Observar que el caràcter ‘1’ no té res a veure amb el número 1.

1.1.3 TIPUS ENTER

Pag 13 de 45


En programació s’haurà de distingir els enters dels reals, com a dos conjunts diferents que no tenen cap relació. Això es degut a la representació interna de cada tipus.(nota: JavaScript NO fa aquesta distinció, però convé conèixer-la)

El tipus enter s’identifica amb el nom reservat enter. Com els ordinadors tenen memòria finita, no es podrà tenir tots els enters que es vulguin, sinó un subconjunt finit que estarà limitat per un enter mínim ENTERMIN i un enter màxim ENTERMAX. Els valors ENTERMIN i ENTERMAX dependran del computador que es faci servir. La sintaxi dels valors vindrà donada pel seguit de xifres que representa el valor enter precedit del signe menys (-) quan l’enter és negatiu. Així, 4, 4876 i -10 són enters. ‘5’ no és un enter sinó el caràcter ‘5’. Les operacions internes que es poden fer amb els enter són el canvi de signe (-), la suma (+), la resta (-), el producte (*), la divisió entera (div), i la resta de la divisió o mòdul (mod).

Les operacions div i mod són les que poden resultar més estranyes. Exemples:

8 div 4 = 2. 7 div 2 = 3 3 div 8 = 0

8 mod 4 = 0 7 mod 2 = 1 3 mod 8 = 3

Les operacions div i mod estan definides pel teorema de la divisió entera d’Euclides:Per tot dividend positiu i divisor positiu i diferent de 0, l’equació

dividend = divisor * quocient + restaté un únic valor de quocient i un únic valor de resta, si la resta compleix que es més gran o igual que 0, i a la vegada més petita que el divisor (0 ≤ resta < divisor).I aquests valors únics són quocient = dividend div divisor i resta = dividend mod divisor.

La divisió entera per 0 produirà un error.

Característiques del tipus enter:

identificador enter

rang de valors des de ENTERMIN fins ENTERMAX

operadors interns - (canvi signe), +, -, *, div, mod

operadors externs Relacionals: =, ≠, <, ≤, <, ≥

sintaxi de valors exemples: 3, 465454, -899993

1.1.4 TIPUS REAL

De la mateixa manera que els enters, està limitat per uns valors mínims i màxims (REALMIN i REALMAX). Aquests valors dependran de la representació interna del computador. A mes, només es poden representar un nombre finit de valors del rang. Pensar que entre dos nombres reals qualsevol, hi ha un nombre infinit de reals, i l’ordinador es finit.

Pag 14 de 45


Com que només es pot representar un conjunt finit de reals, els programes que treballen amb reals estan sotmesos a problemes de precisió i errors en els càlculs.

Els reals comparteixen amb els enters els símbols d’operadors +, -, * (suma, resta i producte). Malgrat la coincidència de símbols, cal que es considerin els símbols com operacions diferents de les que s’apliquen als enters, en el sentit que, per exemple, la suma de reals donarà un resultat enter, mentre que la suma d’enters donarà un resultat enter. També tenen l’operació de divisió (/). Fixar-se que la divisió per 0 produeix error.

La sintaxi de valors es fa mitjançant una successió de dígits on apareix el caràcter ”.” per a denotar la coma decimal (49.22, 0.5, 0.0001, 2.0)

Per a representar “10 elevat a” alguna cosa ,es farà servir el caràcter E. Per exemple 5.0E-8 correspon a 5*10-8 o 0.00000005.

Observar que la sintaxi de reals difereix de la d’enters per la presencia del punt. Així, si es veu escrit “5” es sap que és un enter, “5.0” un real. El computador el tractarà diferent.

Característiques del tipus real:

identificador real

rang de valors des de REALMIN fins REALMAX i no pas tots els valors que estan en el rang

operadors interns - (canvi signe), +, -, *, /

operadors externs Relacionals: =, ≠, <, ≤, <, ≥

sintaxi de valors exemples: 0.6, 5.0E-8, -49.22E+8, 1.0E5, 4.0

1.2 DECLARACIÓ D’OBJECTES

Abans que un algorisme faci servir un objecte, cal que aquest s’hagi declarat prèviament.

Si l’objecte és constant, s’ha de declarar dins un apartat afitat per les paraules clau const … fconst. Si és un objecte variable es declararà dins un apartat afitat var … fvar.

En el cas d’un objecte constant, s’ha d’escriure el seu nom, el seu tipus i el valor constant:const

nom:tipus = valor;fconst

En el cas que l’objecte sigui variable, la declaració pren la forma:var

nom:tipus;fvar

En l’identificador nom cal que el primer caràcter sigui sempre un caràcter alfabètic. La resta de caràcters que segueixen poden ser alfabètics, numèrics o el caràcter “_”. No hi pot haver espai entre caràcters.

Pag 15 de 45


Per exemple, els noms 1xl, Josep-Maria són incorrectes. xl1 i Josep_Maria són correctes.

En el cas de variables del mateix tipus, es poden declarar d’aquesta manera:var

nom1, nom2, nom3, …:tipus;fvar

Hi ha una serie de paraules que delimiten les parts de l’algorisme, anomenades paraules clau, i ajuden a identificar fàcilment amb què es correspon cada cosa. Són paraules reservades del llenguatge algorísmic, i no es poden fer servir com a nom d’objectes (constants o variables).

Hi ha una excepció: i. Tot i que és un operador lògic (i per tant com a operador del llenguatge, paraula reservada), s’accepta la possibilitat de definir una variable amb el nom i, que habitualment s’utilitza com a variable entera, especialment com a índex d’una taula.

Exemples:

constPI:real = 3.1415926535897932;ARREL_2:real = 1.4142135623730950;ln2:real = 0.6931471805599453;diesSetmana:enter = 7;separador:caracter = “-”;

fconst

varsaldo, preu, nombreArticles:enter;diametreCercle:real;caracterLlegit:caracter;

fvar

EXERCISI 2

1.3 EXPRESSIONS

Al escriure algorismes haurà la necessitat d’operar entre els diversos objectes declarats pel nostre entorn de treball per a obtenir algun valor concret. Es farà mitjançant les expressions.Una expressió és qualsevol combinació d’operadors i operands.

Un operand pot ser una variable, una constant o una expressió. Els operadors poden ser unaris o binaris. Un operador unari és aquell que només opera amb un operand (negació lògica i el signe menys aplicat a un número). Un operador binari és aquell que opera amb dos operands (suma, resta)

Perquè una expressió ens sigui útil, cal que aquesta segueixi unes regles sintàctiques i que es respecti el significat dels símbols utilitzats: ha de ser correcta en sintaxi i semàntica.

Pag 16 de 45


1.3.1 SINTAXI I SEMÀNTICA

SINTAXI:Una expressió correcta i per tant avaluable, ha de seguir les regles de combinació següents:

● Un valor és una expressió● Una variable és una expressió● Una constant és una expressió● Si E és una expressió, (E) també ho és.● Si E és una expressió i ● és un operador unari, ●E també ho és (expressió)● Si E1 i E2 són expressions i ● un operador binari, E1 ● E2 també és una expressió● Si E1, E2, E3, … , En són expressions i f és una funció, f(E1, E2, …, En) també és una

expressió.

Les expressions s’escriuen linealitzades, es a dir, d’esquerra a dreta i de dalt cap a baix.

Per exemple, per a a, b, c, d, e enters, ab− x e equival a (a div b) div (c div e) * ecd

SEMÀNTICA:Cal respectar la tipificació de variables, constants, operadors i funcions. Per exemple, si es troba un operador suma aplicat a variables booleanes, l’expressió pot ser correcta sintàcticament però no semànticament (la suma no està definida per a booleans). 4.0 + 7 no és correcte per que barreja dos tipus de dades diferents.

EXERCISI 1

1.3.2 AVALUACIÓ

L’avaluació d’una expressió es fa d’esquerra a dreta començant per les funcions i allò que estigui entre els parèntesis més interns. Dins el parèntesis, s’avaluaran primer les operacions més prioritàries.

Una constant s’avaluarà en el valor descrit en la seva definició. Una variable s’avaluarà en el valor que guarda en el moment què s’avalua.

Les prioritats dels operadors (de major a menor prioritat) són:

1. -(canvi de signe), no2. *, /, div, mod

Pag 17 de 45


3. +, - (resta), 4. =, ≠, <, ≤, <, ≥ 5. i6. o

A igualtat de prioritats, s’avalua d’esquerra a dreta.

Exemples:

1) c div d * e = (c div d) * e

2) 3 * 1 div 3 = (3 * 1) div 3 = 1

3) 3 * (1 div 3) = 0

4) (a * b) - ((c + d) div a) mod (2 * a):1. a * b2. c + d3. (c + d) div a4. 2 * a5. el valor del pas 3 mod el valor del pas 46. el valor del pas 1 - el valor del pas 5

5) a + b = a * b div c:1. a * d2. valor pas 1 div c3. a + b4. valor pas 2 = valor pas 3. El resultat d’avaluar aquesta expressió és un booleà.

6) a > b = c:1. a > b2. valor pas 1 = c. Resultat un booleà

7) a * b > c + d o e < f:1. a * b2. c + d3. valor pas 1 > valor pas 24. e < f5. valor pas 3 o valor pas 4. Resultat un booleà.

8) no a = b i c ≥ d1. no a2. valor pas 1 = b3. c ≥ d4. valor pas 2 i valor pas 3. Resultat un booleà.

EXERCISI 3

Pag 18 de 45


1. 4 DEFINICIÓ DE TIPUS. TIPUS ENUMERATIUS

La notació algorísmica permet definir tipus nous per a poder treballar amb objectes que siguin més propers al problema que s’estigui tractant, amb el constructor de tipus.

El constructor de tipus per enumeració permet de definir un tipus nou de manera que els valors possibles que pugui tenir s’enumeren en la mateixa definició del tipus.

La sintaxi és:

tipusnom = { valor1, valor2, … , valorn}

ftipus

Els únics operadors que es poden aplicar als tipus enumeratius són els operadors relacionals externs. L’ordre en què s’enumeren els valors és el que es fa servir per establir les relacions de més petit a més gran.

tipuscolor = {verd, blau, vermell, groc, magenta, cian, negre, blanc};dia = {dilluns, dimarts, dimecres, dijous, divendres, dissabte, diumenge};

ftipus

L’expressió dimarts < diumenge tornarà el valor cert.

1.5 FUNCIONS DE CONVERSIÓ DE TIPUS

A vegades caldrà passar d’un tipus de valor a un altre tipus. Es disposa d’unes funcions predefinides:

● realAEnter: accepta un argument de tipus real i el converteix al tipus enter. El nou valor resultant perd tots els decimals que pugui tenir el valor real.

exemples: realAEnter(4.5768) = 4realAEnter(-3.99) = -3

● enterAReal: accepta un argument de tipus enter i el converteix al tipus real.exemple:

enterAReal(6) = 6.0

● caracterACodi: accepta un argument de tipus caràcter i el converteix al tipus enter. L’enter té a veure amb la codificació que el caràcter té internament en el computador.

exemples:caracterACodi(‘A’) = 65 (si utilitzem la codificació ASCII)caracterACodi(‘A’) = 193 (si utilitzem la codificació EBCDIC)

Pag 19 de 45


● codiACaracter: accepta un argument del tipus enter i el converteix al tipus caràcter. L’efecte de la funció està limitat a un subconjunt del tipus enter que té a veure amb la codificació de caràcters que utilitza el computador: no té un efecte definit per a aquells enters que no corresponguin a un codi de caràcter. Per exemple, en la codificació ASCII utilitzada en els PC, el subconjunt d’enters és l’interval [0, 127].

exemples:codiACaracter(10) = salt de líniacodiACaracter(48) = “O”

(ASCII és només per al cas de l’idioma anglès, per a altres idiomes hi ha una extensió de l’ASCII que va de 128 a 255, però no del tot difosa i a més, canvia d’acord amb l’idioma que es vulgui utilitzar -francès, espanyol, etc-)

2. ESPECIFICACIÓ D’ALGORISMES.

2.1 ALGORISME I CANVI D’ESTAT

Un algorisme és una descripció d’un mètode sistemàtic per a resoldre un problema. La manera com un algorisme resol un problema forma part de l’algorisme mateix, però en tot cas, la resolució del problema s’aconseguix si s’actua sobre l’entorn en què està inmers l’algorisme, i es modifica convenientment.

Per exemple, una rentadora disposa d’un metode sistemàtic per a rentar roba: es pot concloure que disposa d’un algorisme per a rentar la roba (vist tema1).

Quin és l’entorn sobre el qual actua la rentadora? -d’una manera simplificada- es pot dir que és la roba que hi ha a dins la cubeta de la rentadora.

Com hi actua? (el procés descrit en tema1). El que importa ara és que inicialment la roba està bruta i després d’aplicar l’algorisme de rentat, està neta.

Hi ha hagut un canvi d’estat de l’entorn sobre el qual actua la rentadora. L’estat inicial = roba bruta, estat final = roba neta.

Aquest canvi entre l’estat inicial i l’estat final no s’ha de produir de cop necessàriament. L’algorisme per rentar la roba vist al tema1 és l’execució d’un seguit d’accions. Cadascuna d’aquestes accions modifica l’estat d’alguna manera determinada: entre l’estat inicial i final pot haver molts estats intermedis.

Pag 20 de 45


En primer lloc la rentadora omple la seva cubeta d’aigua barrejada amb sabo, i la roba passa d’estar bruta a estar bruta i en remull amb aigua i sabó. Després la cubeta es mou durant vint minuts, que fa que la brutícia que hi ha a la roba passi en gran part a estar a l’aigua. Després dels vint minuts la roba està més neta i l’aigua més bruta. Etc. Totes aquestes accions produeixen canvis d’estat sobre l’entorn que, si ens baséssim en l’estat immediatament anterior, ens anirien acostant cap a l’estat final desitjat.

L’entorn d’un algorisme és el conjunt d’objectes que intervenen en aquest. Al tema1 s’ha vist amb quins objectes treballa el llenguatge algorísmic. De tots aquests, els únics objectes que L'execució d'un algorisme podrà modificar són les variables: un procés (l’execució d’un algorisme) únicament pot modificar l’entorn si canvia el valor de les variables que hi en aquest.

Per això es diu que l’estat en un moment determinat de l’execució d’un algorisme ve donat pel valor de les variables que hi intervenen.

2.2. QUE VOL DIR ESPECIFICAR?

El primer pas en la construcció d’un algorisme consisteix a saber clarament què és el que es vol resoldre. D’aquesta manera es pot dissenyar un algorisme que el resolgui, i això es fa mitjançant l’especificació.

Especificar consisteix a donar informacio necessària i suficient per a definir el problema a resoldre de la manera més clara, concisa i no ambigua possible.

S’ha de distingir clarament entre especificació i algorisme:● L’especificació ens diu quin és el problema● L’algorisme ens diu com resoldre el problema.

S’ha de donar una descripció clara, concisa i no ambigua de:

● l’estat inicial en què es troba l’entorn i del qual partim

● l’estat final de l’entorn al qual hem d’arribar per a resoldre el problema.

La descripció de l’estat inicial s’anomena precondició i la de l’estat final, postcondició.

L’algorisme és com una caixa negra que, a partir d’un estat inicial determinat per la precondició, obté l’estat final descrit a la postcondició. Quan s’especifica un problema, importen únicament els estats inicials i finals, i no tot el conjunt d’estats intermedis pels quals es passa. Es més, atesa una especificació d’un problema, hi pot haver més d’un algorisme que solucioni el problema.

Pag 21 de 45


S’ha de tenir clar què forma part de què s’ha de resoldre i què forma part de com es resol. A vegades no és tan facil decidir què ha de contenir l’especificació d’un algorisme.

En principi, es poden seguir les indicacions seguents:

● En la precondició descriure tot allò que tingui a veure amb les condicions en les quals l’algorisme ha de poder resoldre el problema.

● En la postcondició posar tot allò que es vol obtenir, el resultat de l’algorisme. Pràcticament sempre s’haurà d’expressar la postcondició en termes de què hi ha a la precondició (relacionar l’estat final amb l’esta inicial).

Seguint amb l’exemple de la rentadora, si es posa en marxa i la roba està apilada al costat, l’algorisme s’executarà igualment però quan hagi acabat la roba continuarà apilada i bruta.

Hi ha certes condicions que l’estat inicial ha de complir perquè l’algorisme funcioni. Es podria tenir per exemple la precondició:

{Pre: la roba és a dins la rentadora i la rentadora està connectada al subministrament de llum i d’aigua. A més, el caixonet destinat al sabó és ple de sabó}

Si a més es vol que surti suau, s’hauria d’afegir “el caixonet destinat al suavitzant és ple de suavitzant”.Si alguna de les condicions de la precondició no es compleix, es pot posar en marxa la rentadora però no tenir cap garantia que la roba es renti.

En la descripcio de l’estat final, s’haurà de dir que la roba inicialment bruta a la cubeta ara està neta. No n’hi ha prou de dir que la roba que hi dins la rentadora està neta, s’ha de dir que “la roba és la mateixa que hi havia a l’estat inicial”. En cas contrari, fixar-se en l’algorisme seguent:

“Obrir la porta de la rentadora. Agafar la roba bruta i tirar-la per la finestra. Anar a l’armari, agafar roba neta. Si no queda, anar a la botiga a comprar-ne. Posar aquesta roba dins la rentadora. Tancar la porta de la rentadora.”

Aquest algorisme resol el problema en què passem de tenir roba bruta dins la rentadora a tenir-hi roba neta.

S’ha d’anar sempre amb cura de relacionar la descripció donada a l’estat inicial amb la descripció de l’estat final.

Postcondició llavors:

{Post: la roba que inicialment era dins la rentadora, continua a dins, pero ara és neta. La roba no està estripada}

Si a més s’especifique l’algorisme d’una rentadora assecadora, s’hauria d’afegir “i la roba està seca”.

Veient els algorismes com a funcions matematiques -de fet ho són- la precondició determina el domini d’aplicació de la funció i la postcondició diu quin és el resultat de la funció.

Pag 22 de 45


El comentari “la roba no està estripada” és important, ja que si no hi fos, una rentadora que estripés la roba a més de netejar-la seria vàlida per a l’especificació.

2.3 ELEMENTS DE L'ESPECIFICACIÓ

L'Especificació d'un algorisme consta de quatre parts: ● la declaració de variables, ● la precondició, ● el nom de l’algorisme ● i la postcondició.

La declaració de variables defineix el conjunt de variables que formen part de l’entorn de l’algorisme i diu de quin tipus són; la precondició i la postcondició són la descripció de l’estat inicial i final d’aquest entorn; el nom de l’algorisme hauria de ser el més significatiu possible.

D’aquesta manera amb l’especificació es diu el següent:

1. Donades unes variables amb les quals s’ha de ser capaç de representar un problema i la seva solució,

2. i donades les condicions de l’estat inicial (precondició)3. s’ha de dissenyar un algorisme tal que4. ha de ser capaç d’obtenir l’estat final desitjat, descrit en la postcondició.

Exemple: especificació d’un algorisme que calcula el factorial d’un nombre enter.

(recordar que el factorial està definit únicament per a nombres naturals, i que es el producte de tots els nombres naturals des d’1 fins a aquest nombre. El factorial de 0 està definit com 1.)

En primer lloc decidir com representar el problema i la seva solució: una variable entera per a representar el nombre del qual es vol calcular el factorial i una altra (entera) per a guardar-hi el resultat. Anomenem respectivament n i fact.

En la precondició s’haurà d’explicar quines son les condicions en què l’algorisme es podrà executar i donarà un resultat correcte. S’haurà de dir que el nombre a partir del qual es calcula el factorial (n) es més gran o igual que 0.

En la postcondició s’haurà de dir quines condicions compleix l’estat final: a fact tenim el factorial de n.

n, fact: enter;{Pre: n té com a valor inicial N i N ≥ 0}factorial{Post: fact és el factorial de N}

Es fa servir N per a designar el valor inicial de la variable n. És necessari perquè el valor de la variable n pot canviar mentre s’executa l’algorisme (ningú no garanteix que l’algorisme factorial no modifiqui n). Per convenció sempre es fa servir com a nom del valor inicial d’una variable el nom de la mateixa en majúscules.

En la postcondició no cal dir què és el factorial, no estaria malament pero seria més informació de la necessària.

Pag 23 de 45


Per a cada especificació, hi ha un conjunt d’algorismes que la compleixen o s’adapten. A més de ser correcte és important que sigui intel·ligible, eficient i general.

2.4 ESPECIFICACIÓ I COMENTARIS

L’especificació també pot servir per un cop fet l’algorisme, recordar què fa clarament sense haver de repassar tot el codi. Això pren importancia a mesura que la complexitat dels algorismes creix. També és molt recomanable afegir comentaris dins l’algorisme que permetin entendre’l facilment. Aquests comentaris poden:

1. especificar en quina situació o estat ens trobem en un moment determinat de l’algorisme. Això permetrà fer el seguiment dels estats pels quals va passant d’una manera còmoda.

2. aclarir les construccions algorísmiques que s’han fet servir. No tenen res a veure amb l’especificació pero sovint son força útils i és molt recomanable fer-los servir.

Es posaran entre claus. Tot i que no formen part de l’algorisme pròpiament, son força importants per fer-los més comprensibles (important en la fase de manteniment, per nosaltros o altres que hàgin d’entendre què fa un algorisme)

2.5 EXEMPLES D’ESPECIFICACIÓ

2.5.1 INTERCANVI DE DUES VARIABLES

Es vol especificar un algorisme que intercanviï els valors de dues variables. L’entorn estarà constituït per aquestes dues variables i s’ha de expressar per a les dues variables que el valor final d’una és el valor inicial de l’altra:

x, y: enter{Pre: x = X i y = Y}intercanviar{Post: x = Y i y = Y}

2.5.2 ARREL QUADRADA

x, arrel: real{Pre: x = X i X ≥ 0}arrelQuadrada{Post: arrel2 = X i arrel ≥ 0}

Obeservar que en la precondició s’indica que no té sentit per l’arrel quadrada d’un nombre negatiu. D’altra banda un nombre positiu té una arrel negativa i una positiva. En la postcondició s’estableix que el resultat correspongui a la positiva.

Pag 24 de 45


2.5.3 ARREL QUADRADA ENTERA

x, arrel: enter{Pre: x = X i X ≥ 0}arrelQuadradaEntera{Post: arrel2 ≤ X < (arrel2 + 1)2}

Fixar-se que en la postcondició no cal especificar que arrel ≥ 0 ja que està contemplat implícitament.

2.5.4 QUOCIENT I RESIDU

x, y, q, r: enter{Pre: x = X i y = Y i X, Y = 0}divisioEntera{Post: X = q * Y + r i es compleix que 0 ≤ r < Y}

2.5.5 NOMBRE DE DIVISORS

Es vol especificar un algorisme que calculi el nombre de divisors positius d’un nombre positiu. L’entorn estarà constituït per dues variables enteres. Una on es tindrà el nombre, i l’altra, on a l’estat final haurà d’haver el nombre de divisors d’aquell.

x, nDivisors: enter{Pre: x = X i X > 0}nombreDivisors{Post: nDivisors és el nombre de nombres entre 1 i X que divideixen Y}

Fixar-se que com que demanen el nombre de divisors sense especificar cap restricció, es té en compte tambè l’1 i X.

EXERCISIS 5, 6, 7, 8, 9

3. ESTRUCTURES ALGORÍSMIQUES

3.1 ESTRUCTURA GENERAL D’UN ALGORISME

En tot algorisme apareixen les parts següents en ordre:

Pag 25 de 45


1. Capçalera: serveix per identificar on comença la descripció de l’algorisme i per donar-li un nom.

2. Definició de constants: immediatament després de la capçalera es defineixen les constants que es faran servir. Si no es fa servir cap no es posa res.

3. Definició de tipus: Si definim tipus nous s’haurà de fer aqui, si no res.

4. Declaració de variables: dir quines variables es fan servir i de quin tipus són. La declaració de constants i tipus s’ha de fer abans perquè així aquí es podran fer servir el tipus i constants definides.

5. Cos de l’algorisme: descripció en llenguatge algorísmic de les accions que fa l’algorisme.

6. Final de l’algorisme: serveix per tenir clar on acaba.

algorisme nom

constnomConstant1 : tipus = valorConstant1;nomConstant2 : tipus = valorConstant2;…

fconst

tipusnomTipus1 = definicioTipus1;nomTipus2 = definicioTipus2;...

ftipus

var nomVariable1 : tipusVariable1;nomVariable2 : tipusVariable2;…

fvar

accio1;accio2;…

falgorisme

3.2 ACCIONS ELEMENTALS

El llenguatge algorísmic té únicament una acció elemental: l’acció d’assignació. Més endavant es veurà com definir altres accions i s’estudiaran una serie d’accions predefinides (i no elementals) que ofereix el llenguatge per a poder comunicar l’execució de l’algorisme amb l’exterior (obtenir les dades necessàries per a l’execució de l’algorisme o mostrar les dades corresponents al resultat donat per l’algorisme).

Pag 26 de 45


3.2.1 L’ASSIGNACIÓ

L’assignació és la manera que es té en llenguatge algorísmic per a donar un valor a una variable. S’expressa de la manera següent:

nom_de_variable:= expressio;

nom_de_variable és l’dentificador d’una variable i expressio es una expressió. S’ha de complir sempre que la variable i l’expressió siguin del mateix tipus. No es pot, per exemple, assignar valors booleans a variables enteres.

L’execució de l’assignació consisteix a avaluar l’expressió, cosa que dóna com a resultat un valor; i posteriorment es dóna a la variable aquest valor. Es a dir, després de fer l’assignació, la variable té com a valor el resultat d’avaluar l’expressió.

Ates que l’assignació (i en general qualsevol acció) modifica l’entorn de l’algorisme, es pot parlar d’un “estat previ” a l’execució de l’acció i d’un “estat posterior”. Per tant es poden aplicar els conceptes de precondició i postcondició a una acció. Així es pot descriure d’una manera clara i sistemàtica l’efecte que té l’execució d’una acció sobre l’entorn.

Per a l’assignació

{El resultat d’avaluar l’esxpressio E es V}x := E;{x = V (es a dir x te com a valor V)}

Exemples:

1. En el cas de tenir una variable anomenada a, que aquesta sigui del tipus caràcter i que es vulgui assignar el valor “e” es pot fer:

{}a := ‘e’;{a = ‘e’}

2. Amb una altra variable de tipus enter (d), l’expressió haurà de ser de tipus enter:

{}d := 3 * 4 + 2;{d = 14}

En aquests dos casos, les expressions estan constituïdes únicament per constants,. Per tant, independentment de l’estat de l’entorn, tindran sempre el mateix valor. Per això no cal establir cap relació entre variables i valors a la precondició, que serà sempre certa.

3. També es poden fer assignacions on en les expressions corresponents intervinguin variables, i per tant, depenguin de l’estat de l’entorn. Si x i y són dues variables reals:

Pag 27 de 45


{(y + 3) / 2 = V}x := (y + 3.0) / 2.0;{x = V}

on V és el valor de l’expressió (amb la mateixa idea dels valors inicials x = X de l’apartat anterior). Aquesta és l’aplicació directa de l’especificació general de l’assignació vista abans. Però també es pot expressar:

{y = Y}x := (y + 3.0) / 2.0;{x = (Y + 3) / 2 }

No es pot fer servir aquesta forma per a l’especificació genèrica de l’assignació, ja que no es sap quines variables intervenen en l’expressió. Però sempre que s’hagi d’especificar una assignació concreta es pot fer així, que és més clar.

D’alra banda, el valor de la variable y no ha variat després de l’assignació. És possible que ens interessi (segons l’algorisme concret del qual formi part l’assignació) que quedi reflectit, així si interessa també aquest coneixement s’hauria de posar:

{y =Y}x := (y + 3.0) / 2.0;{y = Y i x = (Y + 3) / 2}

És important tenir en compte que l’expressió E s’avalua abans de donar el valor a la variable x. Així, si la variable x apareix tambe dins l’expressió, el valor que s’haurà de fer servir per a calcular l’expressió serà el que tenia en l’estat previ a l’assignació.

Exemple: donada variable entera anomenada n,

{n = N}n := n * 2;

{n = N * 2}

3.3 COMPOSICIÓ D’ACCIONS

Com es poden combinar accions elementals per construir algorismes.

3.3.1 COMPOSICIÓ SEQÜENCIAL

La primera forma de composició i la més òbvia és la composició seqüencial d’accions. Consisteix a executar ordenadament una seqüencia d’accions:

accio1

accio2

…accio3

Pag 28 de 45


Fins ara s’ha parlat d’accions individuals. Aquestes tenen un estat previ i un estat posterior. Una seqüència d’accions també té un estat previ i un estat posterior que es pot descriure mitjançant la precondició i la postcondició de la seqüència d’accions. L’estat previ a l’execució de la seqüència d’accions es correspon amb l’estat previ a l’execució de la primera acció de la seqüència.Un cop executada la primera acció, s’obté un nou estat que és l’estat posterior a l’execució d’accio1. És a la vegada l’estat previ a l’execució de l’accio2.La darrera acció tindrà un estat posterior que és el mateix al de la seqüència d’accions.

Exemples:

1) Intercanvi de valors.Es vol donar una successió d’accions que intercanviï els valors de dues variables

enteres x i y. Suposem que tenim una tercera variable també entera (aux) que servirà per fer l’intercanvi.

{Pre: x=X i y=Y}aux := x;{x=X i y=Y i aux=X}x := y;{x=Y i y=Y i aux=X}y := aux;{x=Y i y=X i aux=X}{Post: x=Y i y=X}

-sense especificació:aux := x;x := y;y := y;

Així es podria usar aquesta seqüència d’accions per a donar un algorisme (faltaria la capçalera, declaració de variables, etc) que solucioni el problema especificat a 2.5.1. Observar que la variable aux cal per a resoldre el problema però no pren part en l’especificació (és el que es coneix com variable temporal o tambè variable auxiliar)

2) Impostos i salari netDonat el salari brut d’una persona, cal proporcionar una seqüència d’accions que calculi

el salari net i els impostos que ha de pagar, sabent que aquesta persona paga un 20% d’impostos. Suposem que disposem de tres variables reals anomenades: brut, net, impostos.

{Pre: brut = BRUT}net := brut * 0.8;{brut = BRUT i net = BRUT * 0.8}impostos := brut * 0.2;{Post: brut = BRUT i net = BRUT * 0.8 i impostos = BRUT * 0.2}

S’ha resolt amb una successió de dues accions. En la postcondició es té que el salari net és el 80% i els impostos el 20%.

A l’algorisme s’ha incorporat la precondició i postcondició, i la descripcio dels estats intermedis (en aquest cas només un) perquè es vegi com les accions de la seqüència determinen aquests estats intermedis fins arribar a l’estat final. Aquestes descripcions d’estat no formen part de l’algorisme, s’incorporen en forma de comentari.

Pag 29 de 45


3) InteressosDonat un capital inicial invertit en un dipòsit financer que dóna un 5% anual, donar una

seqüència d’accions que calculi quin capital haurà després de quatre anys (cada any els interessos obtinguts passen a engrossir el capital). Suposar que el capital inicial està en una variable real anomenada capital, i que es vol tenir el capital final també en aquesta variable.

{Pre: capital = CAPITAL}capital := capital * 105.0 / 100.0;{capital té el capital que hi ha després d’un any, on el capital inicial és CAPITAL}capital := capital * 105.0 / 100.0;

{capital té el capital que hi ha després de dos anys, on el capital inicial és CAPITAL}}capital := capital * 105.0 / 100.0;{capital té el capital que hi ha després de tres anys, on el capital inicial és CAPITAL}capital := capital * 105.0 / 100.0;{Post: capital té el capital que hi ha després de quatre anys, on el capital inicial és CAPITAL}

(Veure més endavant que això es pot resoldre de manera iterativa)

3.2 COMPOSICIÓ ALTERNATIVA

La composició alternativa permet decidir quines accions executar segons quin sigui l’estat. La sintaxi és:

si expressio llavorsaccioa

sinoacciob

fsi

Aqui expressio és una expressió de tipus booleà, i per això de vegades s’anomena tambe condicio. D’altra banda, accioa i acciob són dues accions (o successions d’accions). La seva execució consisteix a avaluar l’expressió; si aquesta és certa, s’executarà accioa; si és falsa s’executarà acciob. S’anomena alternativa doble.

Les paraules si, llavors, sino i fsi són paraules clau del llenguatge algorismic i serveixen per a delimitar fàcilment cadascuna de les parts de la composició alternativa.

Una versió més reduïda:si expressio llavors

accioa

fsi

Si la condició és falsa no es fa res. S’anomena alternativa simple.

Es fa servir la composició alternativa quan es vol executar una acció o una altra depenent de si es compleix determinada condició o no, és a dir, quan es vol variar el flux d’execució d’un algorisme.

Pag 30 de 45


Com s’expressa el significat de la composició alternativa en l’especificació:{P i el resultat d’avaluar expressio és un cert valor B (que pot ser cert o fals)}si expressio llavors

{P i B}accioa

{Qa}sino

{P i no(B)}acciob

{Qb}fsi{es compleix Qa o bé es compleix Qb}

Observar que B es un valor booleà, i per tant, {P i B} equival a dir {es compleix P i B és cert}

Qa, Qb i P dependran de quin sigui l’entorn de l’algorisme i de quines siguin accioa i acciob. Després d’avaluar l’expressió booleana es tria una branca o l’altra del si; però l’estat no es modifica. L’estat únicament es veu modificat quan es passa a executar accioa o acciob.

Exemple: Màxim de dos nombres enters.Es vol fer el cos d’un algorisme que calculi el màxim de dos nombres enters. Suposar

que es tindrà aquests dos nombres enters en dues variables enteres x i y i que es vol deixar el resultat a una altra variable entera z.

Es tracta d’assignar a z el màxim de tots dos valors (x i y). El problema és que quan es fa l’algorisme no se sap quin serà el valor mes gran, x o y.

{Pre: x=X i y=Y}si x>y llavors

{x=X i y=Y i x>y}z := x;{x=X i y=Y i X>Y i z=X; per tant: z=maxim(X,Y)}

sino {x=X i y=Y i X ≤ Y}z := y;{x=X i y=Y i X ≤ Y i z=Y; per tant z=maxim(X,Y)}

fsi{Post: z=maxim(X,Y)}

S’ha afegit al tros d’algorisme una descripció de tots els estats intermedis pels quals pot passar l’execució de l’algorisme. No cal fer-ho, però com a pas previ, cal especificar el problema, es a dir donar una precondició i postcondició globals que l’algorisme haurà de complir:

{Pre: x=X i y=Y}si x>y llavors z := x;sino z := y;fsi{Post: z=maxim(X,Y)}

És important que tant d’una branca com de l’altra es pugui deduïr la postcondició que es vol assolir.

Pag 31 de 45


3.3.3 COMPOSICIÓ ITERATIVA

mentre expressio feraccio

fmentre

expressio és una expressió de tipus booleà i accio és una acció o successió d’accions. Les paraules mentre, fer i fmentre són paraules clau del llenguatge algorísmic.

L’execució de la construcció mentre consisteix a executar l’acció mentre l’avaluació de l’expressió tingui com a resultat cert. En el moment en que l’expressió passi a ser falsa, no es fa res més. Si inicialment expressio és falsa, no s’executa accio cap vegada. A cadascuna de les execucions de l’acció es diu iteració.

Especificació. Es fa servir una propietat especial anomendada invariant (representada per I). L’invariant és una descripció de quina és l’evolucio dels càlculs acumulats al llarg de totes les iteracions que s’han fet fins a un moment determinat.

Aquesta descripció ha de servir per a descriure l’estat en que ens trobem quan encara no s’ha fet cap iteració, quan s’ha fet un, dues … i totes.

S’anomena invariant per això: una mateixa descripció serveix per descriure l’estat abans i després de cada iteració. Es a dir s’ha de complir:

1) just abans de la construcció iterativa, és a dir, en l’estat previ a la composició iterativa (encara no s’ha fet cap iteració)

2) en l’estat previ a l’execució de l’acció en totes les iteracions

3) en l’estat posterior a l’execució de l’acció en totes les iteracions.

4) un cop ja s’ha acabat l’execució de la composició iterativa, és a dir, en l’estat posterior d’aquesta (s’han fet ja totes les iteracions).

Especificació de la composició iterativa:

{I i el resultat d’avaluar expressio és un cert valor booleà B (que pot ser cert o fals)}mentre expressio fer

{I i B}accio{I}

fmentre{I i no(B)}

Exemples:

1) Multiplicació de dos enters.Multiplicar dos enters x i y fent servir únicament sumes i d’una manera general. Es

resoldrà pel cas en que la y és positiva. Fàcilment es pot ampliar l’algorisme si es fa servir

Pag 32 de 45


l’operador canvi de signe per a obtenir un algorisme que funcioni per a qualsevol y. Es guarda el resultat en una variable ja definida z.

{Pre: x=X i y=Y i Y ≥ 0}z:=0;mentre y ≠ 0 fer

z:=z+x;y:=y-1;

fmentre{Post: z=X*Y}

Quina ès la propietat invariant? L’invariant ha de contenir prou informació perquè ens serveixi per a deduir, a partir de I i no(B), la postcondició -en aquest cas z=X*Y.x=X i z=x*(Y-y) es compleix abans i després de cada iteració.

*es pot aprofundir però és més un exercici matemàtic i lògic que sera util a l’hora de dissenyar iteracions complexes. No cal trobar les invariants de totes les composicions iteratives que es dissenyen.

2) El factorial.Es vol fer un tros d’algorisme que donat un nombre enter positiu (n) en calculi el

factorial, i el deixi a la variable fact.

S’han de multiplicar tots els nombres naturals entre 1 i n. Caldrà una variable auxiliar i -que soposarem definida- per saber quin es el nombre que multipliquem en cada moment.

{Pre: n=N i N ≥ 0}fact := 1;i := 1;{n = N i N ≥ 0 i fact és el factorial de i-1 i i ≤ n + 1}mentre i ≤ n fer

fact:=fact*1;i:=i+1;

fmentre{Post: n=N, N ≥ 0, fact és el factorial de i-1 i i=i+1, per tant: fact és el factorial de N}

FINALITZACIÓ DE LA COMPOSICIÓ ITERATIVA

Un punt força important quan es fa servir la composició iterativa és saber del cert que s’acabarà en algun moment. Sempre que es fa una iteració, es corre el risc de fer-la malament i que no acabi mai. Aixi, si a l’exemple 1 (multiplicació dos nombres) ens oblidem l’acció y:=y-1, y valdrà sempre el mateix i, per tant, un cop entrem dins el mentre, l’acció z:=z+x s’executarà indefinidament.

Si donada una composició iterativa es pot trobar una funció de fita que compleixi els requisits: el resultat d’aplicar-la abans d’una iteració ha de ser estrictament més gran que el resultat d’aplicar-la després de la iteració, i si es compleix l’invariant i B és certa, ha de ser més gran que 0.

Això és un altra exercisi matemàtic.

Pag 33 de 45


VARIANTS DE LA COMPOSICIÓ ITERATIVA

La construcció mentre permet expressar qualsevol composició d’accions on s’hàgin de repetir una serie de càlculs. Moltes vegades aquesta repetició d’accions segueix un patró concret on es fa servir una variable que es va incrementant (o decrementant) a cada iteració fins que arriba a un valor donat. Per aquests casos:

per index:=valor_inicial fins valor_final [pas increment] feraccio

fper

La part “pas increment” és opcional i si no hi apareix es considera que l’increment és igual a 1. Les paraules per, fins, pas, fer i fper són paraules clau del llenguatge algorísmic.

Es pot expressar amb la sentencia mentre també:

index:=valor_inicial;mentre index ≤ valor_final fer

accio;index:=index+increment;

fmentreReformulació de l’algorisme factorial:

{Pre: n=N i N≥0}fact:=1;per i:=1 fins n fer

fact:=fact*i;fper{Post: fact és el factorial de N}

Aquesta construcció serà més còmoda de fer servir, especialment quan es treballi amb taules. En general, sempre que el nombre d’iteracions sigui conegut, es treballarà amb per.

EXERCISIS 10, 11, 12

4. ACCIONS I FUNCIONS

La notació algorísmica permet definir accions i funcions pròpies. Imaginar per exemple que ens dediquem a resoldre problemes de caire geomètric i que sovint cal calcular el sinus d’un angle i el seu cosinus. Si cada cop que es necessita calcular el sinus d’un angle, s’han de posar totes les accions necessàries per a poder fer els càlculs amb les variables corresponents, els algorismes serien llargs, gairebé repetitius, i amb massa detalls que caldria tenir en compte al llegir-los. En canvi, si per a expressar l’algorisme disposessim d’unes funcions que calculessin els sinus i cosinus d’un angle donat, l’algorisme seria possiblement més curt, i sobretot més entenedor.

Com que la notació algorísmica no té les funcions de sinus i cosinus (els llenguatges de programació si), pero permet definir funcions, es pot suposar que existeixen, i més endavant dissenyar-les i preocupar-se només una vegada de com es calcula un sinus i un cosinus a partir d’un angle donat.

Pag 34 de 45


La importància de les accions i funcions rau en el fet que són eines del llenguatge algorísmic que facilitaran la metodologia que cal seguir mes endavant en el disseny de programes.

D’altra banda quan es desenvolupen els algorismes es pot comptar amb algunes accions i funcions que es consideren predefinides, i que la majoria de llenguatges de programació proporcionen per a facilitar la tasca de la programació, especialment les accions referents a l’entrada i sortida de dades. A vegades es poden desenvolupar algorismes a partir d’una biblioteca d’accions i funcions ja desenvolupades per algun equip de desenvolupament de programari.

4.1 ACCIONS

Una acció ve a ser una mena de subalgorisme que es pot utilitzar des de qualsevol punt d’un altre algorisme o acció. Tenen la mateixa estructura que els algorismes però la capçalera es delimita per les paraules clau accio … faccio en comptes de algorisme … falgorisme.

Dins l’acció es pot definir també un entorn local o propi de l’accio (const … fconst, tipus … ftipus, var … fvar definits dins l’acció). S’enten per entorn local aquell conjunt d’objectes que només l’acció que es desenvolupa pot utilitzar. Es a dir, altres parts de l’algorisme no podran fer servir aquest entorn.

Exemple: Es vol fer l’intercanvi entre els valors de les variables enteres x i y, z i w, i v i u, respectivament.

especificant el problema:x, y, z, w, u, v: enter{Pre: (x=X i y=Y) i (z=Z i w=W) i (v=V i u=U)}tresIntercanvis{Post: (x=Y i y=X) i (z=W i w=Z) i (v=U i u=V)}

Es podria fer intercanviant cada vegada un parell de lletres:

{Pre: (x=X i y=Y) i (z=Z i w=W) i (v=V i u=U)}aux:=x;x:=y;y:=aux;{(x=Y i y=X) i (z=Z i w=W) i (v=V i u=U)}aux:=z;z:=w;w:=aux;{(x=Y i y=X) i (z=W i w=Z) i (v=V i u=U)}aux:=v;v:=u;u:=aux;{Post: (x=Y i y=X) i (z=Z i w=W) i (v=U i u=V)}

Aquest algorisme conté tres subalgorismes semblants que es diferencien només per algunes de les variables utilitzades. Hauria estat més facil expressar-ho:

{Pre: (x=X i y=Y) i (z=Z i w=W) i (v=V i u=U)}Pag 35 de 45


intercanvia x i y{(x=Y i y=X) i (z=Z i w=W) i (v=V i u=U)}intercanvia z i w{(x=Y i y=X) i (z=W i w=Z) i (v=V i u=U)}intercanvia v i u{Post: (x=Y i y=X) i (z=Z i w=W) i (v=U i u=V)}

i després definir en què consiteix “intercanvia … i …”.

Suposar que es pot accedir des de l’acció a les variables de l’algorisme que l’invoca; aleshores es podria dissenyar aquesta acció:

accio intercanviavar

aux:enter;fvaraux:=x;x:=y;y:=aux;

faccio

Suposar també que les variables x i y estan declarades en l’algorisme que invoca l’acció; aleshores es planteja un altre problema: com intercanviar les variables z i w, u i v? Posant-les en x i y abans de la crida? Això seria massa complicat.

(molts llenguatges de programació permeten fer servir dins les accions, variables que estan declarades en l’algorisme principal o altres indrets del programa -variables globals-. És un mal costum fer servir aquesta possibilitat atès que es produeixen programes poc intel·ligibles i molt difícils de seguir)

A més per dissenyar aquesta acció cal saber quina declaració de variables x i y ha fet l’algorisme que l’utilitza.

Hi ha per tant una dependència massa gran entre l’algorisme o acció que la cridi (x i y) i l’acció intercanvia. S’hauria de dissenyar sempre conjuntament l’acció i qualsevol algorisme que la vulgui utilitzar. Es vol definir una acció més general que es pugui aplicar a dues variables qualssevol i que no depengui de l’entorn particular des d’on s’invoca.

Això se soluciona mitjançant l’us de paràmetres.

4.2 PARÀMETRES

Quan es construeix i defineix una acció cal poder expressar, dins els cos de l’acció, accions que actuen sobre objectes genèrics i, més tard, poder associar aquests objectes genèrics concrets definits en l’entorn des del qual es faci servir l’acció.

(equivalent a les funcions matemàtiques: f(x) = x * x + 4. f(4) = 20. De manera anàloga, part del cos de l’acció està expressat en termes d’uns paràmetres que hauran de ser substituits per objectes reals)

Pag 36 de 45


Aquests objectes genèrics (x i y en l’exemple) s’anomenen paràmetres formals de l’acció. Llavors es diu que l’acció esta parametritzada, es a dir que per a poder-la fer servir s’han d’associar abans aquests parametres a objectes concrets.

D’altra banda els parametres formals aniran bé per a expressar allò que es volia de forma genèrica.

A la capçalera de l’acció s’indicaran quins són els parametres formals amb els quals es treballa. La sintaxi de la capçalera serà:

accio nom(param1, param2, …, paramn)… cos de l’accio

faccionom és el nom que identifica l’acció, parami son els paràmetres de l’accio.

A l’exemple l’acció quedaria:

accio intercanvia(entsor x:enter, entsor y:enter)var

aux:b;fvaraux:=x;x:=y;y:=aux;

faccio

x i y no tenen res a veure amb les variables x i y de l’algorisme, i es podrien dir de qualsevol manera.

Més endavant es veurà entsor.

Un cop definida l’acció sobre uns paràmetres, només cal indicar a l’acció a l’hora de cridar-la des de l’algorisme els objectes reals sobre els quals cal que actuï.

Per invocar l’acció dins un algorisme o una altra acció:

nom _de_l’accio(obj1, obj2, …, objn);

on objn és una variable, constant, o una expressió de l’entorn definit en l’algorisme.

Mitjançant els paràmetres l’acció es pot comunicar amb els objectes de l’entorn que l’ha invocat.

Seguint l’exemple, en l’algorisme:

{Pre: (x=X i y=Y) i (z=Z i w=W) i (v=V i u=U)}intercanvia(x, y);intercanvia(z, w);intercanvia(v, u);{Post: (x=Y i y=X) i (z=Z i w=W) i (v=U i u=V)}

En la primera invocació, x i y són els paràmetres actuals de l’acció intercanvia, en contrast amb els paràmetres formals.

Pag 37 de 45


Per tant els paràmetres formals són els que es necessiten per a definit (formalitzar) l’acció. Els paràmetres actuals o reals són els objectes que s’utilitzen en la invocació.

L’acció intercanvia(z, w) és equivalent a:

aux:=z;z:=w;w:=aux;

El tipus definit per a cada paràmetre formal ha de coincidir amb el que tingui cada paràmetre actual.

A l’exemple d’intercanvi, no es poden pasar com a paràmetres actuals, variables de tipus caràcter, ni qualsevol tipus que no sigui l’enter. En cada acció es poden definir paràmetres de diferents tipus.

(els diferents llenguatges de programació tracten això diferentment: strong typing i loose typing: poden llençar error al compilar el programa si els paràmetres són de diferent tipus, o no. més)

Els paràmetres poden ser de diferent tipus segons l’ús que se n’hagi de fer des de l’acció. Es poden classificar en:

● entrada: només interessa consultar el seu valor. Es fa servir la paraula ent.● sortida: només interessa assignar-li un valor → sor.● entrada/sortida: interessa consultar i modificar el seu valor → entsor.

Per a indicar que un paràmetre és d’entrada es fa servir la paraula ent. Si és de sortida, sor, i si és d’entrada/sortida, entsor.

(alguns llenguatges requereixen que es diferenciïn en la declaració -com C- altres no)

● Si un paràmetre és d’entrada, només interessa el seu valor inicial. Es pot modificar aquest valor dins l’acció pero no repercutirà en els parametres actuals.

● Si un paràmetre és de sortida, el seu possible valor inicial no podrà ser llegit per l’acció. Això vol dir que l’inicialització d’aquest paràmetre s’ha de fer en l’acció. Un cop executada l’acció, el valor del paràmetre actual corresponent serà el valor final del seu paràmetre formal.

● Si el paràmetre és d’entrada/sortida, el valor del paràmetre podrà ser llegit i tota modificació del seu valor repercutirà al paràmetre actual.

La sintaxi dels paràmetres en la sintaxi de la capçalera d’una acció és la següent:

● per a un paràmetre d’entrada: ent nom:tipus● per a un paràmetre de sortida: sor nom:tipus● per a un paràmetre d’entrada/sortida: entsor nom:tipus

Si un paràmetre formal és d’entrada, el paràmetre actual podrà ser una variable, una constant o una expressió.

Pag 38 de 45


Si és de sortida o d’entrada/sortida haurà de ser una variable.

Exemple: si es té definida la capçalera següent

accio miraQueFaig(ent valorEntrada:enter, sor resultat:caracter)

es pot invocar de les següents maneres:

varnombre:enter;elMeuCaracter:caracter;

fvar

…miraQueFaig(nombre, elMeuCaracter)…

o bé:

varx, y, comptador:enter;elMeuCaracter:caracter;

fvar

…miraQueFaig(comptador*(x-y)div100, elMeuCaracter)…

o bé:

varx, y, comptador:enter;elMeuCaracter:caracter;

fvar

…miraQueFaig(50, elMeuCaracter)…

En canvi seria incorrecte:

…miraQueFaig(50, ‘A’);…

ja que “A” és una constant del tipus caràcter. Si és una constant, per definició no pot variar el seu valor, i contradiu el fet que el paràmetre formal corresponent és de sortida.

4.3 FUNCIONS

Pag 39 de 45


També hi ha la possiblitat de definir funcions. Les funcions sempre retornen un valor i només poden aparèixer en les expressions. Per tant, no es poden invocar soles.

A més, els paràmetres formals (arguments) de la funció només poden ser d’entrada. L’efecte d’invocar una funció dins una expressió és executar un conjunt d’accions que calculen un valor i, finalment, retornar aquest valor que ha de ser del tipus que s’hagi declarat en la capçalera.

Sintaxi:

funcio nom(param1, param2, …, paramn):tipus……retorna expressio;

ffuncio

On parami és nom:tipus. Com els paràmetres han de ser sempre d’entrada, estalviem d’especificar que ho són amb la paraula reservada ent (no es posa).

L’expressió tipus indicarà el tipus del valor que retornarà la funció.

Tota funció ha d’acabar en una sentència com “retorna expressio” on el valor resultant de l’avaluació d’expressió ha de ser del tipus declarat a la capçalera.

A l’igual que les accions, una funció pot tenir un entorn local.

La difèrencia entre les accions i les funcions està en la forma d’invocar-les i en les restriccions dels seus paràmetres. L’invocació d’una funció sempre ha de formar part d’una expressió, mentre que la d’una acció no en forma part mai. En una funció, els seus paràmetres sempre seran d’entrada i el valor que retorna es l’únic efecte de la funció. En una acció, els paràmetres no tenen aquestes restriccions.

(aquestes restriccions sobre els paràmetres de les funcions no són mantingudes per alguns llenguatges de programació)

Exemple: es podria definir com a funció el producte basat en sumes que s’ha tractat en un subapartat anterior (si? revisar)

{Pre: x=X i y=Y i x>0 i y>0}funcio producte(x:enter, y:enter):enter

varz:enter;

fvarz:=0;mentre y ≠ 0 fer

z:=z+x;y:=y-1;

fmentreretorna z;

ffuncio{Post:producte(x, y) = X*Y}

Si en algun punt d’un algorisme s’hagués de fer el producte de a i b, i posar el resultat en c:

varPag 40 de 45


a, b, c:enter;fvar…c:=producte(a, b);…

Si s’hagués de fer el producte de a*b*c*d i posar el resultat en f:

var a, b, c, d, f:enter;

fvar…f:=producte(producte(producte(a, b), c), d);…

També es podria utilitzar la funció dins una expressió:

var a, b, c:enter;

fvar…c:=4+producte(3, producte(a, b));…

4.4 ACCIONS I FUNCIONS PREDEFINIDES

En la notació algorísmica haurà algunes accions i/o funcions ja predefinides.

4.4.1 FUNCIONS DE CONVERSIÓ DE TIPUS

● funcio realAEnter(x: real): enter● funcio enterAReal(x: enter): real● funcio caracterACodi(x: caracter): enter● funcio codiACaracter(x:enter):caracter

4.4.2. ACCIONS I FUNCIONS D’ENTRADA I SORTIDA DE DADES

El llenguatge algorísmic diposa també d’un conjunt d’accions i funcions predefinides que permeten als algorismes de rebre dades des del dispositiu d’entrada i enviar dades al dispositiu de sortida. D’aquesta manera els algorismes poden rebre les dades amb què han de treballar i retornar els resultats obtinguts.

Pag 41 de 45


● Funció que retorna un enter que s’ha introduït pel teclat del computador:funcio llegirEnter():enter

● Funció que retorna un real que s’ha introduït pel teclat del computador:funcio llegirReal():real

● Funció que retorna un caràcter llegit des del teclat:funcio llegirCaracter():caracter

● Acció que visualitza per pantalla el valor de l’enter e:accio escriureEnter(ent e: enter)

● Acció que visualitza per pantalla el valor del real r:accio escriureReal(ent r: real)

● Acció que visualitza per pantalla el valor del caràcter c:accio escriureCaracter(ent c: caracter)

Exemple d’algorisme complet:

algorisme producteNaturalsvar

x, y, z: enter;fvarx:=llegirEnter();y:=llegirEnter();{Pre: x=X i y=Y i x>0 i y>0}z:=0;mentre y ≠ 0 fer

z:=z+x;y:=y-1;

fmentre{Post: z=X*Y}escriureEnter(z);

falgorisme

O també es podria escriure com:

algorisme producteNaturalsvar

x, y, z: enter;fvarx:=llegirEnter();y:=llegirEnter();{Pre: x=X i y=Y i x>0 i y>0}z:=producte(x, y);{Post: z=X*Y}escriureEnter(z);

Pag 42 de 45


falgorisme

funcio producte(x: enter, y: enter): entervar

z: enter;fvar{Pre: z=Z}z:=0;mentre y ≠ 0 fer

z:=z+x;y:=y-1;

fmentre{Post: z=X*Y}retorna z;

ffuncio

EXERCISIS 13, 14, 15, 16, 17, 18, 19

RESUM

S’han introduït els conceptes bàsics (algorisme, entorn, estat, processador, etc). Amb la introducció de la notació algorísmica per expressar els algorismes amb una notació formal i rigorosa per tal d’evitar qualsevol ambigüitat.

Idea central: veure l’algorisme com l’agent que transforma un estat inicial de l’entorn de l’algorisme a un estat desitjat (i final) de l’entorn, passant progressivament per estats intermedis.

Pautes indicades:

1) entendre “enunciat”: especificar l’algorisme que cal dissenyar. És una reformulació de l’enunciat amb termes mes propers a l’algorísmica. Eliminar els dubtes que inicialment es puguin tenir. Preocupar-se de QUÈ hem de fer, no de COM.

{Pre: … } → Comentar amb precisió quin es l’estat inicial de partidanom_de_l’algorisme{Post: … } → Comentar amb precisió quin es l’estat final

2) Plantejar el problema: la construcció d’un algorisme passarà per descobrir l’ordre temporal en que es compondran les accions amb les estructures escollides per tal d’assolir els objectius plantejats. El seguiment dels diferents estats intermedis pels que passarà l’algorisme abans d’arribar a l’estat final, ens donarà l’ordre en que es compondran les diverses accions. Els comentaris fets per a especificar amb precissió l’estat de l’entorn en un instant donat, entre les accions que cal desenvolupar, ajudarà a raonar i construir la composició correcta d’accions.

3) Formular la solució: conèixer la sintaxi i significat dels elements del llenguatge algorísmic (força semblant a la majoria de llenguatges de programació) permetrà d’expressar amb precisió i rigor l’algorisme final.

{Pre: … } → Comentar amb precisió quin es l’estat inicial de partida

algorisme nom → descriptiu, sense espais, camelCase (amb minúscula inicial)Pag 43 de 45


const … fconst → Declarar objectes constants (enter, real, caracter, boolea)

tipus … ftipus → Declarar tipus

var … fvar → Declarar variables (enter, real, caracter, boolea)

… → Descriure seqüència d’accions amb les estructures conegudes:

○ seqüencial (;)

○ alternativa (si … fsi) (if)

○ iterativa (mentre … fmentre, per … fper)(while,

for)

falgorisme

{Post: … } → Comentar amb precisió quin es l’estat final

A vegades caldrà encapsular certes accions dins una acció i/o funció parametritzada:

ACCIONS:

{Pre: … } → Comentar amb precisió sota quines condicions l’acció treballarà

accio nom(param1, …, paramn) → Definir la capçalera de l’acció amb els seus

paràmetres formals, i indicar de quin tipus són (ent, sor,

entsor)

<Declaració entorn> → Declarar els objectes locals mitjançant const … fconst, tipus

… ftipus, var … fvar

… → Descriure seqüència d’accions que cal fer (;, si … fsi, mentre …

fmentre, per … fper)

faccio

{Post: … } → Comentar amb precisió l’efecte de l’acció

FUNCIONS:

{Pre: … } → Comentar amb precisió sota quines condicions la funció treballarà

funcio nom(param1, …, paramn): tipus → Definir la capçalera de la funció amb els seus

paràmetres formals d’entrada i el tipus de sortida.

<Declaració entorn> → Declarar els objectes locals mitjançant const … fconst, tipus

… ftipus, var … fvar

Pag 44 de 45


… → Descriure seqüència d’accions que cal fer (;, si … fsi, mentre … fmentre,

per … fper)

ffuncio

{Post: … } → Comentar amb precisió l’efecte de la funció

4) Avaluar la solució: de moment, reflexionar a partir de la semàntica de cadascun dels elements del llenguatge algorísmic, i pas a pas, veure si la seva composició és adient. Els comentaris inserits entre accions ajudaran a reflexionar i raonar sobre la correctessa de l’algorisme.

Pag 45 de 45

introducciÓ a la programaciÓ€¦ · web viewintroducciÓ a la programaciÓ material extret de...

Documents