{"id":2456,"date":"2016-05-18T06:00:04","date_gmt":"2016-05-18T04:00:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2456"},"modified":"2022-03-26T14:29:26","modified_gmt":"2022-03-26T12:29:26","slug":"problema-de-las-jarras-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/problema-de-las-jarras-1\/","title":{"rendered":"Problema de las jarras"},"content":{"rendered":"<p>En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medici\u00f3n, una de A litros de capacidad y otra de B. Tambi\u00e9n se dispone de una bomba que permite llenar las jarras de agua.<\/p>\n<p>El <strong>problema de las jarras<\/strong> (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.<\/p>\n<p>Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   jarras :: (Int,Int,Int) -> [[(Int,Int)]]\n<\/pre>\n<p>tal (jarras (a,b,c)) es la lista de las soluciones del problema de las<br \/>\njarras (a,b,c). Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 2 (map snd (sort [(length xs,xs) | xs <- jarras (4,3,2)]))\n   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],\n    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]\n<\/pre>\n<p>La interpretaci\u00f3n [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:<\/p>\n<ul>\n<li>(0,0) se inicia con las dos jarras vac\u00edas,<\/li>\n<li>(4,0) se llena la jarra de 4 con el grifo,<\/li>\n<li>(1,3) se llena la de 3 con la de 4,<\/li>\n<li>(1,0) se vac\u00eda la de 3,<\/li>\n<li>(0,1) se pasa el contenido de la primera a la segunda,<\/li>\n<li>(4,1) se llena la primera con el grifo,<\/li>\n<li>(2,3) se llena la segunda con la primera.<\/li>\n<\/ul>\n<p>Otros ejemplos<\/p>\n<pre lang=\"text\">\n   \u03bb> (snd . head . sort) [(length xs,xs) | xs <- jarras (15,10,5)]\n   [(0,0),(15,0),(5,10)]\n   \u03bb> jarras (15,10,4)\n   []\n<\/pre>\n<p>Nota: Las librer\u00edas necesarias se encuentran en la <a href=\"https:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/codigosDeTemas.php\">p\u00e1gina de c\u00f3digos<\/a>.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEspaciosDeEstados\n\n-- Un problema queda determinado por las capacidades de las dos jarras y\n-- el contenido que se desea lograr \n\n-- Un estado es una lista de dos n\u00fameros. El primero es el contenido de\n-- la jarra de 4 litros y el segundo el de la de 3 litros. \ntype EstadoJarras = (Int,Int)\n\ninicialJarras :: EstadoJarras\ninicialJarras = (0,0)\n\nesFinalJarras :: (Int,Int,Int) -> EstadoJarras -> Bool\nesFinalJarras (_,_,c) (x,_) = x == c\n\nsucesoresEjarras :: (Int,Int,Int) -> EstadoJarras -> [EstadoJarras]\nsucesoresEjarras (a,b,_) (x,y) =\n    [(a,y) | x < a] ++\n    [(x,b) | y < b] ++\n    [(0,y) | x > 0] ++\n    [(x,0) | y > 0] ++\n    [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++\n    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++\n    [(x+y,0) | y > 0, x + y <= a] ++ \n    [(0,x+y) | x > 0, x + y <= b]\n\n-- Los nodos son las soluciones parciales\ntype NodoJarras = [EstadoJarras]\n\ninicialNjarras :: NodoJarras\ninicialNjarras = [inicialJarras]\n\nesFinalNjarras :: (Int,Int,Int) -> NodoJarras -> Bool\nesFinalNjarras p (e:_) = esFinalJarras p e\n\nsucesoresNjarras :: (Int,Int,Int) -> NodoJarras -> [NodoJarras]\nsucesoresNjarras p n@(e:es) =\n    [e':n | e' <- sucesoresEjarras p e,\n            e' `notElem` n]\n\nsolucionesJarras :: (Int,Int,Int) -> [NodoJarras]\nsolucionesJarras p = buscaEE (sucesoresNjarras p)\n                             (esFinalNjarras p)\n                             inicialNjarras\n\njarras :: (Int,Int,Int) -> [[(Int,Int)]]\njarras p = map reverse (solucionesJarras p)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medici\u00f3n, una de A litros de capacidad y otra de B. Tambi\u00e9n se dispone de una bomba que permite llenar las jarras de agua. El problema de las jarras (A,B,C) consiste en determinar c\u00f3mo se puede lograr tener exactamente C litros&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[353,8,456,10,27,11,32],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2456"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2456"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2456\/revisions"}],"predecessor-version":[{"id":2489,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2456\/revisions\/2489"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}