|
|
|
Fonaments de programació.
Llenguatge C/C++ |
|
|
Projecte fi de curs. Propostes |
|
|
|
|
1. Sopa de
lletres Aquest
projecte es basa en la pràctica d'ampliació del mòdul 6. Es tracta de fer un
programa que permeti construir sopes de lletres i buscar paraules en una sopa
de lletres definida prèviament. El programa
tindrà dues parts: 1.
Construcció de sopes de lletres. ·
Aquesta opció demanarà a l'usuari la dimensió de
la taula (que pot no ser quadrada) i el nombre de paraules a amagar. El
nombre de files i de columnes de la taula, i el nombre de paraules a amagar,
no serà en cap cas superior a 50. ·
L'usuari haurà de decidir on vol amagar la
paraula. Una vegada introduïda la paraula, haurà d'indicar la fila i columna
de la primera lletra de la paraula i la direcció de lectura amb el següent
conveni: o hd
horitzontal d'esquerra a dreta. o he
horitzontal de dreta a esquerra. o vb
vertical de dalt a baix. o vd
vertical de baix a dalt. o db
diagonal d'esquerra a dreta i de dalt a baix. o dd
diagonal d'esquerra a dreta i de baix a dalt. o eb
diagonal de dreta a esquerra i de dalt a baix. o ed
diagonal de dreta a esquerra i de baix a dalt. Per exemple: programa 0 0
db
·
Una vegada introduïda la paraula, la posició de
la primera lletra i la direcció, el programa haurà de comprovar si és
possible, és a dir, si la paraula cap en el tauler i si és compatible amb les
paraules introduïdes amb anterioritat. ·
Una vegada introduïdes totes les paraules, el
programa omplirà les posicions buides amb lletres a l'atzar. ·
S'ha de permetre guardar una sopa així construïda
en disc. L'arxiu ha de contenir la dimensió, la llista de paraules que estan
amagades i tota la taula. L'arxiu no guadarà la posició ni la direcció
on s'amaguen les paraules. 2. Cerca de
paraules ·
Aquesta serà la part similar a la pràctica
d'ampliació del mòdul 6. El programa haurà de llegir un arxiu en el mateix
format comentat abans. ·
Una vegada que es trobi la sopa de lletres en
memòria haurà de cercar les paraules en les 8 direccions possibles i mostrar
en pantalla la llista de paraules amagades i la sopa de lletres amb les
paraules amagades en majúscules. 2.
Laberints Aquest
projecte està basat en un dels exercicis de la 1ª Pre-Olimpíada Informàtica
Catalana que es va celebrar a Barcelona el 21 d'abril de 2001. Considerem un
taulell quadriculat com el de la figura en el qual cada casella està
representada per les seves coordenades (fila, columna). En aquest
taulell hi podem trobar algunes caselles negres com les caselles (0,0) i
(1,2). De les
caselles que no són negres, hi ha dues que s'han representat d'un color
diferent i s'han marcat amb les lletres A i B. A representarà la casella inicial
i B la casella final. Es tracta de
cercar un camí, sense passar per caselles negres que ens porti de la casella
A a la casella B. Els camins poden unir dues caselles no negres que tinguin
un costat o un vèrtex comú, és a dir, podem considerar camins horitzontals,
verticals o en diagonal. El programa podria millorar-se si pogués trobar el
camí que satisfaci alguna d'aquestes dues condicions: 1.
Que passi per un nombre mínim de caselles. 2.
Que contingui un nombre mínim de traços rectes. A
l'exemple del dibuix, el camí trobat conté 4 traços: horitzontal, diagonal,
vertical i, de nou, horitzontal. En aquesta
figura pot semblar que el programa no serà molt interessant, però proveu amb
un tauler de 50 x 50 caselles i veureu com a ma (sense ajuda del programa) no
serà fàcil trobar el camí més curt entre dues caselles.
La forma
d'introduir les dades pot triar-se lliurement d'entre vàries possibilitats.
Una d'aquestes possibilitats es fer servir un arxiu d'entrada i un arxiu de
sortida. L'arxiu d'entrada tindrà la següent informació: 1.
Nombre total de files. 2.
Nombre total de columnes. 3.
Nombre total de caselles negres. 4.
Coordenades de les caselles negres. 5.
Coordenades de les caselles inicial i final (A i
B). 6.
Si s'escau, algun paràmetre que indiqui quin camí
ha de buscar: un camí qualsevol, un camí amb un mínim de caselles o un camí
amb un mínim de traços. L'arxiu de
sortida contindrà la llista de totes les caselles del camí trobat començant
per la casella A i acabant per la casella B. En el cas que el camí no sigui
possible, també l'haurà d'indicar. 3.
Comparació d'algorismes d'integració numèrica Quan es
trobem amb el problema del càlcul d'àrees limitats per funcions contínues ens
veiem obligats a calcular integrals d'aquestes funcions. Molts altres
problemes que aparentment no tenen res a veure amb el càlcul d'àrees també es
poden resoldre amb el càlcul d'integrals definides. En molts casos no és
possible un càlcul analític exacte d'aquestes inte grals i ens
veiem en l'obligació de recórrer a un mètode numèric. En aquest projecte es
proposa implementar els algorismes més coneguts de càlcul numèric d'integrals
i fer una comparació d'aquests en quant a temps de càlcul i precisió. Mètode dels
rectangles El primer i
més intuïtiu dels mètodes numèrics d'integració és el mètode dels rectangles
que consisteix en aproximar l'àrea tancada per la funció que volem integrar i
l'eix d'abscisses per una suma d'àrees de rectangles.
Per això es
divideix l'interval d'integració [a,b] en n parts iguals de
longitud (b-a)/n i s'agafen els rectangles que tenen com a base
cadascú d'aquests subintervals i d'alçada la imatge de la funció en el extrem
esquerre ( o dret). Les fórmules són:
Mètode dels
trapezis Aquest mètode consisteix en aproximar l'àrea no per rectangles sinó per
trapezis, tal i com es pot observar a la figura:
L'àrea d'un
trapezi de bases f(xk) i f(xk+1) i
distància entre bases (b-a)/2 és igual a:
La suma de
totes aquestes àrees és:
Es pot
comprovar molt fàcilment que el mètode dels trapezis dóna la mitjana
aritmètica dels valors (I) i (II) del mètode anterior. Mètode de
Simpson El mètode de
Simpson consisteix en aproximar la funció per arcs de paràbola determinats
per tres punts consecutius.
Després d'un
desenvolupament una mica més llarg que en els mètodes anteriors es pot trobar
que :
Per tal de
fer servir el mètode de Simpson és necessari que n sigui parell. Es pot fer
que la introducció de la funció es pugui fer de dues formes: ·
Un arxiu amb els valors tabulats de la funció. És
necessari en aquest cas aquestes dades: o extrem
esquerre (a) o longitud
del subinterval ((b-a)/n) o llista
dels n+1 valors f(xk) ·
Una funció externa que es pugui modificar i
tornar a compilar cada vegada. Aquesta funció començaria: double f(double x){
return (..); } En aquest últim cas és necessari la
introducció del valor n. 4.
Comparació d'algorismes d'ordenació Com a
ampliació de la pràctica d'ampliació 2 del mòdul 3, es proposa en aquest
projecte cercar més informació sobre els diferents mètodes d'ordenació i fer
una aplicació C/C++ que mostri de forma comparada els dos mètodes ja
explicats més un o dos mètodes més. Es recorda
que els mètodes que es van tractar en la pràctica d'ampliació 2 del mòdul 3
són els mètodes de la bombolla i el de selecció.
A més es podria estudiar i implementar un mètode d'ordenació per inserció.
Aquest últim consisteix en ordenar les dades inserint els elements en una
estructura ja ordenada de dades. A més
d'aquests tres mètodes simples, es podria considerar també els següents
mètodes més sofisticats: Ordenació Shell i Ordenació
ràpida (QSORT). El projecte
no consistiria només en la implementació dels tres o quatre algorismes
d'integració sinó que ha de permetre fer un estudi comparatiu de tots tres o
tots quatre. Aquest estudi ha de consistir en: ·
Velocitat de l'ordenació en un cas promig. ¿Com
augmenta aquesta velocitat al augmentar el nombre de dades? (Només un estudi
experimental) ·
Velocitat en el pitjor i el millor dels casos. ·
¿Té l'algorisme un comportament natural o antinatural?
Es diu que un algorisme té un comportament natural si treballa poc si la
llista està gairebé ordenada. 5.
Analitzador d'expressions aritmètiques en notació polonesa. Les piles Una pila
és un tipus d'estructura de dades que fa servir el mètode d'accés LIFO (Last
in, first out), és a dir, la última dada en entrar és també la primera en
sortir. Podem imaginar una pila de plats que es posen un a sobre d'un altre.
El primer plat, el que es troba a sota de tot, és l'últim en fer-lo servir, i
el de sobre, l'últim que es va posar, és el primer en fer-lo servir. Les piles es
fan servir molt en software de sistemes. El mateix compilador de C fa servir
una pila per passar arguments a funcions. Les úniques
accions que es poden fer amb una pila és afegir una dada, que
es posarà a sobre de tot, i treure una dada, que s'agafarà de
sobre de tot. Una aplicació
útil i senzilla alhora de les piles són els analitzadors d'expressions en
notació polonesa. Aquesta és la lògica operacional típica de les calculadores
de la marca HP. L'avantatge
principal d'aquest mètode és que no es necessita parèntesis ni la necessitat
de suposar cap prioritat entre les operacions. Aquest sistema fa que es
minimitzi tant el nombre de tecles presses com el nombre real d'operacions. Per tal
d'explicar aquest mètode operacional imaginem que hem de fer aquesta
operació: 3+4*5 Aquesta
expressió s'introduiria com: 3, 4, 5, *, + o bé: 4, 5, *, 3, + Aquestes dues
expressions només contenen números, els símbols d'operació :+ *, i el símbol
, (coma) que separa els diferents tokens. El programa
analitzador d'aquesta expressió comença llegint l'expressió pel caràcter de
l'esquerra i fa el següent: ·
Si és un número l'escriu a la pila. ·
El caràcter ',' serveix per separar dos tokens
diferents. (s'anomena token a un número o un operador) ·
Si és un símbol: +, -, *, / fa l'operació binària
corresponent, esborra els dos operadors i posa el resultat corresponent a la
pila. Per tal de
distingir entre l'operador binari '-' que representa la resta i l'operador
unari '-' que representa canviar el signe, aquest últim operador sempre anirà
a l'esquerra del número sense separar per comes. També pot ser útil reservar
un símbol diferent per aquest operador, com pot ser 'n'. Exemple: -3+(2*(-5)) seria: -3,2,-5,*,+ o: 3,n,2,5,n,*,+ Per tal de
veure el funcionament de l'analitzador veurem el contingut de la pila amb la
següent expressió: 3, 4,5, *,+
Veiem un
exemple una mica més sofisticat:
3,3,2,4,+,*,-,3,5,-,/,1,2,/,+,2,1,3,1,-,/,+,/
Es pot veure que és molt fàcil
avaluar expressions d'aquests tipus, només fa falta que el programa pugui
extraure els tokens de l'expressió que estan separats per comes. Si el
token és un número ha de cridar a una funció que afegeixi aquest número a la
pila. Si el token és un operador (per simplificar només considerarem +,-,*,/)
fa l'operació binària amb els dos últims números emmagatzemats en la pila i
els substitueix pel resultat, per tant, en cada operació, el nivell de la
pila baixa en una posició. Feu que el programa pugui llegir del
teclat o d'un arxiu una expressió aritmètica i doni el resultat. Podeu perfeccionar aquest senzill
analitzador d'expressions afegint altres operadors binaris com l'exponenciació
i unaris com funcions trigonomètriques, logarítmiques i exponencials. Podeu
permetre també l'ús de variables (de moment una o dues variables serà
suficient). Si l'analitzador troba el nom d'una variable afegeix a la pila el
contingut d'aquesta variable. L'objectiu final d'aquest projecte
podria ser construir un programa que, donada una funció que es pot introduir
per teclat o mitjançant un arxiu pugui tabular la funció entre dos valors
determinats i amb un increment determinat. Per exemple: Si volem tabular la funció: entre els valors 0 i 1 amb un
increment 0.1: Les dades serien: ·
Funció:
x,x,*,n,exp,x,x*,exp,+,2,/ ·
dada inicial:
0 ·
dada
final: 1 ·
increment:
0.1 L'avantatge dels analitzadors
d'expressions és que no és necessari haver de compilar el programa de nou per
tabular una altra funció. 6. Anàlisi criptogràfic d'un
missatge. Substitució monogràfica. Els mètodes elementals de
criptografia consisteixen en substituir unes lletres per unes altres. Si la
substitució es fa lletra a lletra i el missatge és suficientment llarg com
per tenir unes freqüències de símbols significatius, la comparació d'aquestes
freqüències amb les freqüències de les lletres en el idioma en que està
escrit el missatge ens permetrà desxifrar-lo. Un conjunt de programes per tal
d'obtenir missatges xifrats i desxifrar-los seria un senzill projecte que
podria desenvolupar-se de la següent forma: Un programa que permeti xifrar
missatges. El programa podrà optar per diferents opcions: ·
Xifrat Juli Cèsar (fa falta introduir un número). ·
Xifrat monoalfabètic determinat (fa falta
introduir la correspondència de cada lletra. Aquesta serà la clau i es pot
introduir mitjançant un arxiu que contingui una permutació qualsevol de les
27 lletres) ·
Xifrat monoalfabètic aleatori (la clau la
decideix aleatòriament el programa i no la mostra, per tant serà una bona
forma de provar els programes per desxifrar. En qualssevol cas, la llargada del
missatge ha de ser suficient per tal de que les freqüències de les seves
lletres siguin significatives (mínim 1000 lletres). Un programa que permeti obtenir les
freqüències de les diferents lletres de qualsevol text en format ASCII.
Aquest programa ens servirà per determinar la freqüència de les lletres en el
idioma dels textos. Amb aquest programa es pot estudiar si aquestes
freqüències depenen no només de l'idioma sinó també del tipus de text, de
l'autor, de l'època, del tema, etc. Amb aquest programa determinarem tant
les freqüències de les lletres en el idioma determinat sinó també les
freqüències de les lletres en el missatge xifrat. Aquestes freqüències
sortiran en un arxiu que servirà d'entrada pel tercer programa. El tercer programa agafarà com a
dades el text xifrat i les freqüències trobades de les lletres en el idioma i
el el missatge. S'ha de cercar alguns criteris automàtics de substituir
lletres amb freqüència similar i intercalar-los amb criteris manuals. 7. Anàlisi criptogràfic d'un
missatge. Substitució digràfica. Una variant d'aquest mètode de
substitució consisteix en agrupar les lletres de dues en dues i substituir
cada grup de dues lletres per un símbol que habitualment és un altre conjunt
de dues lletres. El primer que s'ha de fer per
desxifrar un missatge xifrat amb aquest mètode és disposar d'una taula de
freqüències de tots els parells de lletres. La primera part d'aquest projecte
serà per tant, construir un programa que permeti comptabilitzar aquestes
freqüències pels 27x27=729 parelles possibles de dues lletres. S'ha de
disposar abans d'un conjunt de textos suficients per tal d'obtenir unes dades
significatives. Aquests textos estaran en format ASCII. Això és pot fer amb
qualsevol processador de textos com Word o AmiPro. Una vegada es disposi d'aquesta taula
de freqüències, s'ha d'establir també una taula de freqüències dels parells
de lletres del missatge xifrat. Això es farà amb el mateix programa anterior. Després s'ha de fer un programa que
permeti substituir unes seqüències de lletres per unes altres. Podeu
establir, com en la proposta anterior, alguns criteris automàtics i
alternar-los amb criteris manuals. Evidentment falta un tercer programa
que pugui xifrar un text amb aquest mètode. Aquest programa és necessari per
tal d'obtenir un missatge a desxifrar. Busqueu formes d'indicar com fer
aquesta substitució (fórmules de qualsevol forma) i també és possible una
correspondència a l'atzar. 8. Joc de les dites. Una variant d'aquest mètode de
substitució consisteix en agrupar les lletres de dues en dues. El joc consisteix en endevinar
una dita amagada a sota de les cel·les d’un taulell de 5 fileres per 20
columnes. El jugador pot indicar caràcter
a caràcter o be si creu que ja la sap, escriure la dita sencera. En funció del temps emprat el
programa donarà una puntuació de 0 a 10. El programa ha de permetre: A) Jugar B) Introduir
una nova dita. C) Respondre
caràcter. D) Respondre
tota la dita
Les dites es
troben emmagatzemades dins l’arxiu “dites.dat” . Dins l’arxiu
una dita acaba en “.*” i el
final del fitxer amb “.*/”
Exemple
d’arxiu dites.dat L'abril mullat
fa créixer l'herba per al ramat.*Per l'abril neteja les armes i mata
les rates.*Abril finit el camp florit.*No t'embarquis per l'abril si
no vols estar en perill.*Per l'abril, abriló ous al ponedor.*Per l'abril
cada gota val per mil i el blat s'estira com un fil.*Abril,abriló de
cada cent, un de bo la vella que això deia en tenia cent un i no n'havia
vist mai ni un.*No hi ha mal any si l'abril és bo.*L'abril diu al maig
jo no he pogut tu plou a raig.*Abril ploraner maig rialler.*Abril finit
hivern passat.*No donis l'hivern per passat fins que l'abril no s'hagi
acabat.*Per l'abril no et treguis ni un fil.*Per l'abril cada ocell
canta en son niu.*A l'abril aigües mil.*D'abril un de bo entre mil.*Per
l'abril, llibres i roses mil.*Rient i plorant, l'abril va passant.*/ 9. Joc del set i mig. És un joc prou conegut per tots. El programa va repartint una a una les
cartes als jugadors i a ell mateix
que fa de banca. En el seu torn, el jugador fa una aposta i demana carta o es planta. Si
es planta el torn passa al següent jugador. Si desitja demanar carta
el programa mostrarà (en el nostre cas el número, no la figura) l’última
carta d’aquest jugador. Quan es demana carta o al plantar-se es pot fer una
nova aposta sense passar un límit que posarà el programa.
1. El
valor total de la carta superi set punts i mig. En aquest cas el jugador ha
perdut i la seva aposta se la queda la banca i les seves cartes van al munt
de les cartes per poder ser utilitzades. Després d’acabar el torn dels jugadors arriba el
torn de la banca.
En tot moment en el monitor es mostraran les següents
dades: . Saldo actual de cada jugador. . Aposta de la jugada. Després
de la jugada s’hauran d’actualitzar les dades *Es pot genera un numero
aleatori 0 , 1 de tal forma que si surt 0 no demana i cas contrari si surt 1
. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
