Quien me AYUDA :_(
_Catwoman_
14 de Febrero del 2005
Quien me ayuda hacer este programa? si hay algo del enunciado que no se entienda preguntarme wapoooooooosss :)
La present pràctica proposa que donat un laberint (en un format especificat més avall), l'aplicació ha de determinar si existeix, o no, un camí des de la marca de Entrada fins a la de Sortida. Si efectivament existeix, l'aplicació ha de mostrar el camí recorregut (en cas que hi hagi més d'un camí, tan sols cal mostrar-ne un qualsevol) marcant-lo sobre el format del laberint original.
Fomat del Laberint
El laberint serà codificat com una matriu de MxN caracters en un arxiu ASCII anomenat "laberint.txt". El laberint estarà format per parets, passadissos, una única entrada i una única sortida.
Parets: el caracter "#" serà el que ens servirà per a definir on hi ha paret. Les parets poden tenir el gruix que es desitgi.
Passadís: el caracter " " (espai) serà el que definirà els passadissos per on es pot recòrrer el laberint. Aquests passadissos sempre seran de 1 sol caracter d'amplada. A més, en les cruïlles, tan sols tindran continuitat vertical i/o horitzontal (el que es coneix com "connectivitat a 4"), però mai diagonal. És a dir, l'exemple (1) sí presenta continuitat, mentre que el (2) no:
##### #####
## ## # # #
# # ## ##
## ## # # #
##### #####
(1) (2)
Entrada: aquesta vindrà marcada pel caracter "E" i sempre estarà situada en algún punt de la paret inferior del laberint, excepte les cantonades.
Sortida: aquesta vindrà marcada pel caracter "S" i sempre estarà situada en algún punt de la paret superior del laberint, excepte les cantonades.
Així doncs, un exemple de laberint seria:
#####S###
# # #
# ##### #
# # #
# # # # #
# # # #
## # # #
##E######
Aquest laberint té una mida 8x8, però no tots han de ser necessàriament quadrats. En aquest cas, el programa diria que SI existeix un camí des de l'entrada fins la sortida i per tant hauria de donar com a resultatel següent laberint amb el camí marcat amb el caracter "·" (punt volat, el que está situat habitualment en el teclat sobre el "3"):
#####S###
# #···#
# #####·#
# #·····#
# #·# # #
# ··# # #
##·# # #
##E######
Com veieu, el camí manté la "connectivitat a 4". El laberint resultant amb el camí marcat s'haura de guardar en un nou arxiu que es dirà "lab_trobat.txt" per tal que l'usuari pugui llavors guardar la solució.
Passos de la Pràctica
Així doncs, els passos que cal seguir per a resoldre la pràctica són els següents:
El Programa Principal
Cal que el programa principal (on hi haurà el "main()") estigui en un arxiu que es digui: "laberint.c"
En aquest arxiu no hi poden haver definicions de TADs.
El TAD Laberint
Cal que definiu un TAD Laberint per tal de poder llegir laberints d'un arxiu "laberint.txt" i poder llavors treballar amb ell ja en memòria. La definició del TAD Laberint ha de tenir les següents parts:
Definir les operacions que formen la "interficie" (o signatura) del TAD. Per exemple: crea_laberint: --> laberint
Cal tenir en compte que haureu de pensar molt bé quines operacions necessitareu per a omplir, consultar, modificar, etc., el laberint, ja que des del programa principal tan sols podreu utilitzar aquestes operacions de la "interficie".
No cal fer l'especificació algebràica.
Definir el tipus concret amb que s'implementarà el TAD. Se suggereix fer-ho amb un "array" bi-dimensional de "char" ja que els laberints mai no seran més grans que 50x50.
Implementar totes les operacions del TAD Laberint definides al punt 1.
Tot això s'haurà de fer en un arxiu "TADLab.c" amb el seu arxiu capçalera corresponent per tal de poder-ho utilitzar des del programa principal.
Cal tenir en compte que el TADLab també ha de permetre llegir l'arxiu "laberint.txt" per a importar un nou laberint a ser analitzat, i també ha de permetre desar el laberint amb el camí trobat a l'arxiu "lab_trobat.txt".
Estructures Auxiliars
Per tal de poder resoldre la cerca d'un camí entre "E" i "S", us haureu d'ajudar de dos TADs auxiliars que tindran les següents propietats:
Camí Recorregut:
La primera estructura auxilar us ha de permetre anar guardant el camí que heu recorregut.
Aquest camí recorregut us servirà per a poder marcar-lo sobre el laberint quan hagueu confirmat que existeix un camí de "E" a "S" i així desar-ho a "lab_trobat.txt".
Aquest camí recorregut també us ha de permetre tornar sobre les vostres passes quan us trobeu amb un camí sense sortida. En aquesta situació heu de tirar enrere fins a la cruïlla més propera on intentareu triar una altra opció de sortida.
Cruïlles Pendents:
La segona estructura auxiliar us ha de permetre anar guardant les opcions que han quedat sense explorar en cada cruïlla per la que heu passat.
En cas de trobar-vos en un camí sense sortida, tirareu enrere per on heu vingut fins a la darrera cruïlla que havíeu passat i en aquella hi haureu d'agafar una nova direcció o branca per a intentar trobar la sortida.
Aquestes estructures auxiliars hauran d'estar definides amb un TAD cadascuna. Cada una serà un TAD dels que ja hem vist a classe i per tant haureu de decidir quin dels TADs vistos s'hi adapta millor a la tasca necessària.
Pista: aquestes estructures auxilars seran o bé dues cues, o bé dues piles, o bé una cua i una pila.
Per a cada una cal fer un arxiu de TAD separat: "TADCami.c" i "TADCruilles.c" amb es seves capçaleres corresponents. Com que els dos seran TADs molt estàndards, no cal que els especifiqueu.
La present pràctica proposa que donat un laberint (en un format especificat més avall), l'aplicació ha de determinar si existeix, o no, un camí des de la marca de Entrada fins a la de Sortida. Si efectivament existeix, l'aplicació ha de mostrar el camí recorregut (en cas que hi hagi més d'un camí, tan sols cal mostrar-ne un qualsevol) marcant-lo sobre el format del laberint original.
Fomat del Laberint
El laberint serà codificat com una matriu de MxN caracters en un arxiu ASCII anomenat "laberint.txt". El laberint estarà format per parets, passadissos, una única entrada i una única sortida.
Parets: el caracter "#" serà el que ens servirà per a definir on hi ha paret. Les parets poden tenir el gruix que es desitgi.
Passadís: el caracter " " (espai) serà el que definirà els passadissos per on es pot recòrrer el laberint. Aquests passadissos sempre seran de 1 sol caracter d'amplada. A més, en les cruïlles, tan sols tindran continuitat vertical i/o horitzontal (el que es coneix com "connectivitat a 4"), però mai diagonal. És a dir, l'exemple (1) sí presenta continuitat, mentre que el (2) no:
##### #####
## ## # # #
# # ## ##
## ## # # #
##### #####
(1) (2)
Entrada: aquesta vindrà marcada pel caracter "E" i sempre estarà situada en algún punt de la paret inferior del laberint, excepte les cantonades.
Sortida: aquesta vindrà marcada pel caracter "S" i sempre estarà situada en algún punt de la paret superior del laberint, excepte les cantonades.
Així doncs, un exemple de laberint seria:
#####S###
# # #
# ##### #
# # #
# # # # #
# # # #
## # # #
##E######
Aquest laberint té una mida 8x8, però no tots han de ser necessàriament quadrats. En aquest cas, el programa diria que SI existeix un camí des de l'entrada fins la sortida i per tant hauria de donar com a resultatel següent laberint amb el camí marcat amb el caracter "·" (punt volat, el que está situat habitualment en el teclat sobre el "3"):
#####S###
# #···#
# #####·#
# #·····#
# #·# # #
# ··# # #
##·# # #
##E######
Com veieu, el camí manté la "connectivitat a 4". El laberint resultant amb el camí marcat s'haura de guardar en un nou arxiu que es dirà "lab_trobat.txt" per tal que l'usuari pugui llavors guardar la solució.
Passos de la Pràctica
Així doncs, els passos que cal seguir per a resoldre la pràctica són els següents:
El Programa Principal
Cal que el programa principal (on hi haurà el "main()") estigui en un arxiu que es digui: "laberint.c"
En aquest arxiu no hi poden haver definicions de TADs.
El TAD Laberint
Cal que definiu un TAD Laberint per tal de poder llegir laberints d'un arxiu "laberint.txt" i poder llavors treballar amb ell ja en memòria. La definició del TAD Laberint ha de tenir les següents parts:
Definir les operacions que formen la "interficie" (o signatura) del TAD. Per exemple: crea_laberint: --> laberint
Cal tenir en compte que haureu de pensar molt bé quines operacions necessitareu per a omplir, consultar, modificar, etc., el laberint, ja que des del programa principal tan sols podreu utilitzar aquestes operacions de la "interficie".
No cal fer l'especificació algebràica.
Definir el tipus concret amb que s'implementarà el TAD. Se suggereix fer-ho amb un "array" bi-dimensional de "char" ja que els laberints mai no seran més grans que 50x50.
Implementar totes les operacions del TAD Laberint definides al punt 1.
Tot això s'haurà de fer en un arxiu "TADLab.c" amb el seu arxiu capçalera corresponent per tal de poder-ho utilitzar des del programa principal.
Cal tenir en compte que el TADLab també ha de permetre llegir l'arxiu "laberint.txt" per a importar un nou laberint a ser analitzat, i també ha de permetre desar el laberint amb el camí trobat a l'arxiu "lab_trobat.txt".
Estructures Auxiliars
Per tal de poder resoldre la cerca d'un camí entre "E" i "S", us haureu d'ajudar de dos TADs auxiliars que tindran les següents propietats:
Camí Recorregut:
La primera estructura auxilar us ha de permetre anar guardant el camí que heu recorregut.
Aquest camí recorregut us servirà per a poder marcar-lo sobre el laberint quan hagueu confirmat que existeix un camí de "E" a "S" i així desar-ho a "lab_trobat.txt".
Aquest camí recorregut també us ha de permetre tornar sobre les vostres passes quan us trobeu amb un camí sense sortida. En aquesta situació heu de tirar enrere fins a la cruïlla més propera on intentareu triar una altra opció de sortida.
Cruïlles Pendents:
La segona estructura auxiliar us ha de permetre anar guardant les opcions que han quedat sense explorar en cada cruïlla per la que heu passat.
En cas de trobar-vos en un camí sense sortida, tirareu enrere per on heu vingut fins a la darrera cruïlla que havíeu passat i en aquella hi haureu d'agafar una nova direcció o branca per a intentar trobar la sortida.
Aquestes estructures auxiliars hauran d'estar definides amb un TAD cadascuna. Cada una serà un TAD dels que ja hem vist a classe i per tant haureu de decidir quin dels TADs vistos s'hi adapta millor a la tasca necessària.
Pista: aquestes estructures auxilars seran o bé dues cues, o bé dues piles, o bé una cua i una pila.
Per a cada una cal fer un arxiu de TAD separat: "TADCami.c" i "TADCruilles.c" amb es seves capçaleres corresponents. Com que els dos seran TADs molt estàndards, no cal que els especifiqueu.
_Catwoman_
14 de Febrero del 2005
Nadie me va a ayudar? : ( por fii
Al menos como puedo empezar
Espero respuestas de alguien muxas asias!
Sonia
Al menos como puedo empezar
Espero respuestas de alguien muxas asias!
Sonia