Aquí més enllaços:
http://users.dsic.upv.es/asignaturas/facultad/alt/problemas/RioCongo/
Sembla que aquest altre conté enllaç (inoperatiu) a codi font:
https://sercastro.wordpress.com/2008/12/08/backtracking-rio-congo/
https://web.archive.org/web/20090211051356/http://amigosdeloajeno.mihost.eu/backtracking-rio-congo/
El dia 30 de maig de 2017 a les 0:54, ALEJANDRO CASTAN SALINAS <
acastan@xxxxxxxx> ha escrit:
He trobat el problema del riu amb solució o indicacions a aquest document:
http://www.koinovacance.org/ig24/ig24-problemas.pdf
a les pàgines 15, 129 i 154
I també a:
www.dsic.upv.es/asignaturas/facultad/alt/problemas/Interes/BOLETIN.ps
http://docplayer.es/12177767-Algoritmica-curso-2009-2010-
seminario-de-python-3-y-el-problema-del-rio-congo.html
El dia 30 de maig de 2017 a les 0:12, Enric Mieza <emieza@xxxxxxxx> ha
escrit:
Jo vaig plantejar un arbre binari: des de qualsevol embarcador nomes tinc
2 opcions, i+1 o i+2
Dp es tracta de buscar totes les rutes o recorreguts per arribar al
embarcador N. Cal fer un recorregut d'arbre de qualsevol tipus: preorder,
inorder o postorder, i elaborar una llista dels rutes possibles.
Finalment, de tots els camins cal trobar aquell q minimitzi el cost,
sabent q tenim la funció C(i,j) on j ha de ser i+1 o i+2 (i no s'especifica
aquesta funció, només es diu q la podem invocar).
I per rematar-ho, com ha dit l'Eduard (però q jo no vaig fer), es pot
optimitzar decartant les rutes q ofereixin un cost major q alguna de les q
ja s'han avaluat. Deu ser un "prune". O sigui combinar la cerca per l'arbre
amb l'avaluació del cost tot del tirón al mateix temps.
Vaig bé?
Jo no vaig agafar les bitlles pq no l'acabava de veure clar, era com molt
facil i alhora, l'algorisme iteratiu podia desmadrar-se en quantitat de RAM
ocupada, així q vaig optar pel primer del arbre binari.
Salut!
Enric
El dia 29 maig 2017 22:40, "ALEJANDRO CASTAN SALINAS" <acastan@xxxxxxxx>
va escriure:
A primera vista i sense raonar em sembla un algorisme de Dijkstra
El dia 29 de maig de 2017 a les 17:30, EDUARD LAFITTE RIBERA <
elafitte@xxxxxxxx> ha escrit:
I per quedar bé, el bruixot fa una modificació per minimitzar el nombre
de trajectes possibles.
És a dir, que sí a mig càlcul ja passes del cost mínim que tinguis fins
aquell moment, abandones aquell possible trajecte.
El 29 may. 2017 15:56, "Enric Mieza" <emieza@xxxxxxxx> escribió:
s'entén per "ruta òptima" aquella que minimitzi els costos calculats
amb la funció (c).
Aquesta ruta sempre serà en salts de 1 o de 2 embarcadors (pel tema
provisions).
Enric
2017-05-29 15:53 GMT+02:00 Enric Mieza <emieza@xxxxxxxx>:
Exercici A especialitat 507
El rei del Congo viatja pel riu més estupendu del seu país,
d'embarador en embarcador. Parteix del 1r, al naixement del riu, i només
pot descendre el riu, sense remuntar. Quan parteix d'un embarxador i,
només
pot anar al i+1 o bé a, i+2 perquè ha de parar a agafar provisions.
El rei, molt aficionat a les mates, ha calculat el cost que li suposa
tots i cadascun dels viatges desde qualsevol embarcador: la funció que
permet calcular c(i,i+1) i c(i,i+2)
Li demana al màxim bruixot que realitzi un algorisme que li calculi la
ruta òptima entre l'inici (embarcador 1) i l'embarcador N, éssent E el
darrer embarcador i on 1 <= N <= E
Es demana especificar les estructures de dades necessàries per a poder
realitzar el càlcul.
Clarificar els algorismes típics i les modificacions que cal fer-los
per adaptar-los al nostre cas.
Codificar el programa en un dels llenguatges favorits del rei (com no,
C, C++, Java).
...i no sé si em deixo alguna cosa més...
Salut!
Enric
2017-05-29 15:33 GMT+02:00 ESTER MARSAL ROCA <emarsal2@xxxxxxxx>:
Hola,
Aquí hi ha l'exercici de l'opció B de la part A del cos 507. És un
redactat aproximat del què recordo:
Les bitlles en un bowling es col·loquen en forma de triangle
equilàter, a cada fila hi ha una bitlla més que la fila anterior
Entrada
C N N...
On C és la quantitat de casos i N la quantitat de bitlles que cal
col·locar com a mínim
Sortida
Quantitat de files que tindrà el triangle, per cada cas
La C és un valor entre 0 i 10.000 sense incloure el 0,
La N és un valor entre 0 i 10^9 sense incloure el 0.
Es demana:
1. Indicar l'estructura de dades que es faran servir
2. Dissenyar l'algoritme en pseudocodi
3. Desenvolupar un mòdul significatiu en C, C++ o Java
4. Calcular el cost de l'algoritme
5. Màxima optimització (Cost 1)
Ester
El dia 29 de maig de 2017 a les 12:33, Joan Josep Ordinas Rosa <
jordinas@xxxxxxxxxxxxxxxxxxxxxxxxxxx> ha escrit:
per curiositat, podeu posar en comú els exercicis que us hagin posat
als opositors en l'exercici de programació?
JJOR
--
« Cap home segueix sent massa el que era quan es reconeix a si
mateix. »
Thomas Mann
--
Enric Mieza Sánchez
Departament d'Informàtica
Institut Esteve Terradas
C/ Bonavista, 70
(Cornellà de Llobregat)
Telf. 93 377 11 00
http://www.esteveterradas.cat ;<http://www.iesesteveterradas.com/>
--
Enric Mieza Sánchez
Departament d'Informàtica
Institut Esteve Terradas
C/ Bonavista, 70
(Cornellà de Llobregat)
Telf. 93 377 11 00
http://www.esteveterradas.cat ;<http://www.iesesteveterradas.com/>
--
Àlex Castán Salinas
Institut Ausiàs March
avinguda d’Esplugues, 38-42, 08034 Barcelona
telèfon. 93-203-33-32 <932%2003%2033%2032> (tardes) , 689-46-56-36
<689%2046%2056%2036>
--
Àlex Castán Salinas
Institut Ausiàs March
avinguda d’Esplugues, 38-42, 08034 Barcelona
telèfon. 93-203-33-32 (tardes) , 689-46-56-36
