divMod

El problema del reciclado

PorJosé A. Alonso 28-marzo-20174-abril-2017

El problema del reciclado N P consiste en lo siguiente: un grupo de personas disponen de N botellas de refresco vacía y las llevan a reciclar obteniendo una botella llena por cada P vacías; se beben inmediatamente el contenido de las botellas obtenidas y sus botellas vacías, junto con las no recicladas anteriormente, las canjean por botellas llenas. El proceso continúa hasta que no tienen suficientes botellas para canjear. El objetivo del problema es calcular el número de botellas que se han bebido.

Por ejemplo, si disponen de 10 botellas y por cada 2 obtienen 1, se producen cuatro canjeos:

en el primer canjeo entregan las 10 y obtienen 5;
en el segundo, entregan 4, le quedan 1 y obtienen 2;
en el tercero, entregan 2, le queda 1 y obtienen 1;
en el cuarto, entregan 2 y obtienen 1.

Por tanto, se han bebido 9 y le quedan 1 que no pueden canjear.

Definir la función

   reciclado :: Int -> Int -> Int

1	reciclado :: Int -> Int -> Int

tal que (reciclado n p) es el número de botellas que se beben en el reciclado comenzado con n botellas y canjeando p botellas vacías por una llena. Por ejemplo,

   reciclado  9 3  ==  4
   reciclado 10 2  ==  9

1 2	reciclado 9 3 == 4 reciclado 10 2 == 9

Referencia: Este ejercicio está basado en el problema Soda surpler de Kattis.

Soluciones

reciclado :: Int -> Int -> Int
reciclado n p = aux n 0
  where aux x k | x < p     = k
                | otherwise = aux (a+b) (k+a) 
          where (a,b) = divMod x p

reciclado :: Int -> Int -> Int

reciclado n p = aux n 0

where aux x k | x < p = k

| otherwise = aux (a+b) (k+a)

where (a,b) = divMod x p

Máximo producto de pares en la lista

PorJosé A. Alonso 30-enero-201726-marzo-2022

Definir la función

  maximoProducto :: [Int] -> Maybe Int

1	maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

   maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
   maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
   maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
   maximoProducto [2,4]                    ==  Nothing
   maximoProducto [2, 5, 7, 8]             ==  Nothing
   maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
   maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

maximoProducto [10, 3, 5, 30, 35] == Just 30

maximoProducto [10, 2, 2, 4, 30, 35] == Just 4

maximoProducto [17, 2, 1, 35, 30] == Just 35

maximoProducto [2,4] == Nothing

maximoProducto [2, 5, 7, 8] == Nothing

maximoProducto [10, 2, 4, 30, 35] == Nothing

maximoProducto [1+2^n | n <- [1..10^6]] == Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

import Data.List (delete, nub, sort)

-- 1ª solución
-- ===========

maximoProducto1 :: [Int] -> Maybe Int
maximoProducto1 xs
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where
    ys = reverse (sort xs)
    zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos
-- elementos de xs. Por ejemplo, 
--   productos [4,3,5,2]  ==  [12,20,8,15,6,10]
productos :: [Int] -> [Int]
productos xs =
  nub [y * z | y <- xs, z <- delete y xs]

-- 2ª solución
-- ===========

maximoProducto2 :: [Int] -> Maybe Int
maximoProducto2 xs = aux (reverse (sort xs))
  where aux []     = Nothing
        aux (y:ys) | esProducto y xs = Just y
                   | otherwise       = aux ys

esProducto :: Int -> [Int] -> Bool
esProducto y []     = False
esProducto y (x:xs) = 
  (m == 0 && d `elem` xs) || esProducto y xs
  where (d,m) = divMod y x  

-- Comparación de eficiencia
-- =========================

--    λ> maximoProducto1 [1..10^4]
--    Just 10000
--    (2.60 secs, 0 bytes)
--    λ> maximoProducto2 [1..10^4]
--    Just 10000
--    (0.01 secs, 0 bytes)

import Data.List (delete, nub, sort)

-- 1ª solución

-- ===========

maximoProducto1 :: [Int] -> Maybe Int

maximoProducto1 xs

| null zs = Nothing

| otherwise = Just (head zs)

where

ys = reverse (sort xs)

zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos

-- elementos de xs. Por ejemplo,

-- productos [4,3,5,2] == [12,20,8,15,6,10]

productos :: [Int] -> [Int]

productos xs =

nub [y * z | y <- xs, z <- delete y xs]

-- 2ª solución

-- ===========

maximoProducto2 :: [Int] -> Maybe Int

maximoProducto2 xs = aux (reverse (sort xs))

where aux [] = Nothing

aux (y:ys) | esProducto y xs = Just y

| otherwise = aux ys

esProducto :: Int -> [Int] -> Bool

esProducto y [] = False

esProducto y (x:xs) =

(m == 0 && d `elem` xs) || esProducto y xs

where (d,m) = divMod y x

-- Comparación de eficiencia

-- =========================

-- λ> maximoProducto1 [1..10^4]

-- Just 10000

-- (2.60 secs, 0 bytes)

-- λ> maximoProducto2 [1..10^4]

-- Just 10000

-- (0.01 secs, 0 bytes)

Cantidad de números Pentanacci impares

PorJosé A. Alonso 18-febrero-20162-mayo-2016

Los números de Pentanacci se definen mediante las ecuaciones

   P(0) = 0
   P(1) = 1
   P(2) = 1
   P(3) = 2
   P(4) = 4
   P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

P(0) = 0

P(1) = 1

P(2) = 1

P(3) = 2

P(4) = 4

P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4

Los primeros números de Pentanacci son

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

1	0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Se obseeva que

hasta P(5) hay 1 impar: el 1 (aunque aparece dos veces);
hasta P(7) hay 2 impares distintos: 1 y 31;
hasta P(10) hay 3 impares distintos: 1, 31 y 61;
hasta P(15) hay 5 impares distintos: 1, 31 y 61, 1793 y 3525.

Definir la función

   nPentanacciImpares :: Integer -> Integer

1	nPentanacciImpares :: Integer -> Integer

tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,

   nPentanacciImpares 5                             ==  1
   nPentanacciImpares 7                             ==  2
   nPentanacciImpares 10                            ==  3
   nPentanacciImpares 15                            ==  5
   nPentanacciImpares 100                           ==  33
   nPentanacciImpares 1000                          ==  333
   nPentanacciImpares 10000                         ==  3333
   nPentanacciImpares (10^(10^6)) `mod` (10^9)      ==  333333333
   length (show (nPentanacciImpares2 (10^(10^6))))  ==  1000000

nPentanacciImpares 5 == 1

nPentanacciImpares 7 == 2

nPentanacciImpares 10 == 3

nPentanacciImpares 15 == 5

nPentanacciImpares 100 == 33

nPentanacciImpares 1000 == 333

nPentanacciImpares 10000 == 3333

nPentanacciImpares (10^(10^6)) `mod` (10^9) == 333333333

length (show (nPentanacciImpares2 (10^(10^6)))) == 1000000

Soluciones

import Data.List (genericLength, genericTake)

-- 1ª definición 
-- =============

nPentanacciImpares1 :: Integer -> Integer
nPentanacciImpares1 0 = 0
nPentanacciImpares1 1 = 1
nPentanacciImpares1 n = 
    genericLength (filter odd (genericTake (n+1) pentanacci)) - 1

pentanacci :: [Integer]
pentanacci = p (0, 1, 1, 2, 4)
    where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

-- 2ª definición
-- =============

-- λ> map nPentanacciImpares1 [1..31]
-- [1,1,1,1,1,1,2,3,3,3,3,3,4,5,5,5,5,5,6,7,7,7,7,7,8,9,9,9,9,9,10]
-- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])]
-- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)]

nPentanacciImpares2 :: Integer -> Integer
nPentanacciImpares2 0 = 0
nPentanacciImpares2 1 = 1
nPentanacciImpares2 n = 2 * q + min r 2 - 1
    where (q,r) = n `quotRem` 6

-- 3ª definición
-- =============

nPentanacciImpares3 :: Integer -> Integer
nPentanacciImpares3 0 = 0
nPentanacciImpares3 1 = 1
nPentanacciImpares3 n | r == 5    = 2*q + 2 
                      | otherwise = 2*q + 1 
    where (q,r) = divMod (n-2) 6

import Data.List (genericLength, genericTake)

-- 1ª definición

-- =============

nPentanacciImpares1 :: Integer -> Integer

nPentanacciImpares1 0 = 0

nPentanacciImpares1 1 = 1

nPentanacciImpares1 n =

genericLength (filter odd (genericTake (n+1) pentanacci)) - 1

pentanacci :: [Integer]

pentanacci = p (0, 1, 1, 2, 4)

where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

-- 2ª definición

-- =============

-- λ> map nPentanacciImpares1 [1..31]

-- [1,1,1,1,1,1,2,3,3,3,3,3,4,5,5,5,5,5,6,7,7,7,7,7,8,9,9,9,9,9,10]

-- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])]

-- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)]

nPentanacciImpares2 :: Integer -> Integer

nPentanacciImpares2 0 = 0

nPentanacciImpares2 1 = 1

nPentanacciImpares2 n = 2 * q + min r 2 - 1

where (q,r) = n `quotRem` 6

-- 3ª definición

-- =============

nPentanacciImpares3 :: Integer -> Integer

nPentanacciImpares3 0 = 0

nPentanacciImpares3 1 = 1

nPentanacciImpares3 n | r == 5 = 2*q + 2

| otherwise = 2*q + 1

where (q,r) = divMod (n-2) 6

El problema del reciclado

Soluciones

Máximo producto de pares en la lista

Soluciones

Cantidad de números Pentanacci impares

Soluciones

Entradas recientes

Buscar

Correo electrónico