Informática Básica

Aquesta publicaci cobreix el temari complet de lassignatura Informtica Bsica dels estudis denginyeria industrial de lEscola Tcnica Supe-rior dEnginyeria Industrial de Terrassa (ETSEIT). Consta de dues parts: una de prctica i una de teoria. La part prctica consta dexercicis dauto-avaluaci per reforar els conceptes introduts a la teoria, problemes resolts exhaustivament per facilitar laprenentage dels diferents mtodes de resoluci i projectes resolts semblants als des-envolupats a les classes de laboratori. Les trans-parncies cobreixen la part de teoria i la part de laboratori de lassignatura. El seu objectiu s afa-vorir el seguiment de les classes i que es puguin utilitzar com a material destudi.

91

Info

rmt

ica

bs

ica

Fra

nch

- M

arco

Mo

liner

o -

Pet

it -

Xha

fa

AULA POLITCNICA/ INFORMTICA

X. Franch - J. Marco - X. MolineroJ. Petit - F. Xhafa

Informtica bsica

EDICIONS UPC

9 788483 016602

Informtica bsica

Xavier Franch, Jordi MarcoXavier Molinero, Jordi Petit , Fatos Xhafa

Primera edici: setembre de 2001Segona edici: febrer de 2002Tercera edici: setembre de 2002

Aquesta publicaci sacull a la poltica de normalitzaci lingsticai ha comptat amb la collaboraci del Departament de Cultura ide la Direcci General dUniversitats, de la Generalitat de Catalunya.

Disseny de la coberta: Edicions UPC

Els autors, 2001

Edicions UPC, 2001 Edicions de la Universitat Politcnica de Catalunya, SL Jordi Girona Salgado 31, 08034 Barcelona Tel. 93 401 68 83 Fax 93 401 58 85 Edicions Virtuals: www.edicionsupc.es e-mail: [email protected]

Producci: CPET (Centre de Publicacions del Campus Nord) La Cup. Gran Capit s/n, 08034 Barcelona

Dipsit legal: B-39922-2002ISBN: 84-8301-660-5

Sn rigorosament prohibides, sense lautoritzaci escrita dels titulars del copyright, sota les sancions esta-blertes a la llei, la reproducci total o parcial daquesta obra per qualsevol procediment, inclosos la repro-grafia i el tractament informtic, i la distribuci dexemplars mitjanant lloguer o prstec pblics.

Pro`leg

El llibre Informa`tica Ba`sica neix, com tantes altres vegades, quasi sense voler, apartir del material que hem anat elaborant els autors durant els anys que hemimpartit doce`ncia a les assignatures dInforma`tica Ba`sica i de Fonaments dIn-forma`tica als estudis de lEscola Te`cnica Superior dEnginyeria Industrial de Ter-rassa (ETSEIT) i lEscola Universita`ria dEnginyeria Te`cnica Industrial de Ter-rassa (EUETIT) de la Universitat Polite`cnica de Catalunya (UPC).

El nostre objectiu ha estat confeccionar una obra que sadaptes a les caracterstiquesde les assignatures esmentades. Per aixo`, hem intentat, en la mesura dels possibles,cobrir els aspectes ba`sics i fonamentals en un curs dintroduccio a la programacio,tant en el vessant teo`ric com en laplicat. Daquesta forma, volem solucionar par-cialment labse`ncia de material especfic per aquestes assignatures.

El resultat ha estat un text organitzat en dues unitats diferenciades, una de pro-blemes resolts i una de teoria.

A la primera unitat, plantegem exercicis dautoavaluacio, problemes resolts i pro-jectes resolts. Els exercicis solen ser enunciats curts i concisos, cadascun dels qualsinvolucra una te`cnica o un coneixement especfic del temari. En general, es tractadexercicis que illustren els conceptes que shan introdut a les classes de teoria. Elsproblemes resolts presenten una major complexitat que la dels exercicis i, frequent-ment, involucren diferents conceptes teo`rics que cal combinar per obtenir una bonasolucio. La majoria dels problemes han aparegut en exa`mens parcials o finals re-cents en les assignatures de les titulacions esmentades (tot i que han estat adaptatsi unificats). La resolucio dels problemes permet mitigar les dificultats que sovinttenen els alumnes en aplicar sobre casos concrets els conceptes que han adquirit i,fins i tot, ente`s en les classes de teoria. Per aixo`, hem intentat comentar exhausti-vament les solucions per facilitar laprenentatge dels diversos me`todes de resolucio

iv

dels problemes. Els projectes resolts pretenen ser un model per a la realitzacio deprojectes semblants, com els que els alumnes han de desenvolupar a les classes delaboratori.

La segona unitat consisteix en una colleccio de transpare`ncies que poden ser usadesen el curs a les classes de teoria i de laboratori. Hem dissenyat les transpare`ncies demanera que siguin forca autoexplicatives, potser mes denses del que es usual en unestranspare`ncies daquesta mena, a mig cam entre transpare`ncies i llibre de text.Aquestes transpare`ncies es divideixen en una part de teoria i una de laboratori.A la part de teoria, es cobreixen els conceptes ba`sics dalgorsmia habituals enun curs dintroduccio a la programacio, sempre tenint en compte, com hem ditanteriorment, el context de les assignatures, tant pel que fa al nombre dhoreslectives com pel fet que semmarquen en uns estudis no informa`tics. A la part delaboratori, es presenten les regles ba`siques de traduccio de la notacio algorsmicaemprada a teoria, al llenguatge de programacio C. Aquesta unitat tambe sillustraamb diversos exercicis resolts.

Voldrem agrair als nostres companys del departament de Llenguatges i SistemesInforma`tics que han fet doce`ncia en aquestes assignatures la seva participacio enla confeccio dalguns dels enunciats dels problemes que apareixen en aquests llibre,aix com els seus comentaris sobre versions preliminars del material.

Esperem que el llibre sigui dutilitat no nomes per als estudiants daquestes assig-natures, sino tambe per als daltres assignatures similars que existeixen en centresno informa`tics de la UPC i altres universitats de parla catalana.

Barcelona, juliol de 2002

Els autors

Index

Pro`leg i

Index v

I Exercicis i problemes 1

1 Introduccio a lalgorsmia 3Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 La congrue`ncia de Zeller per a calendaris . . . . . . . . . . . . . . 81.2 El valor clau per a calendaris . . . . . . . . . . . . . . . . . . . . . 9

2 Seque`ncies 11Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1 Misteri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Vaques boges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3 El control de qualitat . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4 Infraccions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5 Codis de barres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.6 El supermercat Fruita Madura . . . . . . . . . . . . . . . . . . . . 162.7 Productes caducats . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.8 El valor actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.9 La benzinera de Vilanova . . . . . . . . . . . . . . . . . . . . . . . 172.10 El pa`rquing de la Mutua de Terrassa . . . . . . . . . . . . . . . . . 182.11 El polgon equilateral . . . . . . . . . . . . . . . . . . . . . . . . . . 19

vi Index

2.12 La Pica dEstats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.13 Valls minimals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.14 El torneig de futbol . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Accions i funcions 23Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1 No ho se . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 Tampoc no ho se . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.3 Qui ho sap? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.4 Inco`gnita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.5 Comparar dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.6 Articles caducats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.7 Llaunes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.8 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.9 Sumar dgits parells de f(x) . . . . . . . . . . . . . . . . . . . . . . 283.10 La pesta porcina . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.11 Leibniz i pi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Taules 31Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1 Sobre la taula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Pantans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.3 LAvi Pep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.4 El pa`rquing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.5 Vols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.6 Punt de creu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.7 Vector suma columnes . . . . . . . . . . . . . . . . . . . . . . . . . 374.8 Files i columnes perpendiculars . . . . . . . . . . . . . . . . . . . . 374.9 Numeros binaris . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.10 El valor propi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.11 La planificacio de tasques . . . . . . . . . . . . . . . . . . . . . . . 394.12 La suma per capes . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.13 El monitor MonocromTM . . . . . . . . . . . . . . . . . . . . . . . 404.14 La codificacio de missatges . . . . . . . . . . . . . . . . . . . . . . 414.15 Generacio de permutacions . . . . . . . . . . . . . . . . . . . . . . 414.16 El segment nul mes llarg . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Tuples i estructures de dades 43Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.1 La farmace`utica de Sant Cugat . . . . . . . . . . . . . . . . . . . . 465.2 El parc mo`bil dIgualada . . . . . . . . . . . . . . . . . . . . . . . . 475.3 La biblioteca de Castelldefels . . . . . . . . . . . . . . . . . . . . . 475.4 La Universitat de Mataro . . . . . . . . . . . . . . . . . . . . . . . 485.5 Lassociacio de titulats . . . . . . . . . . . . . . . . . . . . . . . . . 485.6 La xarxa de concessionaris . . . . . . . . . . . . . . . . . . . . . . . 485.7 El museu de pintura . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Index vii

5.8 Provncies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.9 Lhospital de Manresa . . . . . . . . . . . . . . . . . . . . . . . . . 505.10 Polinomis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6 Disseny descendent 53Exercicis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6.1 Departaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.2 La immobilia`ria de Canet de Mar . . . . . . . . . . . . . . . . . . . 566.3 El control dacces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576.4 Coixos F.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586.5 El problema del gallifante . . . . . . . . . . . . . . . . . . . . . . . 596.6 Vendes duna empresa . . . . . . . . . . . . . . . . . . . . . . . . . 606.7 El centre de traduccions Que diu que que` . . . . . . . . . . . . . . 616.8 El quadrat ma`gic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.9 El traductor automa`tic . . . . . . . . . . . . . . . . . . . . . . . . . 636.10 Els gratacels de Terrassa . . . . . . . . . . . . . . . . . . . . . . . . 64

II Problemes resolts 67

1 Introduccio a lalgorsmia 691.1 La congrue`ncia de Zeller per a calendaris . . . . . . . . . . . . . . 691.2 El valor clau per a calendaris . . . . . . . . . . . . . . . . . . . . . 71

2 Seque`ncies 752.1 Misteri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752.2 Vaques boges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752.3 El control de qualitat . . . . . . . . . . . . . . . . . . . . . . . . . . 762.4 Infraccions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772.5 Codis de barres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782.6 El supermercat Fruita Madura . . . . . . . . . . . . . . . . . . . . 782.7 Productes caducats . . . . . . . . . . . . . . . . . . . . . . . . . . . 802.8 El valor actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812.9 La benzinera de Vilanova . . . . . . . . . . . . . . . . . . . . . . . 822.10 El pa`rquing de la Mutua de Terrassa . . . . . . . . . . . . . . . . . 832.11 El polgon equilateral . . . . . . . . . . . . . . . . . . . . . . . . . . 852.12 La Pica dEstats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862.13 Valls minimals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862.14 El torneig de futbol . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3 Accions i funcions 893.1 No ho se . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.2 Tampoc ho se . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.3 Qui ho sap? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.4 Inco`gnita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.5 Comparar dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.6 Articles caducats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

viii Index

3.7 Llaunes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923.8 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923.9 Sumar dgits parells de f(x) . . . . . . . . . . . . . . . . . . . . . . 933.10 La pesta porcina . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943.11 Leibniz i pi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4 Taules 974.1 Sobre la taula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.2 Pantans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 984.3 LAvi Pep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 984.4 El pa`rquing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994.5 Vols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004.6 Punt de creu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.7 Vector suma columnes . . . . . . . . . . . . . . . . . . . . . . . . . 1024.8 Files i columnes perpendiculars . . . . . . . . . . . . . . . . . . . . 1034.9 Numeros binaris . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.10 El valor propi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054.11 La planificacio de tasques . . . . . . . . . . . . . . . . . . . . . . . 1064.12 La suma per capes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1074.13 El monitor monocromTM . . . . . . . . . . . . . . . . . . . . . . . . 1084.14 La codificacio de missatges . . . . . . . . . . . . . . . . . . . . . . 1104.15 Generacio de permutacions . . . . . . . . . . . . . . . . . . . . . . 1134.16 El segment nul mes llarg . . . . . . . . . . . . . . . . . . . . . . . . 115

5 Tuples i estructures de dades 1195.1 La farmace`utica de Sant Cugat . . . . . . . . . . . . . . . . . . . . 1195.2 El parc mo`bil dIgualada . . . . . . . . . . . . . . . . . . . . . . . . 1215.3 La biblioteca de Castelldefels . . . . . . . . . . . . . . . . . . . . . 1235.4 La Universitat de Mataro . . . . . . . . . . . . . . . . . . . . . . . 1255.5 Lassociacio de titulats . . . . . . . . . . . . . . . . . . . . . . . . . 1265.6 La xarxa de concessionaris . . . . . . . . . . . . . . . . . . . . . . . 1275.7 El museu de pintura . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.8 Provncies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1305.9 Lhospital de Manresa . . . . . . . . . . . . . . . . . . . . . . . . . 1315.10 Polinomis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6 Disseny descendent 1356.1 Departaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1356.2 La immobilia`ria de Canet de Mar . . . . . . . . . . . . . . . . . . . 1366.3 El control dacces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.4 Coixos F.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.5 El problema del gallifante . . . . . . . . . . . . . . . . . . . . . . . 1446.6 Vendes duna empresa . . . . . . . . . . . . . . . . . . . . . . . . . 1466.7 El centre de traduccions Que diu que que` . . . . . . . . . . . . . . 1486.8 El quadrat ma`gic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1506.9 El traductor automa`tic . . . . . . . . . . . . . . . . . . . . . . . . . 153

Index ix

6.10 Els gratacels de Terrassa . . . . . . . . . . . . . . . . . . . . . . . . 156

III Projectes resolts 159

1 Borsa 1611.1 Enunciat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1611.2 Solucio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

1.2.1 Disseny de les estructures de dades . . . . . . . . . . . . . . 1621.2.2 Primer nivell del disseny descendent . . . . . . . . . . . . . 1631.2.3 Segon nivell del disseny descendent . . . . . . . . . . . . . . 1641.2.4 Tercer nivell del disseny descendent . . . . . . . . . . . . . 1651.2.5 Quart nivell del disseny descendent . . . . . . . . . . . . . . 1661.2.6 Cinque` nivell del disseny descendent . . . . . . . . . . . . . 1671.2.7 Traduccio a C . . . . . . . . . . . . . . . . . . . . . . . . . . 1681.2.8 Joc de prova . . . . . . . . . . . . . . . . . . . . . . . . . . 172

2 Ba`squet 1732.1 Enunciat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1732.2 Solucio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

2.2.1 Disseny de les estructures de dades . . . . . . . . . . . . . . 1752.2.2 Primer nivell del disseny descendent . . . . . . . . . . . . . 1762.2.3 Segon nivell del disseny descendent . . . . . . . . . . . . . . 1772.2.4 Tercer nivell del disseny descendent . . . . . . . . . . . . . 1782.2.5 Quart nivell del disseny descendent . . . . . . . . . . . . . . 1802.2.6 Traduccio a C . . . . . . . . . . . . . . . . . . . . . . . . . . 1802.2.7 Joc de prova . . . . . . . . . . . . . . . . . . . . . . . . . . 184

IV Transpare`ncies 187

1 Transpare`ncies de teoria 1891.1 Introduccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1891.2 Seque`ncies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2071.3 Subprogrames: accions i funcions . . . . . . . . . . . . . . . . . . . 2171.4 Constructors de tipus: taules i tuples . . . . . . . . . . . . . . . . . 2221.5 Disseny descendent . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

2 Transpare`ncies de laboratori 2452.1 Introduccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2452.2 Accions i funcions . . . . . . . . . . . . . . . . . . . . . . . . . . . 2542.3 Taules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2602.4 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

V Annex 269

Part I

Exercicis i problemes

1Introduccio a lalgorsmia

Exercicis

1. Expliqueu la incide`ncia de la Informa`tica en la vostra a`rea de lEnginyeria.

2. Expliqueu a un turista perdut com anar de la Placa Major a lAeroport delPrat utilitzant transports publics en una dia de vaga de taxis.

3. Que` es un algorisme?

4. Digueu quin es el contrari de les assercions seguents:

a es mes petit que b. Plou i fa sol. Dues rectes tenen un punt en comu. Tots els camins porten a Roma. Tots els a`necs son blancs i volen.

5. Feu les taules de veritat de no (a i b) i de no a o no b. Quina es la vostraconclusio? Feu el mateix per no (a o b) i per no a i no b.

6. Feu les taules de veritat de no (a i b i c) i de no a o no b o no c. Quina esla vostra conclusio? Feu el mateix per no (a o b o c) i per no a i no b i no c.

7. Epime`nides de Creta va afirmar: Tots els cretencs son uns mentiders. Que`en penseu?

8. Representeu els enters 0, 1, 73, 81 i 524 en una ma`quina que te les paraulesde 16 bits usant lestrate`gia de representacio per signe i magnitud. Quin eslinterval denters que es pot representar en aquesta ma`quina?

4 Introduccio a lalgorsmia

9. En el codi ASCII, la a es representa amb el valor nume`ric 97, la A amb el65 i el 0, amb el 48. Digueu els valors nume`rics que representen els cara`cters3, 8, A i Z en aquest codi. Representeu aquests valors nume`rics usantparaules de 8 bits.

10. Quins son els tipus ba`sics? Digueu quins valors son admissibles per a cadatipus. Feu una taula on per a cada operador llisteu quins son els tipus delsseus operands i quin es el tipus del seu resultat. Assenyaleu quins errors espoden donar en aplicar aquests operadors.

11. Digueu de quin tipus son les expressions seguents i avalueu-les:

12 12.0 3 + 4 5 4 div 8 div 10 (3 mod 2 = 0) = (7 div 2 > 2) 3 + (4 5) 4 div (8 div 10) cert i fals o cert (3 + 4) 5 ((((3 + 4) 5))) (4 div 8) div 10 cert i (fals o cert) (S D) i (3 = 2 + 1) (5 + 1) div (9 mod 3) enterAreal(34) realAenter(4.9) + realAenter(4.1) realAenter(4.9 + 4.1) cara`cterAenter(9) (en el codi ASCII) enterAcara`cter(65) (en el codi ASCII) cara`cterAenter(2) cara`cterAenter(4)

12. Donades aquestes declaracions:

vari, j, k : enterx, y, z : reala, b, c : cara`cterp, q, r : boolea`

fvar

digueu quines de les expressions seguents son inadmissibles en un algorismei perque`:

a i+ 3 x (j k) div i

Introduccio a lalgorsmia 5

(j k) div x (j k) div cara`cterAenter(x) (j k)/x ((i j z) (x y y)) = (no a i b) |x y|+ z x 0 x2 y2 no (p i q i r i (c A)) (p+ r) + i 3 i (j z) x a b i b > c (3 x)/(3.1416 y)) x+ y + z

i

13. Expliqueu el significat de les instruccions dassignacio, de sequenciacio, al-ternativa, iterativa, de lectura i descriptura.

14. Expliqueu com es comporten els operadors div i mod amb operands negatius.Calculeu 7 div 4, 7 div 3, 7 div 3, 7 div 3, 7 mod 3, 7 mod 3,7 mod 3, i 7 mod 3.

15. Dissenyeu un algorisme que llegeixi dos nombres reals i escrigui la seva suma.

16. Dissenyeu un algorisme que llegeixi un nombre enter i escrigui si es parell osenar.

17. Dissenyeu un algorisme que llegeixi un nombre enter entre 100 i 999 i escriguisi es cap-i-cua.

18. Dissenyeu un algorisme que, donats tres enters que representen hores, minutsi segons, doni lequivalent en segons.

19. Dissenyeu un algorisme que, donats tres enters que representen hores, minutsi segons, sumi un segon i doni el resultat en el mateix format.

20. Dissenyeu un algorisme que, donada una quantitat de segons, digui quanteshores, minuts i segons representa.

21. Dissenyeu un algorisme que converteixi de pessetes a euros, arrodonint comfixa la llei.

22. Dissenyeu un algorisme que donada una quantitat en euros, doni el nombremnim de bitllets i monedes necessaris, sabent que es disposa de monedes de1, 2, 5, 10, 20 i 50 ce`ntims i 1 i 2 euros, i bitllets de 5, 10, 20, 50, 100, 200 i500 euros.

23. Escriviu expressions que, donat un real r, calculin:

la part entera per defecte de r,


la part entera superior de r, el valor enter mes proper a r.

24. Escriviu expressions booleanes que, donat un cara`cter c, indiquin:

si c es una lletra minuscula, si c es una lletra majuscula, si c es un dgit, si c no es ni minuscula ni majuscula ni dgit, si c es una vocal, si c es una consonant, si c es un smbol de puntuacio.

25. Escriviu una expressio entera que es correspongui al valor dun dgit donat(cara`cters de 0 a 9).

26. Escriviu una expressio que converteixi un enter entre 0 i 9 al seu dgit cor-responent.

27. Dissenyeu un algorisme que donats dos intervals reals [a1, b1] i [a2, b2] diguisi el primer es troba dins del segon.

28. Dissenyeu un algorisme que donats dos intervals reals [a1, b1] i [a2, b2] calculilinte`rval corresponent a la seva interseccio o indiqui que es buida.

29. Dissenyeu un algorisme que donades dues hores del rellotge h1:m1:s1 i h2:m2:s2,indiqui si una altra hora h:m:s es troba entre la primera i la segona.

30. Per als problemes seguents, identifiqueu quines son les entrades, quines sonles sortides, quina relacio hi ha entre les entrades i les sortides, quines con-dicions han de complir les entrades i quins errors es poden donar. No feu elsalgorismes.

Calcular la suma de dos nombres reals. Calcular el producte de dos nombres reals. Calcular el quocient de dos nombres reals. Calcular el quocient i el residu de dos nombres enters. Calcular el valor absolut dun nombre real. Calcular larrel quadrada dun nombre real. Resoldre una equacio lineal. Resoldre una equacio de segon grau. Trobar el valor mes alt duna llista denters. Trobar la mitjana de les notes dels alumnes duna classe. Calcular la dista`ncia entre dos punts del pla. Calcular la dista`ncia entre dos punts de lespai. Esbrinar si dues lnies son paralleles o sintersecten. Simplificar una fraccio. Decidir si dues fraccions representen el mateix nombre racional.


31. Un any de traspa`s es un any civil que consta de 366 dies civils. Son anys detraspa`s tots els multiples de 4 que no ho son de 100, o que son de 100 pero`tambe de 400.

Escriviu una expressio que indiqui si una variable entera any es de traspa`s ono.

32. Dissenyeu un algorisme que llegeixi dos enters i nescrigui el ma`xim.

33. Dissenyeu un algorisme que llegeixi dos enters i els escrigui ordenats.

34. Dissenyeu un algorisme que llegeixi tres enters i els escrigui ordenats.

35. Dissenyeu un algorisme que llegeixi quatre enters i els escrigui ordenats.

36. Dissenyeu un algorisme que llegeixi un enter que representa una data enformat ddmmaaaa i escrigui el dia, el mes i lany corresponent.

37. Dissenyeu un algorisme que llegeixi un enter que representa una hora delrellotge en format hhmmss i escrigui lhora, els minuts i els segons correspo-nents.

38. Dissenyeu un algorisme que llegeixi dues dates (dia, mes i any de cadascuna)i digui si la primera es anterior en el temps a la segona.

39. Dissenyeu un algorisme que digui si un enter positiu es primer o no.

40. Dissenyeu un algorisme que escrigui el producte de factors primers dunnumero natural.

41. Dissenyeu un algorisme que escrigui els 10 primers numeros primers de laforma 2n 1 amb n natural.

42. Dissenyeu un algorisme que escrigui les taules de multiplicar del 0 al 9.

43. El teorema de Fermat estableix que lequacio an + bn = cn no te solucio pera a, b i c enters diferents de 0, amb n 3. Feu un algorisme que comprovila certesa del teorema per a 1 a, b 1000 i 3 n 100.

44. Un dels problemes potencials de les operacions aritme`tiques en els ordina-dors es el sobreeiximent: el resultat duna operacio no es pot representar ambla paraula de lordinador perque` falten bits. Un algorisme totalment fiablehauria sempre de verificar que una operacio aritme`tica no provoca sobreeixi-ment. Dissenyeu un algorisme que llegeixi dos enters i, per a cadascuna deles operacions aritme`tiques de suma, resta, producte, divisio i mo`dul detectisi provoca sobreeiximent o no aplicada sobre aquests dos enters.

45. Dissenyeu un algorisme que intercanvi el valor de dues variables enteres senseusar cap variable auxiliar.

46. Que` penseu de lalgorisme seguent?


x := i := 10mentre i > 0 fer

si x = x llavors i := i+ 1 sino i := i 1 fsifmentre

47. Que` penseu de lalgorisme seguent?

i := mentre i 6= 0 fer

i := i 2fmentre

48. Simplifiqueu lalgorisme seguent:

si x = y llavors iguals := cert sino iguals := fals fsi

49. Un mag diu: Pensat un numero. Multiplical per dos. Suma-li 34. Divideix-lo per dos. Treu-li el numero que havies pensat. Ten queden 17!

Que` en penseu?

1.1 La congrue`ncia de Zeller per a calendaris

La congrue`ncia de Zeller es un ca`lcul que permet obtenir el dia de la setmana pera una data qualsevol del calendari gregoria`. Donada una data determinada peltriplet d,m, a, on d es el dia del mes, m es el mes de lany i a es lany,

1. Se li resten dues unitat al mes m i si dona zero o menys se li suma 12 al mesi se li resta una unitat a lany. El nou mes obtingut lanomenem m i el nouany a.

2. Es calcula la centuria c (els dos primers dgits de lany) a partir de lany a.

3. Es calcula lany dins la centuria y (els dos darrers dgits de lany) a partir delany a.

4. Es calcula

f = b2.6m 0.2c+ d+ y + by/4c+ bc/4c 2c,on bxc es la part entera per defecte de x.

5. f mo`dul 7 representa el dia de la setmana segons la corresponde`ncia seguent:0 = diumenge, 1 = dilluns, ...

Utilitzeu la congrue`ncia de Zeller per determinar en quin dia de la setmana vauneixer. Funciona?

Dissenyeu un algorisme que, tot utilitzant la congrue`ncia de Zeller, llegeixi unadata (dia, mes i any) i escrigui en quin dia de la setmana cau.

Traduu el vostre algorisme a C.


1.2 El valor clau per a calendaris

Un any de traspa`s es un any civil que consta de 366dies civils. Despres de la reforma gregoriana sonanys de traspa`s tots els anys multiples de quatreque no acabin en dos zeros i tambe tots aquellsque, acabats en dos zeros, tinguin el nombre quequedaria en treure els dos zeros finals divisible perquatre. Aix, 1700, 1800, 1900, tot i esser multiplesde 4, no foren de traspa`s; en canvi, lany 2000 hova ser.

El me`tode del valor clau es un ca`lcul que permetobtenir el dia de la setmana per a una data qual-sevol en el calendari gregoria`. Donat un dia deter-minat pel triplet d,m, a, on d es el dia del mes,m es el mes de lany i a es lany,

1. Es calcula la centuria c (els dos primers dgits de lany) a partir de lany a.

2. Es calcula lany dins la centuria y (els dos darrers dgits de lany) a partir delany a.

3. Sagafa el residu r de dividir c entre 4.

4. Es calcula

v1 =y

4

+ d+ 11 2r + y

on bxc es la part entera per defecte de x.5. Es calcula

v2 = v1 + clau(m)

on clau(m) es una funcio que pren els valors seguents:

m 1 2 3 4 5 6 7 8 9 10 11 12clau(m) 1 4 4 0 2 5 0 3 6 1 4 6

6. Si el mes m correspon a gener o febrer i lany a es de traspa`s, es resta 1 a v2.

7. Es calcula s, que val el resultat dagafar el residu de dividir v2 entre 7 iafegir-li 1.

8. El valor de s indica el dia de la setmana segons la corresponde`ncia seguent:1 = dilluns, 2 = dimarts, ...


Utilitzeu el me`tode del valor clau per determinar en quin dia de la setmana vauneixer. Funciona?

Dissenyeu un algorisme que, tot utilitzant el me`tode del valor clau, llegeixi unadata (dia, mes i any) i escrigui en quin dia de la setmana cau .

Traduu el vostre algorisme a C.

La`bac es una ajuda meca`nica per a comptar. Les operacions de suma,resta, multiplicacio i divisio es poden portar a terme tant fa`cilment enun a`bac esta`ndard, que en molts pasos asia`tics encara sutilitza.

2Seque`ncies

Exercicis

1. Dissenyeu un algorisme que llegeixi una seque`ncia denters acabada per unzero i digui quants enters la componen.

2. Dissenyeu un algorisme que llegeixi una seque`ncia denters acabada per unzero i compti quants cops apareix el numero 123.

3. Dissenyeu un algorisme que llegeixi una seque`ncia denters acabada per unzero i compti quants numeros positius hi apareixen.

4. Dissenyeu un algorisme que llegeixi una seque`ncia denters acabada per unzero i digui si hi ha mes positius que negatius.

5. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i diguiquants cara`cters la componen.

6. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i diguiquants cops hi apareix la lletra Q.

7. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i diguiquantes vocals hi apareixen.

8. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i digui sihi ha mes vocals que consonants.

9. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i en calculi la mitjana aritme`tica.

10. Dissenyeu un algorisme que, donat un enter positiu, digui quantes xifres te.

12 Seque`ncies

11. Dissenyeu un algorisme que generi els 100 primers termes de la se`rie de Fi-bonacci, definida com:

F (n) =

0, n = 0,1, n = 1,F (n 1) + F (n 2), n 2.

12. Dissenyeu un algorisme que escrigui del reves la representacio bina`ria dunenter positiu, usant el menor nombre de bits possible. Per exemple, per alenter 18, hauria descriure 01001.

13. Dissenyeu un algorisme que escrigui del reves la representacio bina`ria dunenter positiu, usant el mnim nombre de bits multiple de 8 possible. Perexemple, per a lenter 18, hauria descriure 01001000.

14. Dissenyeu un algorisme que llegeixi una se`rie de zeros i uns, corresponent a larepresentacio bina`ria dun enter positiu vista del reves, i digui quin es lenterrepresentat.

15. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui quins son lelement mes petit i el mes gran.

16. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui la difere`ncia entre lelement mes petit i el mes gran.

17. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i digui elnombre de vegades que apareix la sllaba LA.

18. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si hi ha algun element mes gran que 512.

19. Dissenyeu un algorisme que llegeixi una frase acabada en un punt i digui sihi ha alguna lletra R.

20. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si un element donat hi apareix.

21. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i ordenada creixentment i digui si un element donat hi apareix.

22. Dissenyeu un algorisme que llegeixi una frase acabada per un punt i digui sitotes les vocals hi apareixen alguna vegada.

23. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si la difere`ncia entre lelement mes petit i el mes gran esmes gran o igual que 69.

24. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si es creixent o no.

Seque`ncies 13

25. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si conte dos elements consecutius repetits.

26. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si conte tres elements consecutius repetits.

27. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si formen una progressio aritme`tica o no.

28. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i compti el nombre de pics estrictes. Un pic estricte apareix quanun element es estrictament mes gran que el seu anterior i el seu successor enla seque`ncia. El primer i lultim elements no poden ser pics estrictes. Perexemple, es un pic estricte el tros de seque`ncia 4 6 5, mentre que no ho esel tros de seque`ncia 4 6 6 5.

29. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si te algun pic estricte.

30. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si te algun pic (no necessa`riament estricte). Un pic (nonecessa`riament estricte) apareix quan hi ha diversos elements iguals que sonestrictament mes grans que el seu anterior i el seu successor en la seque`ncia.El primer i lultim elements no poden ser pics. Per exemple, es un pic el trosde seque`ncia 4 6 6 6 6 5.

31. Dissenyeu un algorisme que llegeixi una seque`ncia denters positius acabadaper un zero i digui si hi ha mes pics estrictes que valls estrictes. La definiciode vall estricta es sime`trica a la de pic estricte. Aix, el tros de seque`ncia6 3 7 forma una vall estricta.

32. Donada una frase acabada per un punt que no pot tenir blancs a linici, comp-teu el nombre de lletres que tenen la primera i la darrera paraula. Considereuque les paraules se separen per blancs i que no hi ha smbols de puntuacio.

33. Donada una frase acabada per un punt que pot tenir blancs a linici, compteuel nombre de lletres que tenen la primera i la darrera paraula.

34. Donada una frase acabada per un punt, digueu si totes les paraules comencemamb la mateixa lletra.

35. Donada una frase acabada per un punt, digueu si totes les paraules acabenamb la mateixa lletra.

36. Donada una frase acabada per un punt, compteu totes les paraules que nomescontenen una sola vocal.

37. Determineu el primer nombre natural n que compleix la propietat 17n+ 9 =2n2.

14 Seque`ncies

38. Malgrat les protestes de les organitzacions ecologistes, la companyia PetiQui-Peti ha installat una central nuclear i ha decidit incorporar-hi un control dequalitat basat en el mostreig perio`dic dels nivells de radioactivitat. Dissenyeuun algorisme que llegeixi una seque`ncia denters que representa el nivell diaride radioactivitat i que escrigui un * cada vegada que detecti una entradaamb valor superior o igual a 25, o be dues entrades seguides superiors o igualsa 15. El programa acabara` o be en detectar un nivell 1, que indica que lacentral nuclear ha tancat, o en detectar un nivell 50, que representa un nivellde radioactivitat tan gran que assegura que no queda ningu a qui avisar.

39. Dissenyeu un algorisme que indiqui si una expressio acabada en un # esta`ben parentitzada. Es considera que una expressio esta` ben parentitzada si escompleix que:

En qualsevol moment de la lectura de lexpressio es te que el nombre depare`ntesis oberts es mes gran o igual al nombre de pare`ntesis de tancar.

Un cop sha acabat de llegir lexpressio, tenim el mateix nombre depare`ntesis oberts que de tancats.

Per exemple, ))a+b)(((# esta` mal parentitzada, pero` (a+b)((a+b))#ho esta` be.

40. Apliqueu certes regles ba`siques de correccio ortogra`fica a un text escrit encastella` que acaba per un cara`cter *. Concretament, heu de donar com asortida el mateix text tot aplicant les regles seguents:

Les paraules formades per una sola i han de canviar-se a y. Cal canviar les n que hi ha davant de p per m (conpra compra). Cal canviar les sllabes nv per mb (canviar cambiar). Les q sempre han danar seguides per u (qeso queso). La primera lletra que hi hagi darrera dun punt sempre ha destar en

majuscula.

2.1 Misteri

Considereu lalgorisme seguent:

algorisme misterivar

m, a : enterfvar

llegir(a)m := amentre a > 0 fer

si m < a llavors

Seque`ncies 15

m := afsillegir(a)

falgorismeescriure(m)

falgorisme

a) Quina es la sortida daquest algorisme donada lentrada 3 8 9 4 2 -1?

b) Descriviu en una frase que` fa aquest algorisme.

2.2 Vaques boges

Temps de vaques boges... A fi devitar que entrin vaquesboges a la cadena alimenta`ria, la Generalitat de Catalu-nya ha decidit posar un codi (nombre enter) a cada vacaper poder distingir vaques malaltes (boges) i vaques sa-nes. Els codis sescullen de tal manera que si una vaca esboja llavors el seu codi es multiple de 13 i de 15. Quanarriba un grup de vaques a lescorxador per ser sacrifi-cades, un operari introdueix a lordinador els codis detotes les vaques i al final posa un 0 com a codi fictici.

Dissenyeu un algorisme que indiqui si hi ha vaques bogesen un grup de vaques.

2.3 El control de qualitat

La cadena de produccio duna fa`brica de components electro`nics vol dissenyar unalgorisme pel control de la qualitat de les peces que fabriquen. Per poder sortir almercat, les peces han de tenir un pes entre 100 i 150 grams. Per aixo`, lempresa volque dissenyeu un algorisme que donada la seque`ncia dels pesos (en grams) dunapartida de peces detecti si totes passen el control de qualitat. La seque`ncia acabaamb un pes fictici 1 que es fa servir com a sentinella.

2.4 Infraccions

La zona de lEixample de Barcelona pateix des de fa temps problemes en les zonesde ca`rrega i desca`rrega degut a les infraccions que hi fan els vehicles de transport.Ba`sicament, shan rebut queixes de que els vehicles superen el temps reglamentaride ca`rrega/desca`rrega. Per aquest motiu, lAjuntament de Barcelona ha installatuns sensors en aquestes zones que cada vegada que surt un vehicle envia a unordinador central lhora dentrada i lhora de sortida del vehicle (en minuts).

Dissenyeu un algorisme que, donada la seque`ncia de dades que envien els sensorsa lordinador central en un dia, acabada amb hores ficticies 1,1 (per lhoradentrada i de sortida respectivament), calculi:

16 Seque`ncies

El nombre total dinfraccions que hi ha hagut al llarg del dia, es a dir elnombre de vehicles que han superat el temps destada ma`xim, que actualmentes de 30 minuts.

El temps destada mitjana.

2.5 Codis de barres

Actualment la majoria de les empreses fan servir els codis debarres per distingir els seus productes. El codi mes este`s i quetendeix a convertir-se en un esta`ndar es lEAN-13. Aquestcodi esta` format per 13 dgits: 12 que es corresponen al codidel producte seguits dun dgit de control. El dgit de controles una part molt important de la codificacio EAN, perque` possibilita leliminaciototal dels errors de lectura del codi. Concretament, el dgit de control es calculaen dues fases:

a) Se sumen els dgits que ocupen una posicio senar multiplicats per 3 i els queocupen una posicio parella (els dgits es numeren de dreta a esquerra).

b) Es resta el resultat de la suma a la desena superior o igual mes propera aaquest resultat.

Per exemple, el dgit de control corresponent al codi 544900000099 es calcularia:

a) 9 3 + 9 + 0 3 + 0 + 0 3 + 0 + 0 3 + 0 + 9 3 + 4 + 4 3 + 5 = 84b) 90 84 = 6

Per tant, el seu dgit de control seria el 6.

Dissenyeu un algorisme que, donat un unic nombre enter que es correspon al codidun producte, calculi el seu dgit de control.

2.6 El supermercat Fruita Madura

El supermercat Fruita Madura vol donar un premi als seus clients mes fidels. Peraixo`, dona als clients 10 punts per cada 100 euros de compra i al client que hagivingut mes dies a comprar li dona 100 punts extres. El premi se lemporta el clientque obte mes punts.

El supermercat mante per a cada client el seu codi, la quantitat deuros que hagastat fins ara i el nombre de dies que ha vingut a comprar. Un mateix clientapareix un unic cop a la seque`ncia.

Dissenyeu un algorisme que, donada la seque`ncia amb la informacio dels clients,indiqui el codi del client a qui pertoca rebre el premi. La seque`ncia finalitza ambun codi de client igual a 1.Per exemple, si lentrada fos

Seque`ncies 17

3 1234.56 12 2 45654.36 145 5 678.97 23 9 23.45 1 1 44743.54 298 34348.76 20 85 287.65 3 789 4567.85 40 -1

a la sortida tindrem que el premi se lemporta el client numero 1. Noteu que elclient que rep els 100 punts extres pot obtenir mes punts que el que ha gastatmes diners i per tant endur-se el premi. Concretament, el client que ha gastatmes diners es el client numero 2 i te 4560 punts, pero` el que ha vingut mes dies acomprar es el client numero 1 que, amb els punts extres, te un total de 4570 punts.

Tant el premi com els punts extres en cas dempat shan de donar al primer clientque apareix a la seque`ncia.

2.7 Productes caducats

Dissenyeu un algorisme que llegeixi una data que representa la data davui i unaseque`ncia delements codiArticle, dataCaducitat i escrigui els codis dels articles jacaducats. La seque`ncia acaba amb codi darticle 0 i data caducitat 0. Els codisdarticles son enters, aix com la data de caducitat, que es representa en formatddmmaaaa.

2.8 El valor actual

El valor actual del benefici duna empresa per als n darrers anys es calcula mit-jancant la formula

B =ni=1

Ii Di(1 + )i1

on:

Ii son els ingressos fets en lany i-e`sim. Di son les despeses fetes en lany i-e`sim. es la taxa dinflacio de lany actual ( 6= 1).

Donat un valor real i una seque`ncia de parells Ii, Di acabada per 0.0, 0.0, dis-senyeu un algorisme que calculi el valor actual del benefici de lempresa, utilitzantnomes una estructura repetitiva i sense fer servir cap funcio primitiva del tipus xy.

2.9 La benzinera de Vilanova

La benzinera mes famosa de Vilanova disposa dun ordinador connectat als seustres sortidors (A, B, i C). El sortidor A serveix benzina super a un preu de 0.897=C/l, el B, super sense plom a un preu de 0.875 =C/l i el C, gasoil a un preu de0.683 =C/l. Cada sortidor te un diposit de 10000 litres, que somple per les nits i, pertant, quan sobre la benzinera esta` ple. Cada vegada que un usuari vol utilitzar unsortidor, marca la quantitat deuros que vol carregar abans de despenjar la ma`nega.En aquest moment el sortidor envia a lordinador el seu codi (cara`cters A, B o

18 Seque`ncies

C) seguit de la quantitat de pessetes. Per acabar el dia, lencarregat introdueixuna F com a codi dun sortidor fictici.

Dissenyeu un algorisme que comptabilitzi la facturacio obtinguda per cada tipusde benzina, que informi sobre el tipus de benzina mes venuda durant el dia, i quesi algun dipo`sit no te un mnim de 100 litres, no permeti seguir servint benzina iho indiqui amb un missatge per tal que lencarregat tanqui la benzinera.

2.10 El pa`rquing de la Mutua de Terrassa

La Mutua de Terrassa vol informatitzar la gestio del seu pa`rquing, el dibuix delqual es dona a continuacio.

E F S T

Barrera EF Barrera ST

Cada vegada que un vehicle arriba a un sensor (E, F, S o T) aquest envia un senyala lordinador de control. El senyal que envia es el cara`cter corresponent al sensor.

Dissenyeu un algorisme per tal que lordinador de control gestioni el funcionamentdel pa`rquing. Per fer-ho, podeu utilitzar les seguents accions que ja han estatdissenyades:

DonarTicket(): emet un ticket amb lhora dentrada per S. ObrirBarreraEF(): obre la barrera EF. ObrirBarreraST(): obre la barrera ST. TancarBarreraEF(): tanca la barrera EF. TancarBarreraST(): tanca la barrera ST. RetornarTicket(): retorna el ticket introdut en S.

El pa`rquing ha de funcionar de la manera seguent:

Quan un vehicle arribi al sensor E, cal lliurar-li un ticket amb lhora dentradai obrir la barrera EF.

Quan un vehicle passi per F, cal tancar la barrera EF.

Seque`ncies 19

Quan sintrodueixi un ticket a S, cal llegir lhora dentrada del ticket, lhorade pagament i lhora de sortida (expressades en minuts) per tal de comprovarsi esta` pagat i si sha fet fa menys de 10 minuts, en aquest cas cal obrir labarrera ST; en cas contrari cal retornar el ticket per tal que el client puguianar a pagar.

Quan el vehicle passi per T, cal tancar la barrera ST.

Al final del dia, un encarregat envia una # com a senyal i cal informar de:

1. Percentatge de vehicles que han estat menys de 60 minuts en el pa`rquing.2. Percentatge de vehicles que han estat entre 60 minuts i 180 minuts en el

pa`rquing.3. Percentatge de vehicles que han estat mes de 180 minuts en el pa`rquing.4. La recaudacio total sabent que el preu del pa`rquing es de 5 ce`ntims per minut.

Se suposa que al principi del dia el pa`rquing es buit.

2.11 El polgon equilateral

Dissenyeu un algorisme que donat un polgon, indiqui si es equilateral. Un polgones equilateral quan totes les seves arestes tenen la mateixa longitud.

El polgon es representa a traves de la seque`ncia dels seus ve`rtexs. Per exemple, siel polgon fos

x1, y1

x2, y2

x3, y3

x4, y4

x5, y5

x6, y6

a lentrada tindrem: x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x1 y1. Noteu quela seque`ncia acaba quan es tornen a introduir els valors corresponents al primerve`rtex.

Utilitzeu

funcio arrel (x : real) : real

per calcular arrels quadrades. Podeu suposar que tot polgon te, almenys, tresarestes.

20 Seque`ncies

2.12 La Pica dEstats

Dissenyeu un algorisme que, donada una seque`ncia den-ters estrictament positius acabada per un 0, digui siconte algun pic mes gran que 3143 (lalcada de la PicadEstats). En concret, lalgorisme ha descriure S si hiha algun pic mes gran que 3143, i N altrament. Unpic es un enter de la seque`ncia que es estrictament mesgran que els seus elements immediatament antecessor isuccessor dins de la seque`ncia. Per exemple, la seque`ncia

21 41 51 32 26 37 37 27 12 31 42 30 0te els dos pics assenyalats. En aquest cas, la resposta a la pregunta ha de sernegativa (cap pic es mes gran que 3143). Podeu suposar que, com a mnim, semprehi ha tres enters a la seque`ncia (sense comptar el 0 final).

2.13 Valls minimals

Donada una seque`ncia S denters positius acabada per un zero, S = s1, . . . , sn, 0,es vol comptar el nombre de valls minimals que conte. Entenem com a valls lessubseque`ncies si, . . . , sj de S que compleixin les condicions seguents:

1 < i < j < n, si = si+1 = = sj , si1 > si, sj < sj+1.

Una vall si, . . . , sj es minimal si per a tota altra vall sr, . . . , st es compleix si < sr.

Per exemple, la seque`ncia

4 2 2 4 5 3 4 3 3 2 2 2 3 0te tres valls, que son les marcades. Gra`ficament:

Per tant, hi ha dues valls minimals, la primera i la tercera. En aquest cas, elresultat del programa per a lexemple donat hauria de ser 2.

Dissenyeu un algorisme que, donada un sequencia denters acabada en zero, comptiel nombre de valls minimals que conte.

Seque`ncies 21

2.14 El torneig de futbol

Dissenyeu un algorisme que llegeixi el nom i la puntuacio dels equips de futbol queparticipen en un torneig, i que escrigui la puntuacio que tenen mes equips junta-ment amb el nombre dequips que tenen aquesta puntuacio ma`xima. Lentrada esuna seque`ncia de noms dequips i puntuacio, ordenada decreixentment per puntu-acio, on el nom de lequip sera` una paraula (una seque`ncia de cara`cters acabadaen un unic cara`cter blanc) i la puntuacio un enter. La seque`ncia acabara` amb elcara`cter #. Per exemple, donada lentrada:

Barcelona 15 Mallorca 8 Racing 8 Vale`ncia 2 Madrid 1 #

lalgorisme ha descriure:

8 2

Podeu suposar que, com a mnim, sempre hi ha un equip a la seque`ncia. Aixmateix, podeu suposar que la seque`ncia esta` ben formada: tot nom dequip portauna puntuacio darrere (enter no negatiu), la seque`ncia efectivament esta` ordenadaper puntuacio, no hi ha cap equip repetit, i mai hi ha mes dun espai separantels elements de la seque`ncia. En cas que hi hagi mes duna solucio, retorneu lapuntuacio mes gran de les empatades; per exemple, donada lentrada:

Barcelona 15 Mallorca 8 Racing 8 Vale`ncia 3 Rayo 3 Madrid 1 #

lalgorisme ha descriure igualment:

8 2

perque`, ate`s lempat entre les puntuacions 8 i 3, la puntuacio mes gran de lesempatades es 8.

22 Seque`ncies

Els telers Jacquard permetien evolucionar els fils dordit dun en un. Elmecanisme que feien servir per fer els prens i deixes de fils dordit erenunes targetes perforades que marcaven el dibuix que sha de fer. El telerJacquard no nomes va tenir una gran importa`ncia en el sector te`xtilals segles xviii i xix, sino en la futura informa`tica: aquesta ma`quinaera programable, en el sentit que podia portar a terme una seque`nciade passos de forma automa`tica.

3Accions i funcions

Exercicis

1. Expliqueu els avantatges de les funcions i les accions.

2. Expliqueu la difere`ncia entre para`metre real i para`metre formal.

3. Expliqueu la difere`ncia entre invocacio (crida) daccions i de funcions.

4. Expliqueu la difere`ncia entre pas de para`metres per entrada, per sortida, iper entrada i sortida.

5. Expliqueu com transformar un funcio en una accio equivalent. Sota quinescondicions es pot transformar una accio en una funcio equivalent?

6. Expliqueu quins errors conceptuals te la funcio seguent i corregiu-la:

funcio Suma (x, y : enter) : entervar s : enter fvarllegir(x, y)s := x+ yescriure(s)retorna s

ffuncio

7. Considereu laccio seguent per a calcular algunes estadstiques de 5 valorsdonats:

accio Estadstiques (ent v1, v2, v3, v4, v5 : real; sort mn,ma`x,mitjana : real)

Digueu quins errors es donen a les seguents invocacions (crides):

24 Accions i funcions

var x1, x2, x3, x4, x5,mn,ma`x,mitjana : real fvar. . .Estadstiques(12.0, 34.0, 56.0, 7.0 + 2.0, 8.0, 1.0, sort mn,ma`x,mitjana)Estadstiques(ent x1, x2, x3, x4, x5, sort mn,ma`x,mitjana)Estadstiques(x1, x2, x3, x4, x5,mn,ma`x,mitjana)Estadstiques(x1, x2, x3, x4, x5,mn, 123,mitjana)

8. Dissenyeu una funcio que, donat un real, retorni el seu valor absolut.

9. Dissenyeu una funcio que, donats dos enters, retorni el ma`xim dambdos.

10. Dissenyeu una funcio que, donats dos enters, retorni el mnim dambdos.

11. Dissenyeu una accio que, donats dos enters, calculi el mnim i el ma`ximdambdos.

12. Dissenyeu una funcio que, donat un enter positiu, retorni el seu factorial.

13. Dissenyeu una funcio que, donat un enter positiu i, calculi li-e`sim numerode Fibonnaci F (i) (vegeu lexercici 11 del captol 2).

14. Escriviu les capcaleres per a funcions o accions que resolguin els problemesseguents. Doneu nomes la capcalera, no les implementeu.

Calcular la suma de dos nombres reals. Calcular el producte de dos nombres reals. Calcular el quocient de dos nombres reals. Calcular el quocient i el residu de dos nombres enters. Calcular larrel quadrada dun nombre real. Resoldre una equacio lineal. Resoldre una equacio de segon ordre. Trobar el valor mes alt duna llista denters. Trobar la mitjana de les notes dels alumnes de la classe. Calcular la dista`ncia entre dos punts del pla`. Calcular la dista`ncia entre dos punts de lespai. Esbrinar si dues lnies son paralleles o sintersecten. Simplificar una fraccio. Decidir si dues fraccions representen el mateix nombre racional.

15. Dissenyeu una accio que, donats dos enters estrictament positius, calculi elseu quocient i residu, sense utilitzar div ni mod.

16. Dissenyeu una accio que intercanvi els valors de dos enters.

17. Dissenyeu una accio que, donat un text acabat en un punt, salti els espais enblanc.

18. Dissenyeu una accio que, donat un text acabat en un punt, salti els espais enblanc i deixi en un para`metre el primer cara`cter no blanc.

Accions i funcions 25

19. Dissenyeu una funcio que, donats dos enters estrictament positius, calculi elseu ma`xim comu divisor.

20. Dissenyeu una funcio que, donats dos enters estrictament positius, calculi elseu mnim comu multiple.

21. Dissenyeu una funcio que, donat un enter, indiqui si es un nombre primer ono.

3.1 No ho se

Considereu laccio seguent:

accio NoHoSe (ent i : enter; ent/sort b : boolea`; sort r : real)si b llavors

si i 0 llavors b := fals sino i := i fsifsir := enterAreal(i)

faccio

Per als algorismes seguents, digueu si la crida es correcta i, en cas que ho sigui,quin sera` el valor que prenen les variables dels algorismes despres de la crida alaccio.

algorisme alg1var x : boolea`; b : real; r : enter fvarx := cert; r := 45; NoHoSe(r, x, b)

falgorisme

algorisme alg2var y : boolea`; c : real; e : enter fvary := fals; e := 22; NoHoSe(e, y, c)

falgorisme

algorisme alg3var x : boolea`; b : real; i : enter fvarx := cert; i := 45; b := NoHoSe(x, i)

falgorisme

algorisme alg4var x : real; i : enter; b : boolea` fvari := 81; b := i mod 3 = 0; NoHoSe(i, b, r)

falgorisme

3.2 Tampoc no ho se

Considereu la funcio seguent:

funcio func (a : enter; b : real; c : cara`cter; d : boolea`) : boolea`a := 3; b := 4.0; c := A; d := fals


retorna no (d o a > 4 i b < 3.5)ffuncio

Per als algorismes seguents, digueu si la crida es correcta i, en cas que ho sigui,quin sera` el valor que prenen les variables dels algorismes despres de la crida a lafuncio.

algorisme alg1var d : enter; c : real; a, x : boolea` fvara := cert; c := 7.0; d := 2; x := func(d, c, 5, a)

falgorisme

algorisme alg2var d : enter; c : real; a, x : boolea` fvara := fals; c := 4.0; d := 8; x := func(d+ 1, c 4.0, Z,no a)

falgorisme

algorisme alg3var d : enter; q : cara`cter; c : real; a : boolea` fvarq := Q; c := 1.0; d := 14; a := func(d+ 1, c 4.0, q, c < 0)

falgorisme

algorisme alg4var d : enter; c : real; a, x : boolea` fvara := fals; c := 4.0; d := 8; x := func(c, d, Z,no a)

falgorisme

3.3 Qui ho sap?

Considereu les accions i lalgorisme seguents:

accio cosa (ent/sort x, y : enter)var z : enter fvarz := x; x := y; y := z

faccio

accio quisap (ent r : enter; ent/sort s : enter)r := r + 1; s := s+ 1cosa(r, s)

faccio

algorisme misterivar a, b : enter fvarllegir(a, b)quisap(a, b)escriure(a, b)

falgorisme

Quina sortida escriu aquest algorisme donada lentrada 3 5?. I quina sortida donaamb lentrada 9 15?. Traduu-lo al llenguatge de programacio C.


3.4 Inco`gnita

Descrivriu que` fa la funcio seguent:

funcio inco`gnita (c : cara`cter) : boolea`retorna c = A i c = E i c = I i c = O i c = U

ffuncio

3.5 Comparar dates

Dissenyeu una funcio CompararDates() que, donats dos enters d1 i d2 que repre-senten dues dates en format ddmmaaaa retorni:

1 si d1 < d2,0 si d1 = d2,1 si d1 > d2.

Per exemple, CompararDates(30031971,29051971) ha de retornar lenter1 perque`el 30 de marc de 1971 es anterior al 29 de maig de 1971.

3.6 Articles caducats

Dissenyeu un algorisme que, donada una data i una seque`ncia darticles escriguiels codis dels articles caducats. Concretament, lentrada de lalgorisme es la dataactual (representada con un enter en format ddmmaaaa) seguida duna seque`nciadarticles, on cada article es representa per una parella CodiArticle,DataCaducitat,on el codi de larticle es un enter i la data de caducitat tambe es un enter en formatddmmaaaa. La seque`ncia acaba amb un article 0, 0, que actua com a sentinella.Per exemple, si lentrada de lalgorisme es:

04032002 99999 09302001 88888 04062002 828 01012002 0 0

el que sha descriure es:

99999 828

El vostre algorisme pot fer servir la funcio CompararDates() definida al pro-blema 3.5, encara que no lhagueu dissenyada.

3.7 Llaunes

Lempresa de supermercats KDolent sha proposat millorar la imatge dels seusmagatzems arreu de Catalunya, amb lobjectiu de vendre el ma`xim nombre deproductes als seus clients habituals i de captar-ne de nous. Assessorats per laconsultoria Artur Centpercent, els dirigents de KDolent volen que, cada mat, elsclients es trobin les llaunes de conserves apilades duna forma que ells consideren


sumament este`tica: La fila de dalt de tot nomes conte una llauna, i cada fila conteuna llauna mes que les que hi ha a la seva fila superior (vegeu dibuix). Per tal depoder fer les comandes als seus provedors, els supermercats KDolent necessitensaber si un determinat nombre de llaunes de conserva es poden o no apilar segonsels criteris de la consultoria.

a) Escriviu una funcio que, donat un nombre positiu que representa el nombrede llaunes, indiqui si es poden apilar o no de la forma descrita.

b) Escriviu un algorisme que llegeixi una seque`ncia denters positius acabada enzero i escrigui, per a cada enter, SI si es apilable i NO si no es apilable.

3.8 Intervals

Dissenyeu un algorisme que, donada una seque`ncia dintervals positius sobre elsreals acabada amb linterval fictici [1.0, 1.0], indiqui quin es el primer intervalque sinclou en linterval [10.5, 17.9].

Per a la solucio del problema, dissenyeu pre`viament una funcio que resolgui elproblema seguent: Donats quatre valors reals a, b, c, d que representen dos intervalsreals [a, b] i [c, d] on a b i c d, indicar si [a, b] [c, d].

3.9 Sumar dgits parells de f(x)

Sigui f(x) la funcio seguent definida sobre el conjunt dels naturals:

f(x) =

{2x+ 1 si x es parell,2x si x es senar.

Donat un valor enter positiu n, dissenyeu un algorisme que calculi la suma delsdgits parells de tota f(x) per als valors x {1, . . . , n}.


3.10 La pesta porcina

Dissenyeu un algorisme que, donada una seque`ncia de cara`cters acabada per unpunt, escrigui la llargada de la paraula mes llarga que contingui alguna lletra P.Si el text no conte cap paraula amb la lletra P, cal escriure 0.

Suposeu que darrera cada paraula hi ha un sol blanc (fins i tot, darrera lultima)i que no hi ha blancs abans de la primera paraula.

Per exemple, per a lentrada

LA PESTA PORCINA NO PERMET EXPORTAR PORCS DE CATALUNYA .

el resultat hauria de ser 8.

3.11 Leibniz i pi

El matema`tic escoce`s James Gregory (16381675) va demostrar al 1671 que

pi = 4 limn

(1 1

3+

15 1

7+ + (1)

n1

2n 1).

Aquesta expansio del nombre pi tambe va ser descoberta al 1673 de forma indepen-dent per Gottfried Leibniz (16461716), inventor duna de les primeres calculadoresmeca`niques.

Una possible manera de trobar una aproximacio del nombre pi consisteix a calcularpik per a valors prou grans de k, on pik es igual a quatre cops la suma dels k primerstermes de la se`rie de GregoryLeibniz.

Dissenyeu un subprograma (accio o funcio) que, donat un valor real > 0, calculiuna aproximacio pik del nombre pi tal que la difere`ncia en valor absolut entre pik ipik1 sigui inferior a .


(a) J. Gregory (b) G. Leibniz

(c) La calculadora de G. Leibniz

3 1415 9265 3589 7932 3846 2643 3832 7950 2884 1971 6939 9375 1058 2097 49445923 0781 6406 2862 0899 8628 0348 2534 2117 0679 8214 8086 5132 8230 6647 09384460 9550 5822 3172 5359 4081 2848 1117 4502 8410 2701 9385 2110 5559 6446 22948954 9303 8196 4428 8109 7566 5933 4461 2847 5648 2337 8678 3165 2712 0190 91456485 6692 3460 3486 1045 4326 6482 1339 3607 2602 4914 1273 7245 8700 6606 31558817 4881 5209 2096 2829 2540 9171 5364 3678 9259 0360 0113 3053 0548 8204 66521384 1469 5194 1511 6094 3305 7270 3657 5959 1953 0921 8611 7381 9326 1179 31051185 4807 4462 3799 6274 9567 3518 8575 2724 8912 2793 8183 0119 4912 9833 67336244 0656 6430 8602 1394 9463 9522 4737 1907 0217 9860 9437 0277 0539 2171 76293176 7523 8467 4818 4676 6940 5132 0005 6812 7145 2635 6082 7785 7713 4275 77896091 7363 7178 7214 6844 0901 2249 5343 0146 5495 8537 1050 7922 7968 9258 9235

(d) Els 700 primers dgits de pi

4Taules

Exercicis

Nota preliminar: La solucio a aquests exercicis ha de definir-se dins daccionso funcions. Podeu introduir accions o funcions auxiliars quan ho cregueuconvenient, aix com definir nous tipus si aixo` us ajuda.

1. Donada una taula denters, calculeu la suma dels seus elements.

2. Donada una taula denters, determineu si un element donat hi apareix algunavegada.

3. Calculeu la suma de dos vectors de N reals.

4. Calculeu el producte escalar de dos vectors de N reals.

5. Expliqueu les difere`ncies entre les dues alternatives per a gestionar taulesparcialment ocupades: finalitzador (sentinella) i longitud.

6. Suposeu que les paraules es representen en una taula de M cara`cters, uti-litzant $ com a finalitzador. Es demana que determineu si dues taules re-presenten la mateixa paraula. Expliqueu doncs perque`, en general, no tenensentit els operadors = i 6= per a taules. Feu el mateix per saber si una pa-raula es menor a una altre (en ordre lexicogra`fic, el del diccionari) i expliqueuperque` no tenen sentit els operadors , i per a taules.

7. Donada una taula de cara`cters parcialment ocupada, determineu si la paraulaque hi ha guardada a la part ocupada es palndroma o no (te els mateixoscara`cters mirada desquerra a dreta que de dreta a esquerra). Per exemple,les paraules anilina o anna son palndroms.

32 Taules

8. Donada una taula de cara`cters parcialment ocupada, determineu si la fraseque hi ha guardada a la part ocupada es sonorament palndroma o no (sonaigual llegida desquerra a dreta que de dreta a esquerra). Considereu que lafrase esta` composta nomes de lletres minuscules i blancs que separen les pa-raules de la frase. Per exemple, les frases tiram ans a la sina, marito a Gava` la gent nega la vaga son sonorament palndromes.

9. Donada una frase acabada per un punt formada nomes per lletres minuscules,determineu quantes vegades apareix cada lletra.

10. Un pangrama es una frase que conte totes les lletres de lalfabet. Donadauna frase acabada per un punt, formada per lletres minuscules i blancs,es demana que calculeu si es o no un pangrama. Per exemple, la fraseanglesa the quick brown dog jumps over the lazy fox i la frase ca-talana jove xef, porti whisky amb quinze glacons dhidrogen sonpangrames.

11. Donada una paraula acabada per un punt, determineu la longitud del seuabece mes llarg. Definim com a abece una seque`ncia de lletres consecutivesde labecedari que apareixin en la paraula. Aix, labece ma`xim de cabraes 3, perque` apareixen la a, la b i la c; mentre que labece ma`xim deferguson es tambe 3, degut a les lletres e, f i g, que supera labeceformat per les lletres r i s, que tambe hi apareixen (els altres abece sonde longitud 1). En calcular els abeces, els repetits no compten.

12. Donades dues taules denters, determineu si luna es permutacio de laltra, esa dir, si conte els mateixos enters apareixent el mateix nombre de vegades.

13. Donada una taula denters de dimensio parell, determineu si tant la se`rie deposicions parelles com la de posicions senars son creixents.

14. Donada una taula de cara`cters que son dgits (xifres), que representa unnombre decimal, calculeu quin es aquest enter representat.

15. Donada una taula denters de N posicions conte nomes els valors 1, 0 i 1 ales seves posicions, i donada una seque`ncia de N enters positius, comproveusi la seque`ncia segueix la forma representada a la taula. Si la posicio k (ambk > 1) de la taula es igual a 1, ha de passar que lelement k-e`sim de laseque`ncia sigui mes petit que el (k 1)-e`sim; si la posicio k de la taula esigual a 1, ha de passar que lelement k-e`sim de la seque`ncia sigui mes granque el (k 1)-e`sim; i si es igual a 0, ha de passar que lelement k-e`sim de laseque`ncia sigui igual que el (k 1)-e`sim.

16. Dissenyeu una accio que, donades dues taules de N elements ordenats cadas-cuna, produeixi una taula amb els 2N elements de les taules tambe ordenats(fusio de taules).

17. Dissenyeu una variant de lalgorisme de fusio de dues taules en que` es per-metin repeticions en les taules de partida, pero` que asseguri que no hi harepetits en la taula de sortida.

Taules 33

18. Repetiu el problema anterior per al cas particular en que` els N elements delconjunt son precisament els enters entre 1 i N , de manera que la representacioes pot simplificar.

19. Quan es volen fer operacions aritme`tiques amb enters molt grans, en lloc du-sar variables de tipus enter es poden representar els enters en una taula, pera evitar problemes de sobreiximent. Definiu un tipus enterGran que permetirepresentar enters de fins a 1000 xifres. A continuacio, feu accions/funcionsper a sumar, restar, multiplicar i dividir (obtenir el quocient) denters grans.Feu tambe operacions de comparacio.

20. Donada una matriu M N , calculeu la suma de tots els seus elements.21. Donada una matriu N N , calculeu la suma dels elements a la seva diagonal

principal. La diagonal principal duna matriu A esta` formada pels elementsAi,i per 1 i N .

22. Donada una matriu M N , calculeu la seva transposada.23. Donades dues matrius M N , calculeu la seva suma.24. Donades dues matrius N N , calculeu el seu producte.25. Donades dues matrius N N , determineu si son iguals.26. Donades dues matrius NN , determineu si son sime`triques (es a dir, si luna

es la transposta de laltra).

27. Donada una matriu M N i una matriu N P , calculeu el seu producte.28. Donada una matriu N N , comproveu si el seu triangle superior dret es ple

de zeros.

29. Donada una matriu M N , comproveu si totes les seves columnes sumenzero. Feu el mateix per a les files.

30. Donada una matriu M N , comproveu si totes les seves columnes tenen lamateixa suma. Feu el mateix per a les files.

31. Donada una matriu N N , comproveu si tots els productes escalars de lafila i-e`sima amb la columna i-e`sima son zero.

32. Es disposa duna retcula de M files i M columnes en la que` un geno-cientficvol estudiar levolucio duna colo`nia de bacte`ries. En cada cella pot haver-hicom a molt un organisme; en conseque`ncia, cada bacte`ria te com a molt 8vens, residents a les celles adjacents a la seva. En el cas de les bacte`riesresidents a les voreres de la retcula, el nombre potencial de vens es encaramenor, ate`s que te menys celles adjacents. La colo`nia va evolucionant con-tinuament degut a naixements i morts dia`ries; lestat de la colo`nia al finaldun dia es funcio de lestat al final del dia anterior. Les regles que regeixenlevolucio de la colo`nia dun dia per laltre son:

34 Taules

Les bacte`ries amb 0 o 1 vens moren per solitud. Les bacte`ries amb 4 vens o mes moren per asfixia. Les bacte`ries amb 2 o 3 vens sobrevieuen. En les celles buides que tenen exactament tres celles adjacents ocupades

per bacte`ries, neix una bacte`ria nova.

Representeu el tipus colo`nia mitjancant una taula bidimensional i Dissenyeuuna accio que es digui Evoluciona() que modifica lestat de la colo`nia segonsles regles anteriors. Intenteu fer laccio sense usar cap taula auxiliar. Perultim, Dissenyeu una accio que simuli levolucio de la colo`nia a partir dunestat donat com a para`metre fins arribar a un estat estable, es a dir, un estattal que en passar dun dia al seguent no hi ha cap naixement ni mort a lacolo`nia (noteu que, en particular, la retcula buida es un estat estable).

33. El departament de Medi Ambient vol iniciar una campanya de recuperaciodels boscos cremats. Per aixo`, shan creat mapes per a cada bosc cremat. Unmapa te forma de matriu gegant on a cada posicio sescriu V per indicar unarbre viu o X per indicar un arbre cremat. El departament de Mediambientconsidera que una fila sha de recuperar si almenys el 70% dels elements dela fila son cremats.

Dissenyeu una accio o funcio que, donada una matriu M N , indiqui quinesfiles shan de recuperar.

4.1 Sobre la taula

Contesteu les preguntes seguents:

a) Donada una taula t: taula[1 .. N ] de enter i un enter x a cercar a la taula,quina o quines propietats de les seguents shan de complir forcosament perpoder aplicar lalgorisme de cerca dicoto`mica de x dins t? Recordeu quela cerca dicoto`mica (tambe dita cerca bina`ria), va dividint la taula en duesparts successivament.

1. Que els enters de la taula t no siguin negatius.2. Que la taula t estigui ordenada.3. Que N no sigui mes gran que 1024.4. Que N sigui una pote`ncia de 2.5. Que x estigui dins de la taula t.

b) Considereu lexpressio a + b div t[k] essent a, b i k tres variables enteres it: taula[1 .. N ] de enter.

Digueu quins errors es poden produir en avaluar lexpressio. Illustreu lexpli-cacio amb exemples, donant per a cada error uns valors a les variables usadesque provoquin lerror.

Taules 35

c) Ordeneu pas a pas el vector seguent, aplicant lalgorisme dordenacio perseleccio. Concretament, dibuixeu sis vegades el vector, una per a cada pasde lalgorisme dordenacio, mostrant el seu contingut.

8 5 6 1 7 3

d) Repetiu la pregunta anterior aplicant lalgorisme dordenacio per insercio.

4.2 Pantans

El departament de Medi Ambient de la Generalitat de Catalunya mante informaciodels seus N pantans daigua (N 50) en forma duna taula on cada componentrespresenta la quantitat (nombre enter) de litres daigua del panta`.

Dissenyeu una accio o funcio que donada la informacio dels pantans ens indiqui si hiha una situacio crtica dels recursos daigua a Catalunya. La situacio es consideracrtica si mes de la meitat dels pantans estan per sota de 10000 litres.

4.3 LAvi Pep

LAvi Pep te un hort rectangular deN perM metres, dividit en parcelles quadradesdun metre quadrat, limtrof pel sud amb un riu. De tota la vida, lAvi ha plantatuna sola classe dhortalisses a cada parcella (de fet, tota la comarca ho fa aix).Les hortalisses que creixen en aquesta comarca son: toma`quets, enciams, bledes iraves; representem cada hortalissa per la seva inicial. Per exemple, la producciode lany passat de lavi, amb N = 6 i M = 4, fou:

r e - e

r e e -

t t r -

- - t -

- - - -

t t r t

6

5

4

3

2

1

1 2 3 4

t: toma`quetsr: ravese: enciamsb: bledes-: res (lliure)

Aconsellat per la seva jove, el Nadal passat, lAvi Pep va decidir adaptar-se als noustemps i va comprar un ordinador per mantenir informacio sobre quines hortalissesestan plantades a quines parcelles. Navegant per la pa`gina de web dUnio dePagesos a lInternet, lAvi Pep sha assabentat que aquest estiu les bledes pujarande preu, i que els toma`quets baixaran. Per aixo`, lAvi vol plantar una filera sencerade bledes, tot suprimint, si cal, tomaqueres (pero` nomes tomaqueres). Pero` comque les bledes necessiten molta aigua i la seva esquena es ressent de portar pesos,

36 Taules

vol que la filera de bledes es trobi el mes a prop possible del riu, que esta` situatjust a sota de la darrera fila.

Dissenyeu un subprograma que, donada una representacio de lhort, digui si hi haalguna filera on es puguin plantar les bledes i, en cas afirmatiu, indiqui tambe aquina fila ha de plantar-les.

En el cas de lexemple, les bledes shaurien de plantar a la fila 3, perque` la fila 3es la mes propera al riu que nomes conte parcelles buides o tomaqueres.

4.4 El pa`rquing

Una gran superfcie comercial ofereix un pa`rquing als seus clients. La informaciosobre locupacio de pa`rquing es mante mitjancant una matriu M N (M 100 iN 100) cada component de la qual es cert si la placa del parking esta` ocupada ifals en cas contrari.

Dissenyeu una accio o funcio que, donada una matriu com abans indicada, calculiel percentatge de places lliures del pa`rquing i la fila mes lliure.

4.5 Vols

La informacio de vols entre ciutats diferents dun pas es dona en una matriu V(N N) de components enteres amb N 50, on N indica el nombre total deciutats i lelement Vi,j de la matriu es el temps de vol per anar de la ciutat origeni a la ciutat dest j. Quan no hi ha vol directe de la ciutat i a la ciutat j, llavorsVi,j val 0.

a) Dissenyeu una accio o funcio que, donada una ciutat origen i, indiqui elnombre de vols que surten daquesta ciutat cap a la resta de les ciutats.

b) Dissenyeu una accio o funcio que, donades una ciutat origen i i una ciutatdest j tals que no hi ha vol directe de i a j, indiqui el vol duna escala peranar de i a j amb temps mnim. Indicar el vol duna escala significa trobarlndex k de la ciutat per on passa el vol. Se suposa que sempre hi ha volsduna escala per anar duna ciutat i a una ciutat j.

Taules 37

4.6 Punt de creu

Lassociacio Tot sobre el Punt de Creu dela Iaia Dolors mante la informacio de ca-dascun dels seus dissenys en una matriu DN M denters on M i N son menors que100. Cada cella daquesta matriu representael codi del color dun punt del disseny (se-gons la carta de colors Anchor). Es a dir,Di,j es el codi del color del punt (i, j) dundeterminat disseny.

Actualment lassociacio rep moltes peticionsde dissenys que es puguin fer amb nomes doscolors concrets i, per aixo`, la Iaia Dolors us ha encarregat que dissenyeu una accioo una funcio que, donat un disseny (una matriu) i els codis de dos colors (dosenters), indiqui si el disseny es pot fer utilitzant nomes aquests dos colors.

4.7 Vector suma columnes

Donada una matriu A de M files i N columnes de components reals i un vectorv de N components reals, dissenyeu una accio o funcio que indiqui si el vector ves igual a la suma de totes les columnes de la matriu, o sigui si, per cada j, amb1 j N ,

vj =Mi=1

Ai,j .

Aqu, el primer ndex de la matriu indica la fila i el segon ndex indica la columna.

Per exemple, si la matriu A fos:

-1 2 3 120 4 7 131 1 0 0

i el vector v fos 0 7 -1 25 , llavors la resposta seria negativa.

4.8 Files i columnes perpendiculars

Donada una matriu quadrada A (N N) amb N 50 de components enters,dissenyeu una accio o funcio que indiqui el nombre de parelles fila, columna queson perpendiculars. Una fila i es perpendicular a una columna j si el producteescalar entre elles es igual a zero, es a dir, si

Nk=1

Ai,k Ak,j = 0.

38 Taules

4.9 Numeros binaris

Es volen sumar i restar enters no negatius representats en binari. Lexpressio aavaluar resideix en una taula bidimensional de zeros i uns, on cada fila representauna operacio a efectuar; la taula te N files i cada fila nou dgits zeros o uns. Elprimer dgit de la fila representa loperacio (0: suma; 1: resta), i els altres vuitrepresenten lenter en base 2. Com a excepcio, el primer 0 o 1 de la primera fila note cap significat. Un exemple de taula seria el seguent (posem al costat el significatde cada fila):

000010011 . valor 19; el primer dgit no es mira001110000 . shi suma 112100000011 . shi resta 3000011111 . shi suma 31

Lexpressio de la taula savalua de la manera seguent: partint del numero de laprimera fila, es van aplicant ordenadament les operacions que hi ha des de lasegona fila fins a la fila N , obtenint un resultat final. Es considera un error si, enel transcurs del ca`lcul, apareix un numero negatiu, o be es manipula un numeropositiu mes gran que 255, que es el valor ma`xim que es pot representar amb 8 bits.

Dissenyeu una accio que, donada una taula com lanterior, retorni dos resultats:un boolea` per saber si hi ha hagut error o no en el ca`lcul; i el resultat de loperacio,en cas que no hi hagi hagut error, expressat mitjancant un enter. Per a lexempleanterior, el resultat hauria de ser:

El boolea` cert (no hi ha hagut cap error). Lenter 159.

4.10 El valor propi

Donada una matriu quadrada A (N N) de components reals i un vector v de Ncomponents reals, dissenyeu una accio o funcio que indiqui si el vector u = A v esproporcional al vector v, es a dir si hi existeix un valor tal que

u1v1

=u2v2

= = uNvN

= .

El valor de proporcionalitat es diu valor propi de la matriu A associat al vector v.Recordeu tambe que el vector u = A v (producte de la matriu A pel vector v) esfa de la manera seguent: la seva component i-e`sima ui es el producte escalar de lafila i-e`sima de A pel vector v, es a dir:

ui =Nk=1

Ai,k vk.

Podeu suposar que no hi ha cap 0 en v.

Taules 39

4.11 La planificacio de tasques

En una empresa han dexecutar-se diverses tasques. Cada tasca te associada unadurada expressada en minuts, i exigeix de ser executada per un treballador determi-nat, identificat per un enter entre 1 i N . Un treballador pot tenir la responsabilitatdexecutar diverses tasques, i en aquest cas ho fa sequencialment: quan acaba unatasca, pot comencar immediatament la seguent.

Feu un algorisme que llegeixi una seque`ncia de tasques, essent cada tasca un parelldenters durada, treballador, i que digui quants minuts son necessaris per execu-tar el total de tasques, ateses les durades de les tasques i els treballadors que leshan dexecutar, i recordant que un treballador no pot estar executant mes dunatasca a la vegada. Suposeu que la seque`ncia acaba amb un parell 0 0.

4.12 La suma per capes

Donada una matriu quadrada N N denters, dissenyeu una accio que calculi laseva suma per capes, es a dir, un vector que conte: a la primera posicio, la sumadels elements de la primera capa de la matriu; a la segona, la dels de la segonacapa, etc. Entenem com a capa k-e`sima duna matriu les posicions que es trobena dista`ncia k 1 de la fila o columna mes externa. Gra`ficament:

...

Capa 1

Capa 2

Per exemple, la suma per capes de la matriu

1 2 3 4 5 47 3 2 1 5 15 7 8 1 2 11 3 6 2 0 25 6 9 2 1 27 1 2 2 1 3

es el vector

59 41 17

40 Taules

4.13 El monitor MonocromTM

El MonocromTM es un monitor en blanc i negre de pantalla quadrada formada peruna retcula de N N pxels, cadascun dels quals pot estar de color blanc o decolor negre. Per simplificar el problema, suposarem que N es una pote`ncia de 2.

El monitor mostra les figures a partir de certes ordres que rep en forma de seque`nciade cara`cters; els cara`cters enviats actuen no sobre tota la pantalla, sino nomessobre una a`rea seleccionada, que pot canviar-se mitjancant aquests cara`cters. Ini-cialment, la`rea seleccionada es tota la pantalla i els seus pxels estan de colorblanc. El cara`cter x serveix per pintar la`rea seleccionada (es a dir, posar totsels seus punts de color negre) i, immediatament, tornar a considerar com a a`reaseleccionada la pantalla sencera. Finalment, els cara`cters del 1 al 4 serveixen perfer mes petita la`rea seleccionada, de manera que posteriors cara`cters x afectinmenys punts. Concretament, aquests cara`cters restringeixen la`rea seleccionada aun dels seus quatre quadrants: 1: superior esquerre; 2: superior dret; 3: inferiordret; 4: inferior esquerre.

Aix, el MonocromTM nomes serveix per pintar un o mes quadrats; qualsevol figuracomplexa ha de pintar-se a trossos, seleccionant i pintant els quadrats adequats.Per dibuixar una figura com la que apareix a continuacio, que te N = 16, cal donaren qualsevol ordre les seque`ncies de cara`cters seguents:

Per al quadrat petit del ve`rtex superior dret: 2222x Per al quadrat gran del ve`rtex inferior dret: 3x Per al quadrat mitja` de lesquerra: 113x

Per tant, les sis seque`ncies possibles de cara`cters que generen aquesta figura son:

2222x3x113x. 2222x113x3x. 3x2222x113x.3x113x2222x. 113x2222x3x. 113x3x2222x.

Dissenyeu un algorisme que, donada una seque`ncia de cara`cters acabada per unpunt, sigui capac de generar una figura segons les regles anteriors.

Taules 41

4.14 La codificacio de missatges

Lagent secret 007 es en una perillosa missio secreta contra undolent molt dolent en un pais llunya` amb la companyia de noiesespectaculars. Davant la necessitat denviar missatges a la seucentral dels serveis secrets de Sa Majestat (de la qual en sou el cap del departamentdinforma`tica), 007 segueix un procediment pre-establert per codificar-los.

Per codificar un missatge (acabat per un punt), 007 deixa les tires de vocals con-secutives inalterades, mentre que les tires de no-vocals les manipula en dos passos:primer, les capgira i, a continuacio, mou els cara`cters que ocupen posicions parellsdins de la tira capgirada, darrere dels que hi ocupen posicions senars. Aix, la tirade no-vocals BCDFGHJ es converteix en JHGFDCB despres de la primera mani-pulacio i en JGDBHFC despres de la segona. Amb aquesta estrate`gia, el missatge:

El meu nom es: Bond, James Bond.

es codifica com:

Em leun o meB :soJ ,dnameB sodn. despres de capgirarEml eun o meB: soJ,n dameBs odn. despres de moure

Noteu que els blancs tambe es tracten com a cara`cters no-vocals.

Per descodificar amb seguretat i rapidesa els missatges enviats per 007, el capdels serveis secrets de Sa Majestat us encarrega la construccio dun algorisme que,donat un missatge codificat, lescrigui descodificat. La longitud ma`xima duna tiraconsecutiva de no-vocals es 20 (per culpa dels noms islandesos).

4.15 Generacio de permutacions

Dissenyeu un algorisme que generi totes les cadenes de N bits comencant per la000 . . . 0

N

fins a la 111 . . . 1 N

, ordenadament segons la seva interpretacio com a nom-

bres binaris. Per exemple, per a N = 3: 000 001 010 011 100 101 110 111.

4.16 El segment nul mes llarg

Sigui una taula denters t de N posicions. Definim un segment de la taula comun tros consecutiu del vector, es a dir, un tros que va des duna posicio x a unaposicio y tals que 1 x y N . Direm que un segment de la taula es nul si lasuma dels enters que hi ha a les seves posicions es 0. Dissenyeu un algorisme quecalculi la longitud del segment nul mes llarg duna taula t.

Per exemple, donat el vector de la figura seguent, la resposta hauria de ser 4,perque` el segment nul mes llarg es el que va de la posicio 2 a la 5. Hi ha altressegments nuls mes curts, com ara el que va de la posicio 4 a la 6.

1 2 3 4 5 6 7 81 8 5 4 1 3 7 0

42 Taules

Ada Byron Lovelace, filla del poeta brita`nic Lord Byron, es consideradacom la primera persona que va programar ordinadors al interessar-sepels projectes de C. Babbage. La contessa de Lovelace va ser musica,matema`tica i mare de tres fills. Nascuda lany 1815, va morir prematu-rament als 36 anys. En el seu honor, hi ha un llenguatge de programacioanomenat Ada.

5Tuples i estructures de dades

Exercicis

1. Definiu un tipus a mantenir la informacio sobre una hora del rellotge (hora,data i segons).

2. Definiu un tipus a mantenir la informacio sobre una data (dia, mes i any).

3. Definiu un tipus tComplex per a manipular nombres complexos. Escriviufuncions per calcular la suma, resta, i producte de dos complexos.

4. Definiu un tipus tRacional per a manipular nombres racionals. Escriviufuncions per calcular la suma, resta, producte i divisio de dos racionals.

5. Utilitzeu el tipus tRacional de lexercici anterior per dissenyar una funcio queindiqui si dos racionals son iguals. Expliqueu doncs perque`, en general, notenen sentit els operadors = i 6= per a tuples. Feu el mateix per saber si unracional es menor a una altre i expliqueu perque`, en general, no tenen sentitels operadors , i per a tuples.

6. Definiu un tipus tPunt per a mantenir les coordenades dun punt a la pantalladun ordinador. A partir dell, definiu un tipus tFinestra per a mantenir latalla i posicio duna finestra rectangular (amb els seus costats parallels alsde la pantalla). Escriviu una funcio per saber si un punt donat es troba dinsduna finestra donada.

7. Definiu un tipus tPunt per a mantenir les coordenades dun punt a lespai.Dissenyeu una funcio que donats dos punts calculi la dista`ncia de lun alaltre. Utilitzeu

44 Tuples i estructures de dades

funcio arrel (x : real) : real

per calcular arrels quadrades.

8. Utilitzant el tipus tPunt de lexercici anterior, definiu un tipus tRecta pera mantenir la informacio duna recta, passant per dos punts diferents. Dis-senyeu una funcio que, donades dues rectes, digui si son la mateixa, si sonparalleles o si sintersequen.

9. Definiu un tipus enumerat pels possibles estats dun sema`for.

10. Definiu un tipus enumerat per lestat cvil duna persona (solter, casat, di-vorciat, separat, vidu).

11. Definiu un tipus enumerat pels dies de la setmana.

12. Una taula de 100 posicions indica quin dia de la setmana cal regar cada plantadun hivernacle. Usant el tipus enumerat de lexercici anterior, dissenyeu unaaccio que llisti els numeros de les plantes que avui cal regar.

13. Una botiga de discos vol informatitzar el seu cata`leg. La botiga compta ambun fons de com a molt 10000 discos diferents. Per a cada disc, es vol saberla seva categoria, el seu ttol, el seu compositor, el seu inte`rpret, el nombredunitats en estoc i el seu preu. Les categories possibles son: simfonia, o`pera,concert per a piano o quartet de cordes. Tots els textos tenen com a molt100 cara`cters.

Dissenyeu les estructures de dades necessa`ries. Dissenyeu una accio que llisti tots els ttols duna categoria donada. Dissenyeu una funcio que compti quantes unitats hi ha en estoc per a

un compositor i un preu ma`xim donats.

14. Podem representar els polinomis

Informática Básica

Documents

Transcript of Informática Básica