Resum: Es presenten dues sopes A i B amb n mL cadascuna. A cada torn es selecciona a l'atzar una de quatre operacions amb probabilitat 0.25: servir 100 mL d'A i 0 mL de B; servir 75 mL d'A i 25 mL de B; servir 50 mL d'A i 50 mL de B; servir 25 mL d'A i 75 mL de B. El procés acaba quan A o B es buiden. Si una operació demana més quantitat de la disponible, només se serveix el que queda. L'objectiu és calcular la probabilitat que A es buidi abans que B més la meitat de la probabilitat que totes dues es buidin en el mateix pas.
Intuïció: Cada torn redueix totes dues quantitats i el resultat depèn de quin recipient s'esgota primer o si tots dos s'esgoten simultàniament. Les quatre operacions generen una estructura probabilística en forma d'arbre i el problema consisteix a calcular el valor esperat recorrent aquest arbre. És natural emprar memorització per emmagatzemar resultats de subproblemes que es repeteixen. Per a n gran, específicament per sobre de 4500 mL, el resultat convergeix molt a prop d'1.0, per la qual cosa es pot retornar 1 com a drecera.
Simplificació: Per reduir l'espai d'estats es treballa amb unitats de 25 mL. És a dir, es converteix n en m igual al sostre de n dividit entre 25. D'aquesta manera cada operació es representa per decrements enters en aquestes unitats i es limita el nombre d'estats a calcular.
Enfocament: Es defineix una funció p(a, b) que retorna la probabilitat desitjada partint de a unitats d'A i b unitats de B. Casos base: si a és menor o igual que zero i b és menor o igual que zero retornar 0.5; si a és menor o igual que zero retornar 1; si b és menor o igual que zero retornar 0. Per a un estat general p(a, b) és igual a 0.25 per la suma de les quatre crides recursives amb els decrements corresponents. S'usa memorització amb una matriu bidimensional o un diccionari per emmagatzemar resultats i evitar recàlculs.
Pseudocodi: funció p de a coma b: si a és menor o igual que zero i b és menor o igual que zero retornar 0.5. Si a és menor o igual que zero retornar 1. Si b és menor o igual que zero retornar 0. Si existeix resultat a memo retornar resultat. Calcular resultat igual a 0.25 multiplicat per la suma de p amb a menys 4 coma b; p amb a menys 3 coma b menys 1; p amb a menys 2 coma b menys 2; p amb a menys 1 coma b menys 3. Guardar resultat a memo i retornar resultat. Funció principal sopaServings amb n: si n major que 4500 retornar 1. Calcular m igual al sostre de n dividit entre 25. Retornar p de m coma m.
Versions i notes d'implementació: En C++ es pot usar una matriu double size 300 per 300 i la funció recursiva p amb els casos base i memorització. En JavaScript és pràctic emprar un Map per memoritzar claus concatenades i una funció recursiva dp. En Python convé usar lru cache de functools per simplificar la memorització. En les tres implementacions la conversió a unitats de 25 mL i la drecera per a n major que 4500 milloren el rendiment.
Complexitat temporal i espacial: El nombre d'estats únics és de l'ordre de m al quadrat, on m és el sostre de n entre 25. En el pitjor cas per a n igual a 4500 això correspon aproximadament a 300 per 300, la qual cosa dona al voltant de 90000 estats. La complexitat espacial és del mateix ordre per l'ús de la taula de memorització bidimensional.
Reflexió final: Aquest exercici barreja probabilitat i programació dinàmica recursiva. Els elements clau són agrupar quantitats en unitats de 25 mL per limitar l'espai d'estats, usar memorització per evitar recomputació i aprofitar la convergència per a n gran. És un problema recomanable per practicar memorització, raonament probabilístic i optimització de l'espai d'estats.
Sobre Q2BSTUDIO: Q2BSTUDIO és una empresa de desenvolupament de programari i aplicacions a mida especialitzada en solucions tecnològiques per a empreses. Oferim programari a mida, aplicacions a mida, serveis d'intel·ligència artificial, ciberseguretat i consultoria en serveis cloud aws i azure. També desenvolupem serveis d'intel·ligència de negoci, implementacions de power bi, agents IA i solucions d'IA per a empreses que integren models d'intel·ligència artificial per optimitzar processos. Comptem amb equips experts en intel·ligència artificial, ciberseguretat i arquitectures cloud per transformar idees en productes escalables i segurs.
Contacte i serveis: Si necessites projectes d'aplicacions a mida, programari a mida, consultoria en intel·ligència artificial, ciberseguretat, serveis cloud aws i azure, serveis d'intel·ligència de negoci, agents IA, IA per a empreses o implementacions de power bi, Q2BSTUDIO pot ajudar-te a dissenyar, construir i desplegar solucions adaptades a les teves necessitats empresarials.
